Life On VM

ครั้งนี้ตัดคำว่าเฉลยออกแล้ว ลดความมั่นใจลงหน่อยนึง - -‘a 

แต่ตั้งแต่ทำมา 3 ปี ปีนี้เป็นปีแรกที่ได้คะแนนเต็มรอบแรก T_T ดีใจ

ข้อแรก Snapper Chain

ถ้าเปลี่ยน ON เป็นเลข 1 แล้ว OFF เป็นเลขศูนย์ แล้วให้ปลั๊กไฟหลัก (Power) อยู่ซ้ายสุด

ถ้ามี Snapper สองอัน มันจะวิ่งตามลำดับนี้

00
10
01
11 <--- Light on!
00
10 …

ถ้าเป็น 3 อัน ก็พอจะเดาได้ว่ามันก็เป็นแบบนี้

000
100
010
110
001
101
011
111 <--- Light on!

สรุปว่ามันก็เหมือนกับนับเลขฐานสองกลับหลัง ดังนั้นถ้ามี snapper n อัน กรณีที่จะทำให้หลอดไฟติดได้ก็คงต้องเป็นการ snap เป็นจำนวน (c * 2^n) – 1 เท่านั้น (โดย c เป็นจำนวนเต็ม … บวก)

if __name__ == '__main__':
    fin = 'A-large.in'
    fon = 'A-large.out'
    
    fi = open(fin, 'r')
    fo = open(fon, 'w')
    
    c = int(fi.readline())
    for i in xrange(c):
        n, k = [int(x) for x in fi.readline().split(' ')]
        ans = (k % 2 ** n) == 2 ** n - 1
        fo.write("Case #%d: %s\n" % (i + 1, 'ON' if ans else 'OFF'))
    
    print "Done!"
    fi.close()
    fo.close()

ข้อสอง Fair Warning

ข้อนี้เข้าใจว่าเป็นเรื่องแนวๆ number theory

มีคนอ่านโจทย์แล้วงงเยอะมาก โจทย์มันถามว่า ต้องใช้เวลานานอย่างน้อยเท่าไหร่ ถึงจะทำให้ ตัวหารร่วมมากสุด (ห.ร.ม. – Greatest Common Divisor (GCD)) มีค่ามากที่สุด

ในโจทย์ตัวอย่างเป็น 26000 11000 6000 ดังนั้นถ้าเวลาผ่านไป 4000 sec (ซึ่งเป็นคำตอบที่ถูกต้อง) จะทำให้กลายเป็น 30000 15000 10000 และทำให้เลขชุดนี้มี GCD เป็น 5000 ซึ่งไม่ว่าจะเป็นเวลาก่อน 4000 sec หรือหลัง 4000 sec ไปอีกนานเท่าไหร่ก็ตาม GCD ที่หาได้ก็จะมีค่าไม่เกิน 5000 แน่นอน เช่นถ้าผ่านไปแค่ 2000 sec จะได้เลขชุดนี้เป็น 28000 13000 8000 ซึ่งมี GCD = 1000 (น้อยกว่า 5000)

ขอแทนเวลาที่ผ่านไปเรื่อยๆ ด้วยแถบยืดๆ x (ซึ่งยืดได้เท่าไหร่ก็ไม่รู้ แต่ต้องยืดเท่าๆกันสำหรับแต่ละ event)

<===== x ===...==><==  6000 ==>
<===== x ===...==><== 11000 ======>
<===== x ===...==><== 26000 ================>

หรือถ้าเรา define ให้ y = x + 6000 จะกลายเป็นรูปนี้ (เลือก 6000 เพราะเป็น MIN)

<===== y ===...=======>
<===== y ===...=======><== 5000 ======>
<===== y ===...=======><== 20000 ===========>

ทีนี้เราก็จะหา GCD ของ y, y+ 5000, และ y + 20000 .. ยกคุณสมบัติ GCD ที่จะใช้มาทวนก่อน

• gcd(a, b) = gcd(b, a) …. สลับที่
• gcd(a, gcd(b, c)) = gcd(gcd(a, b), c) …. เปลี่ยนกลุ่ม
• gcd(a, b) = gcd(b, a - b) … กรณี a > b

จากรูปด้านบน ถ้าเราหา GCD ระหว่าง y กับบรรทัดอื่นๆ ทีละคู่ จะได้อะไรประมาณนี้ออกมา

<===== y ===...=======>
<== 5000 ======>
<== 20000 ===========>

กลายเป็น gcd(5000, 20000, y) ทำโน่นนี่ไปมาจะได้ GCD = gcd(gcd(5000, 20000), y)

เนื่องจากว่าเราให้ y เป็นอะไรก็ได้อยู่แล้ว ดังนั้น MAX GCD = gcd(5000, 20000) = 5000 แน่นอน!

ต่อมา เราต้องการทราบ x น้อยที่สุด (เวลาน้อยที่สุดที่จะทำให้ได้ MAX GCD) ซึ่ง y = x + 6000

พบว่าในเคสนี้ x น้อยสุดเป็น 4000 ซึ่งทำให้ y เป็น (+) ได้ และหาร MAX GCD = 5000 ลงตัว

ขอสารภาพว่า … ข้อนี้ตอนทำไม่ได้คิด math แบบข้างบนหรอก (อ้าววว) นั่งวาดรูปๆๆๆ เดาๆๆ แล้วลองมั่วๆกับ sample ดู ถูกเคสเล็กก็ลองเคสใหญ่เลย ไอ่ที่ทำ math เพราะพยายามหาข้อสนับสนุนวิธีที่ทำไป(แล้ว) = =’

ขอขอบคุณ Python ทำให้ไม่ต้องไปวุ่นวายเรื่อง BigInteger แล้วก็ยังแถม fractions.gcd มาให้อีก!

(แอบภูมิใจบรรทัด reduce TvT)

import fractions

if __name__ == '__main__':
    fin = 'B-large.in'
    fon = 'B-large.out'
    
    fi = open(fin, 'r')
    fo = open(fon, 'w')
    
    c = int(fi.readline())
    for i in xrange(c):
        ts = [int(x) for x in fi.readline().split(' ')][1:]
        m = min(ts)
        tns = [x - m for x in ts]
        unit = reduce(lambda x,y: fractions.gcd(x,y), tns)
        r = m % unit
        ans = unit - r if r else 0 
        fo.write("Case #%d: %d\n" % (i + 1, ans))
    
    print "Done!"
    fi.close()
    fo.close()

