ผ่าน Round 1 – Google Code Jam 2009 แล้วว

ปีนี้เป็นปีแรกที่ได้แข่ง Google Code Jam ครับ เนื่องจากปีที่แล้ว ติดภารกิจเอาแชมป์โลก เลยได้แต่นั่งดูเพื่อนแข่งตากะปิปกะปิป

ปีนี้เลยไม่พลาดแน่ และก็ผ่านรอบ Qualification ไปแบบเฉียดๆ ทำแล้วรุ้สึกว่าตัวเองล้างรา เขียนโปรแกรมแนว algorithm อย่างมาก

แถมด้วย ใช้ C# เป็นอาวุธ ประจำกาย ก็พบว่า วิทยายุทธลืมเลือนไปมาก จะ sort list ทีนึง ทำไงหว่า? จะหา stack ใช้ มันมีคลาสอะไรแล้วนะ?

อารเรย์สองมิติทำไง ก็ต้องถาม google ทำให้ ทุลักทุเล โค้ดน่าเกลียด จนไม่อาจเอามาเผยแพร่ได้

สำหรับ Round 1 นี้ เค้าแบ่ง เป็น 3 sub-round มี 1A , 1B และ 1C  เรียกว่าแข่งได้ 3 รอบ และเอา 1000 คนแรกของแต่ละรอบเข้ารอบต่อไปครับ

Round 1A

นอนหลับน้ำลายยืด อยู่บนเตียง เพราะลืมไปว่ามีแข่งครับ ปรากฏว่าวันนั้นตื่นมาบ่าย 2

Round 1B

พร้อมมาก นั่งรอตั้งแต่ก่อน 1 ชม. พอเริ่ม ก็เลือกทำข้อ 3 ที่คะแนนเยอะสุดก่อนเลย แล้วก็ ได้ทำแค่นั้นแหละ ติดอยู่นานและ ไม่อยากจะทิ้งครับ

เหมือนจะออกๆ แล้ว แต่สุดท้าย ก็กิน 0 ไป ไม่ได้ซักแต้ม

Round 1C

ลังเลว่า จะดูกันดั้ม ดีหรือ แข่งอีกดี แต่ก็คิดว่า ปีนึงมีหน เลยลงมือครับ กะว่าพวกเซียนผ่านเข้ารอบไปหมดแล้ว

ข้อที่ 1 All Your Base

ข้อนี้อ่านโจทย์แล้วเข้าใจครับ แต่ทำไม คิดในหัวกับ ตัวอย่าง Input , Ouput ที่ให้มาแล้ว ไม่เห็นถูกเลย!

โจทย์ผมเข้าใจว่า alien ส่งเลขจำนวนอีกกี่วินาทีที่จะบุกโลกมา ให้แปลงสัญลักษณ์ในตัวเลขของ alien แต่ละหลัก

ให้เป็น digit ซักอันใน base ใดๆ แล้ว จะมี base นึงที่ ได้เวลาวินาที น้อยสุด

ลองคิดมือ ดูแล้ว คำตอบไม่ตรง ผ่าน!! แล้วกัน

ข้อ 2 Center Of Mass

อ่านจบ คิดๆซักพัก นี่มันโจทย์แคล! ม.ปลายนี่นา หยิบกระดาษที่ รอบ 1B ไม่ได้เขียนอะไรเลยมา นั่งทดๆๆ เขียนๆ จนได้สูตรออกมาครับ

อย่างแรกคือ หาตำแหน่ง center of mass ก่อน ซึ่งก็ โจทย์มันบอกเทียบกับตัวเรา แต่เรา ยืน (0,0,0) อยุ่แล้ว และมวลของ fireflies เท่ากันหมด

เพราะฉะนั้น C(x,y,z) ก็จะเทียบกับตัวเราโดยอัตโนมัติ ก็คิดแยกแกนได้สูตรดังนี้

เสร็จแล้วก็ เอา dx,dy,dz มาหา distance รวม ก็กำลังสองถอดรูท(Euclidean Distance) ได้สูตร d ขึ้น กับ t มา

เค้าต้องการหาระยะทางที่สั้นที่สุดทีเกิดขึ้น ก็ใช้หาจุดต่ำสุดสูงสุดสัมพัทธ์ ก็ดิฟ d เทียบ t = 0

