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