ข้อสาม Theme Park

ข้อนี้ใช้วิธี pre-computed (หรือจะเรียกว่า cache ?) อะไรที่มันทำได้ไว้ก่อน ทำให้ตอนคำนวณจริงๆไม่ต้องทำอะไรซ้ำๆ แต่ถ้าทำแค่นี้มันจะยังไม่เร็วพอ (โดยเฉพาะถ้าเป็นโปรแกรม Python รันดิบๆ T_T’)

แนวคิดคือ ในการเล่นรอบใดๆที่มี group ที่อยู่หัวคิวเป็น group เดียวกัน (เช่นรอบ 3 กับรอบ 5 มี g1 เป็นหัวคิวเหมือนกัน) จะเก็บเงินได้เท่ากันเสมอ และหัว group ในรอบถัดไปก็จะเป็น group เดียวกันเสมอ …

ดังนั้นไอ่การคำนวณจำนวนคนนั่งในแต่ละรอบนี่ ทำครั้งเดียวก็พอ (สำหรับรอบที่ขึ้นต้นด้วยแต่ละ group) และก็ควรบันทึกไว้ด้วย ว่าหลังจาก group นี้เล่นในรอบนี้แล้ว รอบถัดไปจะเป็น group ไหน จากตัวอย่าง

grou: [1, 4, 2, 1]
hist: [5, 6, 4, 6]
next: [2, 3, 1, 2]

อันนี้บอกว่า ถ้าเริ่มที่ g0 เก็บเงินได้ 5 ในรอบนั้น, g1 เก็บได้ 6, ….

และถ้าเริ่มที่ g0 รอบถัดไปจะเริ่มที่ g2, เริ่ม g1 ถัดไปเริ่มที่ g3, เริ่ม g2 ถัดไปเริ่มที่ g1, …

โจทย์กำหนดมา r รอบ ก็แค่บวก hist แล้ววนตาม next ต่อไป r ครั้งก็น่าจะได้คำตอบแล้ว แต่อาจจะไม่ทัน …

ถ้าสังเกต next ดีๆ จะเห็นว่ามันวนซ้ำๆ

• g0 –> g2 –> g3 –> g1 –> g2 –> g3 –> g1 –> g2 –> g3 –> g1 –> g2 –> ….
• g0 –> (g2 –> g3 –> g1 –>)*  ….

จะเห็นว่ามี loop g2 –> g3 –> g1 วนซ้ำไปมา เราสามารถคิดเงินรวมได้เป็น hist[2] + hist[3] + hist[1] และการวนนี้ใช้เวลา 3 รอบ

ถ้าเรารู้ว่าในการเล่นเครื่องเล่น r รอบมันมีการวนแบบนี้เกิดขึ้นกี่ครั้ง ก็เอาจำนวนรอบมาคูณค่าเล่นรวมได้เลย จะลดการคำนวณไปได้มากเลยทีเดียว เพราะบางเคสมันเล่นตั้ง 10^8 รอบ

ข้อนี้โค้ดผมยาวและซับซ้อนผิด concept มาก - -‘ ปัญหาหลักเกิดจากการเลือกใช้ data structure ไม่ถูกต้อง ผมดันไปใช้เป็น linked structure แบบที่เห็นด้านบน ทำให้ทั้งการหา loop อะไรมันทำยากไปหมด ทั้งๆที่มันทำเป็น list ธรรมดาก็ได้แล้ว

จากเท่าที่แอบไปดูโค้ดเพื่อนบ้านมา ผมชอบคำตอบข้อนี้ของ nattster เขียนอ่านเข้าใจง่ายดี กระชับ สั้น (Python) เป็นตัวอย่างในการเรียนรู้ที่ดี (ส่วนโค้ดยาวๆของผมอยู่ที่นี่ )

ว่าด้วย Big Integer

ข้อสองดักคอคนเขียน C++ สุดๆ เพราะ input/output มันเกิน range ของ int, long ไปเยอะมากๆๆ (10^50)

หลังจากไปไล่อ่านโค้ดเพื่อนบ้านมาว่าแต่ละคนแก้ปัญหายังไง เพื่อนบ้านเขียนกันหลายภาษามาก Python, Ruby, C#, C++, Java, Scala, .. ได้ข้อสรุปว่า

• Python - ไม่ต้องทำอะไร เด๋วมันเพิ่มขนาดให้เอง
• C/C++ – ปกติใครๆในอินเทอร์เน็ตก็จะแนะนำให้ใช้ GNU MP (GMP - http://gmplib.org/) แต่เชื่อว่าหลายคนเห็นว่าเป็น GNU ก็คงไม่อยากยุ่งด้วยแล้ว ด้วยความชันของการเรียนรู้เพื่อใช้งาน (ผมคนนึงล่ะ) แล้วก็มีคนใช้ http://mattmccutchen.net/bigint/ ผมว่า lib มันดูใช้ง่ายน่าใช้มากเลยอ่ะ บางคนก็เคยเขียน big num ไว้ใช้เอง (จริงๆ)
• Java – BigInteger!
• C# - เข้าใจว่า pre 4.0 ยังต้องหา lib ข้างนอกมาใช้เอง ส่วนถ้า 4.0+ (Visual Studio 2010) มี System.Numerics.BigInteger ให้ใช้ (พร้อมเมธอด GreatestCommonDivisor) เฉพาะเรื่องนี้ตามหลัง Java ไม่รู้กี่ปี 555+

ส่วนตัวรู้สึกสอบรอบนี้ โจทย์เน้นหนักไปทางคนที่ถนัดคิดแบบ verbally ซะเป็นส่วนใหญ่ (คือคนที่คิดเป็นข้อความ คำพูด พวกตรีโกณมิติ พีชคณิต ทฏษฏีจำนวน) คนที่ถนัดคิดแบบ visually จะเสียเปรียบ

Code Jam 2010 participants from Thailand http://www.go-hero.net/jam/10/regions/Thailand

ใครมีอะไรมาแชร์ คอมเม็นต์มาโลดด~

General google, code jam, algorithm, python

สรุปว่า Round 1 ปีนี้ทำถูกจริงๆและได้คะแนนแค่ 1 ข้อครับ =_=’  แล้วก็มีอีกข้อที่ถ้าส่งทันน่าจะผ่าน 1B ไปแล้ว ต้องยอมรับว่ายังอ่อนซ้อม Python อยู่มาก ไปหาวิธีดีบักที่ไหนมาก็เจอแต่เรื่อง pdb   จริงๆผมอยากได้หน้าต่าง immediate, watch แบบ Visual Studio อ่ะ ตอนแข่งนี่ก็เลยใช้ VIM + printf debugging กว่าจะหาสาเหตุแต่ละอย่างเจอก็เหนื่อย แถมเจอแล้วเป็นเรื่องผิดแบบโง่ๆอีก +_+ อาทิเช่นลืมหารตอนสุดท้าย หรือว่า copy input file มาไม่ครบ

สิ่งที่ได้มามากที่สุดก็คงเป็นเรื่อง Python ที่รู้จักเยอะขึ้นในหลายแง่มุม ภาษามันเหมาะกับการเอามาเขียนอัลกอซับซ้อนมากเลยนะ เพราะเขียนแล้วอ่านง่าย บางคนถึงกับยกให้เป็น Executable pseudo code เลยทีเดียว จนบางทีผมรู้สึกว่าพอเอามาใช้เขียนพวก Web App ง่ายๆแล้วมันจะได้ใช้ “ข้อดี” ของภาษานี้อย่างเต็มที่รึเปล่า ??

พรุ่งนี้รอบ 4 โมงเย็นคงไม่ได้เล่นเพราะต้องไปเที่ยว โอกาสผ่านเข้ารอบนี้น่าจะสูงเพราะพวกเคี่ยวๆก็ผ่านไปใน 1A กับ 1B หมดแล้ว ปีหน้าเจอกันใหม่ฮะ สวัสดีคุณโค้ดแยม =)