จะสังเกตว่า โจทย์บอกความเร็วคงที่ เหมือนบอกเพื่อให้ดิฟโดยไม่ต้องระวัง v กลายเป้น a ก็เลยได้สูตรมาประมาณนี้

ก็เขียนโค้ดได้เลยยย  มีจุดระวังนิดหน่อยเรื่องหายด้วย ศูนย์และเวลาติดลบ

namespace GoogleCodeJam2009
{
    public class CenterOfMass : ISolver
    {
        Double vx;
        Double vy;
        Double vz;
        Double x;
        Double y;
        Double z;
        Double t;
        Double d;
        int T, N;

        public void Solve(TextReader reader, TextWriter writer)
        {
            T = Int32.Parse(reader.ReadLine());
            for (int i = 0; i < T; i++)
            {
                String[] tmp;
                vx = 0.0;
                vy = 0.0;
                vz = 0.0;
                x = 0.0;
                y = 0.0;
                z = 0.0;
                t = 0.0;
                d = 0.0;
                N = Int32.Parse(reader.ReadLine());
                for (int j = 0; j < N; j++)
                {
                    tmp = reader.ReadLine().Split(' ');
                    x += Double.Parse(tmp[0]);
                    y += Double.Parse(tmp[1]);
                    z += Double.Parse(tmp[2]);
                    vx += Double.Parse(tmp[3]);
                    vy += Double.Parse(tmp[4]);
                    vz += Double.Parse(tmp[5]);
                }
                t = -1*((vx * x) + (vy * y) + (vz * z)) / ((vx * vx) + (vy * vy) + (vz * vz));
                if (t < 0 || t.Equals(Double.NaN))
                    t = 0;
                d = Math.Pow(x + (t * vx), 2) + Math.Pow(y + (t * vy), 2) + Math.Pow(z + (t * vz), 2);
                d = Math.Abs(Math.Sqrt(d) / N);
                writer.WriteLine("Case #" + (i + 1) + ": " + String.Format("{0:0.00000000} {1:0.00000000}", d, t));
            }
        }
    }
}

ก็ผ่านทั้งข้อเล็กและใหญ่แบบฟลุค มีความรุ้สึกตะหงิดๆ ว่าต้องกันเงื่อนไขไม่ครบทางคณิตศาสตร์ แต่ผ่านหมดก็ดี

ข้อ 3 Bribes the Prisoners

อ่านโจทย์แล้วนึกถึง Prison Break ยังไม่ได้ดูภาค 4 เลย เอ้ย ดูโจทย์มันกลิ่นอาย Dynamic Programming มาก ซึ่งผมอ่อนแอยิ่งนัก

ก็นั่งพยายามคิดวิธีฉลาดๆ แต่คิดไม่ออก สุดท้ายเลย recursive แ-ง่งเลย  ก็เขียน recursive วนเลือก แบ่งซ้ายขวา แตกลงไปเรื่อยๆ

แล้วจะได้ least bribes ย้อนกลับขึ้นมา แล้วก็เลือกที่ดีที่สุดแต่ละชั้น (มันคล้าย divide and conquer เปล่าหว่า) นั่นแหละ รันผ่าน

small-set มาได้ แต่ พอ large-set นี่ ค้างไปเลยครับ  สุดท้ายก็แก้ไม่ทัน ปล่อยหมดเวลาไป ตอนนั้น เหลืออีกประมาณ 15 นาที กับที่ 700 กว่า

เลยนั่งจ้องเวลาเลย ที่ 860 ตอนเหลือ 5 นาที ตื่นเต้นมากกตอนนั้น ดูเพื่อนเหมือนไอแก๊นจะเข้ารอบแล้วที่ 600 กว่า

ที่ 937 ตอน 30 วินาที อ๊าก…..

…..

ปุ๊ป! จบที่ 779 แวีบแรก เห็นแล้วงง แต่อ๋ออ ข้อใหญ่มันยังไม่บอกคะแนนจริงนี่หว่า อืม จบที่ 779 ครับ

ผ่านเข้าสู้รอบ 2 ต่อไปครับ แต่คงไม่รอดแล้วล่ะ ฮ่าฮ่า แต่ก็สนุกดี

มีเว็บรวมสถิติ แยกตามประเทศให้ด้วยครับ รวมทั้งเฉลยภาษาต่างๆ (มีคนแก้บางข้อด้วย SQL ด้วยนะ o_O!) ให้ด้วย ไปดูกันได้