ปล. รอบ Qualify นี่สนุกสุดแล้ว

General code jam, google, algorithm, python

ยังคงคอนเซ็ปต์เดิม ว่าต้อง “แยม” ไม่ใช่ “แจม” (ผมอยากกวนตรีนราชบัณฑิตอ่ะ ไม่มีไรหรอก - -‘’)

ปีก่อนลุยด้วย C# ปีนี้ลุยด้วย Python แทนครับ ผมชอบความเรียบง่ายของภาษานะ แต่ตอนนี้ติดอยู่ที่ไม่รู้จะ Debug ยังไงให้มันง่ายๆ อยากให้เหมือน C# แบบที่พอ Break แล้วจะพิมพ์โค้ดอะไรเข้าไปทดสอบ (ในหน้าต่าง Immediate) ก็ได้ ใครรู้บอกที

Alien Language

ข้อแรกค่อนข้างง่ายครับ ส่วนที่เสียเวลาน่าจะเป็นตอนพยายาม break ตัว input ที่เค้าให้มาเป็นส่วนๆ ผมลองผิดลองถูกกับ regex อยู่นานเหมือนกัน หลังจาก break ได้แล้วทุกอย่างก็ตรงไปตรงมา คือตัดตัวที่เป็นไปไม่ได้ออกจาก dict ไปเรื่อยๆ

Edit: แอบไปดูโค้ดรุจมา ใช้วิธีเปลี่ยน ( กับ ) เป็น [ กับ ] แล้ว treat as regex เลย … อึ้ง

import re

if __name__ == '__main__':
    #in_filename = "A-small.in"
    #in_filename = "A-dummy.in"
    in_filename = "A-large.in"
    #out_filename = "A-small.out"
    out_filename = "A-large.out"
    
    in_file = open(in_filename, 'r')
    out_file = open(out_filename, 'w')

    L,D,num_cases  = [int(x) for x in in_file.readline().split(' ')]

    # Read the dictionary
    words = []    
    for i in range(0,D):
        words.append(in_file.readline())
    
    
    for c in range(0,num_cases):
        # Clone a list
        ws = words[:]
        s = in_file.readline()
        clues = re.findall('(\([a-z]+\)|[a-z])',s)
        #print clues
        for k in range(0,len(clues)):
            ws = filter(lambda x: clues[k].find(x[k]) != -1, ws)
        out_file.write("Case #%d: %d\n" % (c+1, len(ws)))

    out_file.close()

Watersheds

ผมคิดว่าข้อนี้ยากที่สุดสำหรับปีนี้แล้ว โจทย์มันคล้ายๆกับการเทสีใน Paint คือจะใช้ floodfill ทำก็ได้ (มีตัวอย่างโค้ด Floodfill ภาษา Java ที่บลอกภาษาอังกฤษ)  หรือใช้วิธีอื่นก็ได้ อย่างที่ทำครั้งนี้เป็นการแสกนดูก่อนว่าจุดไหนบนแผนที่เป็นกลุ่มเดียวกันบ้าง (คล้ายๆเรื่อง Disjoint Set) แล้วค่อยทำการ Assign ตัวอักษรให้ใหม่ โปรแกรมนี้เขียนเละๆ และดีบักนานมากกก อาจจะเพราะไม่ได้เขียนนานแล้วแล้วก็ยังไม่ค่อยคุ้นกับวิธี Debug ใน Python ด้วย ใช้ “Printf Debugging” ตลอด ฮะๆ

import re
import sys

if __name__ == '__main__':
    #in_filename = "B-small.in"
    #in_filename = "B-dummy.in"
    in_filename = "B-large.in"
    #out_filename = "B-small.out"
    out_filename = "B-large.out"
    
    in_file = open(in_filename, 'r')
    out_file = open(out_filename, 'w')

    num_cases = int(in_file.readline())
    for c in range(0,num_cases):
        H,W = [int(x) for x in in_file.readline().split(' ')]
        map = []
        for h in range(0,H):
            map = map + [int(x) for x in in_file.readline().split(' ')]
        label = range(0,H*W)
        assoc = [-1]*H*W 
        
        for h in range(0,H):
            for w in range(0,W):
                cursor = h*W + w
                min = sys.maxint
                way = -1
                
                pos1 = (h-1)*W + w
                if h != 0 and map[pos1] < min:
                    min = map[pos1]
                    way = 1

                pos2 = h*W + w - 1
                if w != 0 and map[pos2] < min:
                    min = map[pos2]
                    way = 2

                pos3 = h*W + w + 1
                if (w + 1) < W and map[pos3] < min:
                    min = map[pos3]
                    way = 3

                pos4 = (h + 1)*W + w
                if (h + 1) < H and map[pos4] < min:
                    min = map[pos4]
                    way = 4
                
                # If is Sink
                if min < map[cursor]:
                    if way == 1:
                        assoc[label[cursor]] = label[pos1]
                    elif way == 2:
                        assoc[label[cursor]] = label[pos2]
                    elif way == 3:
                        assoc[label[cursor]] = label[pos3]
                    elif way == 4:
                        assoc[label[cursor]] = label[pos4]

        # Do paths compression
        #print "Before", assoc
        for ind in range(0,len(assoc)):
            next = assoc[ind]
            last = next
            while next != -1:
                last = next
                next = assoc[next]
            assoc[ind] = last 
        #print "Compress", assoc

        # Final relabel
        out_file.write("Case #%d:\n" % (c+1))
        char_map = {}
        running = ord('a') 
        for h in range(0,H):
            for w in range(0,W):
                cursor = h*W + w
                if assoc[label[cursor]] != -1:
                    label[cursor] = assoc[label[cursor]]
                if label[cursor] not in char_map:
                    char_map[label[cursor]] = running
                    running = running + 1
                
            #print label[h*W:h*W + W]
            out_file.write(' '.join([chr(char_map[x]) for x in label[h*W:h*W + W]]))
            out_file.write('\n')


    out_file.close()

ดูเหมือนอันนี้จะง่ายกว่าข้อสอง ใช้ Dynamic Programming แก้ เป็นตารางขนาด len(‘welcome to code jam’) x len({text}) แต่ละแถวคือจำนวนคำตอบที่จบด้วยตัวอักษรที่คู่กับแถวนั้น  ปกติพวกโค้ด DP จะอ่านไม่ค่อยรู้เรื่องอยู่แล้วเพราะมันเป็นการเอาความสัมพันธ์เวียนเกิด (Recursion) ใน math มาเปลี่ยนเป็นโค้ด o__o’’

เข้าใจว่าข้อนี้ถ้าแก้ด้วย Brute force ก็น่าจะทันเวลา (ล่ะมั้ง) วิเคราะห์ไม่เป็นแล้ว :-o

Edit: คะแนนออกแล้วปรากฎว่า ลืมไปบรรทัดนึง ตรง answer = reduce( …. ต้องเปลี่ยนเป็น answer = reduce(..) % 10000 สะเพร่าเสมอต้นเสมอปลาย - -‘’

w, e, l, c, o, m, e,  , c, o, d, e,  , t, o,  , c, o, d, e,  , j, a, m,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0
0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 2, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 0
0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 2, 0, 0, 2, 0, 0, 0, 0, 3, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 6, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0

import re
import sys

if __name__ == '__main__':
    #in_filename = "C-small.in"
    #in_filename = "C-dummy.in"
    in_filename = "C-large.in"
    #out_filename = "C-small.out"
    out_filename = "C-large.out"
    
    in_file = open(in_filename, 'r')
    out_file = open(out_filename, 'w')

    num_cases = int(in_file.readline())
    for case in range(0,num_cases):
        text = in_file.readline()
        sen = "welcome to code jam"
        W = len(text)
        H = len(sen)
        tab = [0]*W*H
        for r in range(0,H):
            sum = 0
            for c in range(0,W):
                cursor = r*W + c
                if r == 0 and text[c] == sen[0]:
                    tab[cursor] = 1
                else:
                    sum = (sum + tab[(r-1)*W + c]) % 10000
                    if text[c] == sen[r]:
                        tab[cursor] = sum
            #print tab[r*W:r*W+W]

        # Sum last row
        answer = reduce(lambda x,y: x + y, tab[(H-1)*W:H*W])
        print "Case #%d ..." % (case + 1)
        out_file.write("Case #%d: %04d\n" % ((case+1), answer))
        #print '-'*80
    out_file.close()

เมื่อคืนนอนเร็วมากด้วยความอ่อนเพลีย เลยได้ตื่นมาเล่นตั้งแต่ 6 โมงเช้าครับ เขียนไปเรื่อยๆจน 9 โมง ติดข้อสองนานมากกกก

ปีนี้รู้สึกไม่ค่อยมีคน Active มาเล่นด้วยเท่าไหร่ คนรุ่นเดียวกันสงสัยจะทำงานไม่มีเวลาว่างกลับมาก็เหนื่อยแล้วล่ะมั้ง วันนี้ระหว่างวันก็ไม่ได้ยุ่งกับ Code Jam ได้แต่เปิด Score board มามองตาปริบๆ แล้วก็แอบๆทดเลขลงกระดาษไปพลางๆ พอดีวันนี้งานเข้าซะด้วย ฮือๆ รู้สึกนายแท็ปก็จะคล้ายๆกัน

ครั้งนี้ได้ใช้ Python คล่องมือขึ้นเยอะ (แต่ยังไม่รู้จะเอาไปทำอะไรดี .. อ้ะ) มีอะไรแนะนำผมคอมเม็นต์มาได้เลยนะครับ ^ ^ ยังเป็นมือใหม่อยู่ เพื่อนๆที่ทำด้วยกันลองเอาโค้ดขึ้นบลอกมาแบ่งกันดูด้วยก็ดี อยากเห็นวิธีของคนรอบตัวมากกว่าอยากเห็นวิธีของฝรั่ง/คนจีนในเน็ต : )

Edit: มีคนทักเรื่อง DP มาเยอะ (สองคนถ้วน o__o) จริงๆแล้วส่วนใหญ่โจทย์ที่เป็น DP ส่วนใหญ่มันจะ

• เป็นโจทย์พวก Optimization เช่นหาน้อยที่สุด แพงที่สุด จำนวนมากที่สุด ระยะทางสั้นสุด
• เป็นโจทย์ที่คำตอบของปัญหาใหญ่ๆมักจะคำนวณได้จากปัญหาเล็กๆ เช่น factorial, fibonacci, …
• เวลาไม่รู้จะทำยังไงแล้ว (ฮ่าๆ)

อย่างข้อ 3 นี่ สมมติว่าให้ text มาเป็นคำว่า “d d o o o g d d” และให้หาคำว่า “d o g”

• แถวแรก (คู่กับตัว d) จะแทนจำนวน seq ที่เป็นไปได้ที่ลงท้ายด้วยตัว d นั่นก็คือตำแหน่งที่เป็นตัว d จะเป็น 1 ส่วนที่อื่นเป็น 0
  ได้ 1 1 0 0 0 0 1 1
• แถวที่สอง (คู่กับตัว o) เป็นจำนวน seq ที่ลงท้ายด้วย o คือ “d o” ช่องที่จะเป็นไปได้ก็คือช่องที่เป็นตัว o เท่านั้น แต่จะมีจำนวนเท่าไหร่ก็ขึ้นกับว่าก่อนหน้าตัวมันเองมี seq “d” ให้ใช้ทั้งหมดกี่อัน ทำได้โดยการเอาแถวข้างบนบวกกันจนถึงตัวมันเอง
  ได้ 0 0 2 2 2 0 0 0
• แถวที่สาม (คู่กับตัว g) ทำแบบเดียวกับแถวสอง คือเติมเฉพาะช่องที่เป็น g และนับจำนวน seq ก่อนหน้าที่เป็น “d o”
  ได้ 0 0 0 0 0 6 0 0
• เอาแถวสุดท้าย sum ทั้งแถว ได้จำนวนรูปแบบทั้งหมดที่เป็นไปได้

General google, code jam, algorithm, python

ในบรรดาโจทย์ปี 2008 คิดว่าข้อนี้น่าจะยากที่สุดครับ แอบเถื่อนนิดหน่อยตรงที่มันใช้ Math พอสมควร ใจความหลักของโจทย์ข้อนี้คือ “จะหาพื้นที่ที่ตัดกันระหว่างวงกลมกับสี่เหลี่ยมได้ยังไง” ซึ่งมันก็มีหลายวิธี

• ทำ Computer Integration วิธีนี้ผมใช้ตอนปีก่อน อารมณ์ประมาณซอยเป็นสี่เหลี่ยมคางหมูหลายๆอันให้ถี่ๆ ก็จะใช้ประมาณพื้นที่ได้ โจทย์บอกว่าคำตอบต้องละเอียดถึง 1e-6 ก็ต้องแบ่งให้ถี่ๆแบบสัมพันธ์หน่อย เหมือนวิธีนี้จะเรียกผลรวมรีมันด์อะไรซักอย่าง จำไม่ได้ล่ะ (ได้แคลคูลัส C)
• ทำ Integrate รูปปิด ประมาณว่าหาสูตรคำนวณพื้นที่นั่นเอง หลังจากนั้นก็เอาขอบเขตมาแทนค่าพร้อมกับตัดเติมลบอีกนิดหน่อย ก็จะได้พื้นที่ออกมาเลย การ Integrate สมการวงกลม (x^2 + y^2 = r^2) มันทำยาก ใช้ Tool พวกที่ช่วยทำ Integrate ให้ได้ แล้วค่อยมาเอาแทนค่า (รายละเอียดเต็มๆเชิญกระมู้นี้)

• อีกวิธีใช้เรขาคณิตวิเคราะห์ธรรมดา! คำนวณพื้นที่ส่วนที่รู้แล้วด้วยวิธีปกติก่อน ส่วนที่มันเป็นโค้งๆก็ใช้วิธีการหาพื้นที่ของ segment แล้วลบออกด้วยพื้นที่สามเปลี่ยม ก็จะได้เฉพาะพื้นที่ส่วนที่เป็นโค้งๆสีเหลือง เอามาคำนวณต่อได้ ครั้งนี้ใช้วิธีนี้

ไปที่โค้ด Python  ขอสารภาพว่าดีบั๊กอยู่นานพอควร ไม่รู้ตอนสอบปีก่อนรอด Large test case ข้อนี้มาได้ไง ><’’
โค้ดน่าเกลียดไปหน่อย ซ้อนกันหลายบล็อคเกิน

import math

def calculate_segment(R,x1,y1,x2,y2):
    ang1 = math.atan(y1/x1)
    ang2 = math.atan(y2/x2)
    ang = math.fabs(ang1 - ang2)
    area = (ang/math.pi/2)*math.pi*R**2
    cord = math.sqrt((x1-x2)**2 + (y1-y2)**2)
    pie = math.cos(ang/2)*R*cord/2
    return area - pie

if __name__ == '__main__':
    #in_filename = "C-small-practice.in"
    #in_filename = "C-dummy.in"
    in_filename = "C-large-practice.in"
    #out_filename = "C-small.out"
    out_filename = "C-large.out"
    
    in_file = open(in_filename, 'r')
    num_cases = int(in_file.readline())
    out_file = open(out_filename, 'w')

    for c in range(0,num_cases):
        f, R, t, r, g = [float(x) for x in in_file.readline().split(' ')]
        r = r + f
        g = g - 2*f
        t = t + f
        x1 = r
        y1 = r
        
        # Is the interested point inside the circle
        is_inside = lambda x,y : (x**2 + y**2) <= (R-t)**2
        
        # Get y from x, or get x from y
        get_pair = lambda x : math.sqrt((R-t)**2 - x**2)

        if g > 0.0:
            area = 0.0
            while x1 <= R-t:
                while y1 <= R-t:
                    x2 = x1 + g
                    y2 = y1 + g
                    if is_inside(x1,y1):
                        if is_inside(x2,y2):
                            # Full rectangle is inside
                            area = area + (x2-x1)*(y2-y1)
                        else:
                            x1_y2_in = is_inside(x1,y2)
                            x2_y1_in = is_inside(x2,y1)
                            if x1_y2_in and x2_y1_in:
                                xt = get_pair(y2)
                                yt = get_pair(x2)
                                area = area + (x2-x1)*(y2-y1)
                                area = area - (x2-xt)*(y2-yt)/2
                                area = area + calculate_segment(R-t,xt,y2,x2,yt)
                            elif x1_y2_in and not x2_y1_in:
                                xt2 = get_pair(y2)
                                xt1 = get_pair(y1)
                                area = area + (xt2 + xt1 - 2*x1)*(y2-y1)/2
                                area = area + calculate_segment(R-t,xt2,y2,xt1,y1)
                            elif not x1_y2_in and x2_y1_in:
                                yt1 = get_pair(x1)
                                yt2 = get_pair(x2)
                                area = area + (yt1 + yt2 - 2*y1)*(x2-x1)/2
                                area = area + calculate_segment(R-t,x1,yt1,x2,yt2)
                            else:
                                yt = get_pair(x1)
                                xt = get_pair(y1)
                                area = area + (yt-y1)*(xt-x1)/2
                                area = area + calculate_segment(R-t,x1,yt,xt,y1)
                    y1 = y1 + g + 2*r
                x1 = x1 + g + 2*r
                y1 = r
            all_area = math.pi*R*R/4
            prob = (all_area - area)/all_area
        else:
            prob = 1.0
        out_file.write("Case #%d: %f\n" % (c+1, prob))

    out_file.close()

General google, code jam, python, math

ครั้งก่อน Feedback ไม่ค่อยดี (จริงๆแล้วไม่มี feedback - -‘’) เลยตัดสินใจเลิกเขียนอธิบายดีกว่า เมื่อยตุ้ม 55+

โจทย์ที่นี่ (Qualification Round 2008)

จุดเน้น : ข้อนี้มันออกแนวๆ Simulation มากกว่านะ คือจำลองเหตุการณ์ตามที่กำหนดให้ไปเรื่อยๆ แล้วบันทึกค่าไว้เป็นคำตอบ โค้ดไม่ยาวเท่าไหร่ แต่ดีบักอยู่หลายชม. ไม่เคยเขียนนี่หว่า - -‘ จบข้อนี้ได้ความรู้ Python ใหม่ๆ ได้แก่

• ลองใช้ List Comprehension เพิ่มเติม
• ลองใช้ Lambda กับ map, filter, reduce และ list.sort

class Event(object):
    def __init__(self):
        # Time in seconds
        self.time = 0
        # Offset to apply to train count
        self.offset = (0,0)

if __name__ == '__main__':
    #in_filename = "B-small-practice.in"
    in_filename = "B-large-practice.in"
    #out_filename = "B-small.out"
    out_filename = "B-large.out"
    
    in_file = open(in_filename, 'r')
    num_cases = int(in_file.readline())
    out_file = open(out_filename, 'w')

    for c in range(0,num_cases):
        turnaround = int(in_file.readline())
        from_a, from_b = [int(x) for x in in_file.readline().split(' ')]
        actions = []

        for a in range(0,from_a):
            # Get departure/arrival time in minutes
            depart, arrive = [reduce(lambda h,m : h*60 + m,[ int(y) for y in x.split(':') ]) for x in in_file.readline().split(' ')]
            # Departure event : A--
            ev = Event()
            ev.time = depart
            ev.offset = -1,0
            actions.append(ev)

            # Ready for next departure : B++
            ev = Event()
            ev.time = arrive + turnaround
            ev.offset = 0,1
            actions.append(ev)

        for b in range(0,from_b):
            # Get departure/arrival time in minutes
            depart, arrive = [reduce(lambda h,m : h*60 + m,[ int(y) for y in x.split(':') ]) for x in in_file.readline().split(' ')]

            # Departure event : B--
            ev = Event()
            ev.time = depart
            ev.offset = 0,-1
            actions.append(ev)

            # Ready for next departure : A++
            ev = Event()
            ev.time = arrive + turnaround
            ev.offset = 1,0
            actions.append(ev)
        
        # Sort the events by their times
        actions.sort(cmp=lambda x,y : cmp(x.time,y.time))

        train_count_a, train_count_b = 0,0
        lowest_a, lowest_b = 0,0
        last_time = None

        for act in actions:
            if last_time != act.time:
                # Only track the lowest values when all events
                # at the same time are all processed
                lowest_a = min(lowest_a, train_count_a)
                lowest_b = min(lowest_b, train_count_b)
                last_time = act.time

            #print act.time,act.offset

            train_count_a = train_count_a + act.offset[0]
            train_count_b = train_count_b + act.offset[1]

        #l = raw_input("pause ..")

        out_file.write("Case #%d: %d %d\n" % (c+1,lowest_a*-1, lowest_b*-1))

    out_file.close()

General algorithm, google, code jam

ช่วงนี้กำลังคลั่งไคล้ Python ครับ แต่ถ้าคลั่งไคล้อย่างเดียวแต่ไม่ได้ทำแลบเปียกเลยก็คงเขียนไม่คล่องซักที เลยลองเอา Python ไปทำโจทย์เก่าที่เคยทำด้วย C# ของ Google Code Jam ปีที่แล้วดู ทำเสร็จแล้วดองไว้ที่บ้านก็ไม่ดี เอามาเฉลยดีกว่า เผื่อใครอยากลองแข่งปีนี้ (รอบ QR วันที่ 2 กันยายน 2009)

โจทย์ข้อนี้มาจาก Qualification Round 2008 โดยย่อ โจทย์จะให้รายชื่อ Search Engine มาทั้งหมด S อัน และคำค้นหาอีก Q อัน คำค้นหาจะถูกประมวลผลเรียงตามลำดับที่ได้รับเข้ามา โดยในเวลาใดเวลาหนึ่งจะมี Search Engine ทำงานอยู่ได้เพียงตัวเดียว

ถ้าคำค้นหาตรงกับชื่อ Search Engine จะทำให้ Search Engine ระเบิด! ดังนั้นจึงอนุญาตให้ “สลับ” Search Engine จากตัวหนึ่งไปอีกตัวหนึ่งได้ คำถามคือ จากรายชื่อ SE และคำค้นหาที่ให้มา จำเป็นจะต้องใช้การสลับอย่างน้อยสุดกี่ครั้ง จึงจะประมวลผลการค้นหาทั้งหมดได้

ตัวอย่าง

มี SE

• Googol Vietnam
• Googol Jersey
• Googol Ethiopi

มีคำค้นหา

• Googol Jersey
• Googol Vietnam
• Googol Jersey
• Googol Jersey
• Googol Jersey
• Googol Jersey
• Googol Ethiopia
• Googol Ethiopia
• Googol Ethiopia
• Googol Ethiopia
• Googol Vietnam
• Googol Ethiopi

ตอบ 1 ครั้ง

เฉลย

ข้อนี้แก้ได้ด้วยวิธีแบบ Greedy ครับ คำอธิบายยาวๆลองไปดู E-learning ของอาจารย์สมชาย แล้วกัน :)

แต่สั้นๆคือ “ทำอะไรที่เห็นตรงหน้าให้ดีที่สุดไว้ก่อน”

ข้อนี้ก็เริ่มจากการหา Search Engine ที่จะ process query ได้เยอะที่สุดโดยไม่ต้องสลับ ซึ่งก็หาได้โดยดู query จากต้นไปเรื่อยๆ จนกว่าจะพบ query ที่เป็นชื่อ Search Engine ครบหมดทุกตัว ตัวสุดท้ายที่พบ (ตัวที่ทำให้บรรลุเงื่อนไข “พบหมดทุกตัว”) จะเป็น Search Engine ตัวที่ทำให้ process query ได้เยอะที่สุดตัวแรก ซึ่งก่อนที่จะ process query อันสุดท้ายนี้ เราจำเป็นอย่างหลีกเลี่ยงไมได้ ต้องทำการ “สลับ” เสียก่อน หลังจากสลับแล้ว query อันสุดท้ายนี้ก็จะนับเป็น Search Engine ที่เราได้ “พบ” แล้วอีกตัวหนึ่ง ก่อนที่จะทำการมอง query ต่อไปเรื่อยๆจนจบ

ประเด็นที่น่าจะยากสำหรับมือใหม่คือการเช็คว่า “พบ Search Engine ครบทุกตัว” แล้วหรือยัง ??

วิธีที่ผมใช้คือเอาชื่อ Search Engine ใส่พวก Map/Dictionary แล้วตอนได้รับ Query มาก็ตรวจดูว่ามี key อันนี้แล้วหรือยัง ถ้ามี และยังไม่เคยพบ ก็จะเซ็ตให้เป็น True (แปลว่าพบ) แล้วก็ใช้ counter อีกตัวนึงคอยนับว่าเจอครบทุกตัวแล้วหรือยัง

โค้ดใน Python ตามนี้

if __name__ == '__main__':
    filename = "A-small-practice.in"
    filename = "A-large-practice.in"
    out_filename = "A-small.out"
    out_filename = "A-large.out"
    file = open(filename, 'r')
    num_cases = int(file.readline())
    out_file = open(out_filename, 'w')
    for c in range(0,num_cases):
        
        # For each case
        num_switch = 0
        
        # To check for dupplicate search engine names
        dict = {}

        num_engine = int(file.readline())
        found_engine = 0
        for e in range(0,num_engine):
            engine = file.readline()
            dict[engine] = False

        num_q = int(file.readline())
        for q in range(0,num_q):
            query = file.readline()
            if dict.has_key(query):
                if dict[query] == False:
                    found_engine = found_engine + 1
                dict[query] = True

            # Check if there is no possibility of not switching
            # all search engines are used up
            if found_engine == num_engine:
                num_switch = num_switch + 1
                found_engine = 1
                for (k,v) in dict.items():
                    if query != k:
                        dict[k] = False
            
        out_file.write("Case #%d: %d\n" % (c+1, num_switch))

    out_file.close()

ครั้งนี้เหมือนโยนหินถามทางครับ~

ถ้า Feed back ดีอาจมีตอนต่อ :)

General google, code jam, algorithm, python

ไปแอบอ่านมานิดหน่อยครับ เค้าว่าเป็นแนวปฎิบัติที่ใช้กันใน Google คนเขียน C++ ลองไปอ่านดู

Google C++ Style Guide

เรื่องที่น่าสังเกตหลังอ่านเรื่องหนึ่งคือ “Do not use Hungarian notation” ตอนสมัยผมสนใจ C++ ใหม่ๆ เมื่อนานมากแล้วสมัย VB6 กำลัง Boom จำได้ว่าเค้า Encourage นักหนา ให้เอา prefix แปลกๆมานำหน้าชื่อตัวแปล ไม่ว่าจะเป็น lpstrXxxx, szXxxx, hWndXxxx, … blah blah อ่านทีนึงแทบจะเป็นลม ประกอบกับตอนนั้นอ่าน Code C++ ที่ใช้สร้างหน้าต่างโง่ๆมาอันนึง ไม่มีอะไรเลย ใช้ Code ประมาณ 60 บรรทัด (มารู้ตอนแก่ว่ามันคือการใช้ Win32 API ล้วนๆ) แต่ VB6 แค่ New Project ก็เสร็จแล้ว ทำให้ตอนนั้นผมเลิกสนใจ C++ ไปเลย

กลับมาเรื่อง Hungarian Notation ชื่อตัวแปรที่ Google แนะนำให้ตั้งจะเป็นแบบ lower case หมด แล้วใช้ underscore คั่นระหว่างคำแทน ก็ดูอ่านง่ายดี เหมือนภาษา C

How to Name

Give as descriptive a name as possible, within reason. Do not worry about saving horizontal space as it is far more important to make your code immediately understandable by a new reader. Examples of well-chosen names:

int num_errors;                  // Good.
int num_completed_connections;   // Good.

Poorly-chosen names use ambiguous abbreviations or arbitrary characters that do not convey meaning:

int n;                           // Bad - meaningless.
int nerr;                        // Bad - ambiguous abbreviation.
int n_comp_conns;                // Bad - ambiguous abbreviation.

Type and variable names should typically be nouns: e.g., FileOpener, num_errors.

Function names should typically be imperative (that is they should be commands): e.g., OpenFile(), set_num_errors(). There is an exception for accessors, which, described more completely in Function Names, should be named the same as the variable they access.

จริงๆแล้วภาษา C++ มันเปิดมาก เปิดจนมีวิธีการหลายอย่างในการทำเรื่องๆเดียว ตัวเลือกก็เลยมีมากมาย เอาโค้ดคนอื่นมาทำต่อก็เลยต้องใช้เวลาหน่อย มีเรื่องน่าสนใจอีกหลายอย่างเกี่ยวกับการเลือกแนวปฎิบัติของ Google ลองไปอ่านกันดู :)

Native google, c++, convention

เจ๋งดีครับ ลองเล่นแล้วชอบมาก

ทำให้รักเจ้า Windows Mobile Samsung มากขึ้นอีกเป็นกอง เพราะมัน synchronize กับ google calendar ได้แล้ว

พร้อมกันนี้ก็สมัคร EDGE/GPRS Package 5hr ราคาประมาณ 50 บาทไปแล้วด้วย (ใช้ได้ 30 วัน)

ปล. จริงๆโพสต์นี้จะทดสอบ Windows Live Writer กับ BlogEngine.NET ครับ สรุปได้คำเดียวว่าสุดยอดมาก

General google, gadget

ผมเริ่มเขียนบลอกภาษาอังกฤษมาตั้งแต่ประมาณปลายปี 2006 จุดประสงค์ที่เขียนก็ไม่มีอะไรมากไปกว่าการเขียนเพื่อฝึกภาษาอังกฤษ และคิดว่าความรู้หรือปัญหาที่เจอมาบางอย่างเขียนพ่นใส่บลอกภาษาไทยไปก็คงไม่เกิดประโยชน์อะไร ใครจะเข้ามาอ่านวะ? (ยกเว้นบางเรื่องที่มันทั่วๆไปมาก คิดว่าเขียนแล้วยังมีคนค้นมาเจอบ้าง) เขียนเป็นภาษาอังกฤษอย่างน้อยก็น่าจะมีคนเข้ามาเจอบ้าง ตั้งแต่ตอนนั้นถึงตอนนี้ผมคิดว่าการเขียนบลอกช่วยผมในเรื่องภาษาอังกฤษได้มากๆเลย ยิ่งช่วงนี้มีสอบสัมภาษณ์เข้าทำงาน ผมคิดว่าผมพูดเรื่องใน Technical Domain ได้โอเคมากๆ ไม่นับเรื่องทั่วๆไปนะ แหะๆ

ประโยชน์แอบแฝงของบลอกภาษาอังกฤษที่ว่านี่คือ ผมเอาโฆษณาไปแปะเพื่อสร้างรายได้เล็กๆได้ มันคือ Google Adsense นั่นเอง ผมเริ่มแปะมาตั้งแต่เดือนสิงหาคม 2007 แต่ยอดเงินเพิ่งแตะ 100 USD เมื่อเดือนพฤศจิกายน 2008 ที่ผ่านมานี่เอง รวมระยะเวลา 1 ปี และ 3 เดือน การแปะโฆษณาก็ช่วยให้ผมมีกำลังใจในการเข้าไปเพิ่มบทความเรื่อยๆมากขึ้น บางครั้งก็เสียเวลาหมกมุ่นกับการไปอ่านบอร์ดชุมชนเช่น ThaiSEOBoard บ้าง แต่พวกนั้นเป็นพวกทำกันเป็นอาชีพจริงๆ ซึ่งผมก็คิดว่างานพวก Online Marketing ก็เป็นแหล่งทำเงินที่ดีไม่น้อยเลย

และในที่สุด เช็คจาก Google ก็เดินทางมาถึงบ้านเมื่อวันที่ 5 มกราคม 2009 หากคิดว่าแปะเล่นๆไม่ต้องทำอะไรมาก แล้วได้ค่าขนมกินเล่นปีละประมาณ 3500 บาท ผมว่ามันไม่เลวเลยนะ

รูปต่อไปนี้ ก็เอามาโม้ ยั่วกิเลส รวมถึงเอามาเป็นกำลังใจให้คนที่ยอดยังไม่ถึง และช่วยคอนเฟิร์มให้ครับว่า Google มันจ่ายจริง :) เป็นความภูมิใจเล็ก เล็ก เล็ก ของผมกับรายได้ออนไลน์ก้อนแรกครับ (ก้อนใหม่แตะ USD 20 แล้ว)

สามารถเข้าไปเช็ค Tracking Number ได้จากหน้า Payment ครับ

เอาไปเช็คกับไปรษณีย์ไทยได้ด้วยว่าถึงผู้รับรึยัง ไม่เคยคิดเลยว่าบริการไปรษณีย์มันเทพขนาดนี้!

เช็คถึงมือครับ เป็นของ Citibank เอาไปขึ้นกับธนาคารอะไรก็ได้ที่เรามีบัญชี และชื่อภาษาอังกฤษตรงกับในเช็ค (สำคัญนะ)

General google, adsense, bank

หลังจากผ่านรอบ Qualify และ Round 1C มาได้ ก็ถึง Round 2 ครับ

รอบนี้มีเวลาแข่ง 2 ชม. กับ โจทย์ 4 ข้อ ปรากฎว่าโจทย์แอบยาก ข้อแรกโผล่มาก็เป็นเรื่องต้นไม้ ไม่รู้ว่าเรียนวิชา AI มากไปรึเปล่าเลยฝังใจเรื่อง Search มาก อยู่ๆก็นั่งเขียน Search ซะงั้น แต่เขียนไปได้ครึ่งทางกลับไม่รู้จะทำยังไงต่อ (ดังนั้นจงคิดในจบก่อนเขียนอะไรก็ตามนะครับ - -')  มานั่งคิดๆให้ดีตอนหลัง มันใช้ Dynamic Programming ได้นี่นา ก็เลยลุยลบเขียนใหม่อีกรอบ ก็แก้ small ได้ และค่อนข้างมั่นใจกับ large

ส่วนเวลาที่เหลือประมาณ 50 นาที เอาไปทำข้อ D ซึ่งก็ใกล้ออกเต็มทีแล้วล่ะ คิดว่ามันเป็นการหามัธยฐานแล้วก็หากึ่งกลางแบบถ่วงน้ำหนัก แต่ทำไม่ทันแฮะ เสียดายเหลือเกิน

สรุปผลออกมาได้ที่ 1236 ครับ 15 คะแนน (A-small + A-large) ตกรอบไปตามยถากรรม (รับ 1000 คน) แต่ผ่านมาได้ถึงรอบนี้ก็แอบดีใจพอสมควร เพราะงานนี้มันแข่งกันไม่จำกัดอายุ พวกโอลิมปิก, Timus ทั้งหลายทั้งปวงคงพากันยกพวกมาแข่ง ฮ่าๆ มานั่งคิดๆดู ถ้าใช้ C++ เขียนประกอบกับใช้ STL (Standard Template Library) เป็นคงเร็วกว่าที่ใช้ C# เขียนอยู่ตอนนี้เยอะเลย มันรับ Input อะไรพวกนี้ไม่ค่อยสะดวกอ่ะ แต่ก็มีข้อดีที่มี Library ให้ใช้มากกว่า ตอน sort ก็ใช้ anonymous delegate ช่วยได้ สะดวกเป็นบ้า

ขออนุญาตเอาคะแนน ตัดมาเฉพาะคนไทยที่แอดไว้แล้วก็่ได้คะแนนมากกว่าแล้วกันนะครับ :) ปีหน้าคงมีคนเล่นด้วยเยอะขึ้น ปีนี้พวกชมรมโรบอตไม่ได้แข่งเลยเพราะตรงกับไปจีน

General google, code jam, c#