Gcj2014

Round 1A 2014

A. Charging Chaos

Source: [1]

ชาวนา Shota มีปัญหา เขาเพิ่งจะย้ายไปที่บ้านฟาร์ม แต่ระบบปลั๊กไฟนั้นมีการติดตั้งที่ผิดพลาด เนื่องจากเขาเป็นชาวนายุคใหม่ Shota จึงมีมือถือและแลบทอปจำนวนมาก เขามีอุปกรณ์รวมทั้งสิ้น N ชิ้น

อุปกรณ์เหล่านี้มี spec ที่แตกต่างกันและทำโดยบริษัทที่แตกต่างกันด้วย อุปกรณ์เหล่านี้จึงมีความต้องการการไหลของกระแสไฟที่แตกต่างกัน ในทำนองเดียวกันปลั๊กไฟแต่ละอันก็มีการปล่อยกระแสไฟที่แตกต่างกันด้วย กระแสไฟที่ปล่องนี้ สามารถแทนได้ด้วยสตริงของ 0 และ 1 ความยาว L ตัวอักษร

Shota ต้องการที่จะชาร์ตอุปกรณ์ทั้ง N ชิ้นนี้พร้อม ๆ กัน และก็เป็นเหตุบังเอิญเลยทีเดียวที่ในบ้านก็มีปลั๊กจำนวน N อันเช่นเดียวกัน ในการปรับแต่งกระแสไฟฟ้า จะมีแป้นควบคุมที่ประกอบไปด้วยสวิตช์จำนวน L อัน สวิตช์อันที่ i จะสลับบิตที่ i ของกระแสไฟฟ้าของทุก ๆ ปลั๊กในบ้าน ยกตัวอย่างเช่น ถ้ากระแสของแต่ละปลั๊กเป็นดังนี้:

Outlet 0: 10
Outlet 1: 01
Outlet 2: 11

การสลับสวิตช์ตัวที่ 2 จะเปลี่ยนกระแสไฟฟ้าเป็น

Outlet 0: 11
Outlet 1: 00
Outlet 2: 10

ถ้า Shota มีมือถือที่ใช้กระแส "11" ในการชาร์ต, แทบเบล็ตที่ใช้กระแส "10" ในการชาร์ตและแลบทอปที่ใช้กระแส "00" ในการชาร์ต การสลับสวิชต์ที่ 2 จะทำให้เค้ามีความสุขอย่างมาก

Misaki ได้รับการว่าจ้างจาก Shota ให้ช่วยเขาแก้ปัญหา เธอได้วัดกระแสจากทุก ๆ ปลั๊กในบ้านและสังเกตว่ามันแตกต่างกันทั้งหมด ให้ตรวจสอบว่าเป็นไปได้หรือไม่ที่ Shota จะสามารถชาร์ตอุปกรณ์ทั้งหมดของเขาในเวลาเดียวกันได้หรือไม่ ถ้าเป็นไปได้ ให้หาว่าจำนวนสวิชต์ที่ต้องสลับทั้งหมดที่น้อยที่สุดเป็นเท่าใด (เนื่องจาก Misaki ไม่อยากจะเหนื่อยกดสวิชต์มากเกินความจำเป็น)

B. Full Binary Tree

Source: [2]

tree คือ connected graph ที่ไม่มี cycle

rooted tree คือ tree ที่มีจุดยอดพิเศษที่เรียกว่า root. ถ้ามีเส้นเชื่อมระหว่าง X และ Y ใน rooted tree, เราจะกล่าวว่า Y เป็นลูกของ X ถ้า X อยู่ใกล้กับ root มากกว่า Y (กล่าวคือ เส้นทางสั้นที่สุดจาก root ไปยัง X สั้นกว่าเส้นทางที่สั้นที่สุดจาก root ไปยัง Y)

full binary tree คือ rooted tree ที่ทุก ๆ จุดยอดมีลูกสองจุดยอดพอดี หรือไม่ก็ไม่มีเลย

คุณได้รับ tree G ที่มี N โหนด (เรียกเป็นโหนด 1 ถึง N) คุณจะสามารถลบบางโหนดทิ้งได้ ถ้าโหนดถูกลบทิ้ง เส้นเชื่อมทั้งหมดที่ต่อกับโหนดนั้นก็จะถูกลบไปด้วย งานของคุณคือลบโหนดให้น้อยที่สุดเพื่อโหนดที่เหลือเป็น full binary tree สำหรับบาง root ที่เลือกจากโหนดที่เหลือ

C. Proper Shuffle

Source: [3]

ลำดับการเรียงสับเปลี่ยนของ N จะมีตั้งแต่ 0 ถึง N-1 โดยเลขแต่ละตัวจะปรากฎเพียงครั้งเดียวเท่านั้น สำหรับลำดับการเรียงสับเปลี่ยนที่มีความยาว N อาจมีได้หลายรูปแบบ (ซึ่งก็มี N! ลำดับ แต่นั่นก็ไม่สำคัญสำหรับโจทย์ข้อนี้) เราอาจเลือกลำดับการเรียงสับเปลี่ยนใดๆ มาลำดับหนึ่งโดยสุ่มโดยมีโอกาสเท่าๆ กัน ที่จะหยิบได้ลำดับใดลำดับหนึ่ง

Pseudocode สำหรับอัลกอริทึมหนึ่งที่จะสร้างลำดับเรียงสับเปลี่ยน (ซึ่งจะเรียกอัลกอริทึมต่อไปนี้ว่าอัลกอริทึมที่ดี) เขียนได้ดังนี้

for k in 0 .. N-1:
 a[k] = k
 for k in 0 .. N-1:
   p = randint(k .. N-1)
   swap(a[k], a[p])

จากโค้ดด้านบน randint(a .. b) คืนค่าเป็นจำนวนเต็มตั้งแต่ a ถึง b สำหรับอัลกอริทึมนี้ ทำโดยเริ่มจากลำดับเรียงสับเปลี่ยน 0 ถึง N-1 เรียงตามลำดับจากน้อยไปมาก หลังจากนั้นวนลูปจาก 0 ถึง N-1 และเลือกจำนวนเต็มสองจำนวนตั้งแต่ k ถึง N-1 และสลับจำนวนในช่องที่ k กับช่องที่สุ่มตัวเลขได้มา

ตัวอย่าง เมื่อ N=4 จะเริ่มจากลำดับเริ่มต้น 0 1 2 3

เมื่อ k=0 จะเลือกจำนวนเต็มตั้งแต่ 0 ถึง 3 ซึ่งในที่นี้สุ่มได้ 2 ก็จะสลับจำนวนตำแหน่งที่ 0 กับจำนวนที่ 2 ทำให้ได้ลำดับ 2 1 0 3

เมื่อ k=1 ก็จะเลือกจำนวนเต็มตั้งแต่ 1 ถึง 3 คราวนี้สุ่มได้ 2 อีกครั้ง ก็สลับจำนวนในตำแหน่งที่ 2 กับตำแหน่งที่ 1 2 0 1 3

เมื่อ k=2 ก็จะเลือกจำนวนเต็มตั้งแต่ 2 ถึง 3 สุ่มได้ 3 อีกครั้ง ก็สลับจำนวนในตำแหน่งที่ 2 กับตำแหน่งที่ 3 2 0 3 1

เมื่อ k=2 ก็จะเลือกจำนวนเต็มตั้งแต่ 3 ถึง 3 ซึ่งสุ่มได้จำนวนเดียวคือ 3 ก็สลับจำนวนในตำแหน่งที่ 3 กับตำแหน่งที่ 3 ก็คือไม่มีอะไรเปลี่ยนแปลง 2 0 3 1

ขั้นตอนการสุ่มลำดับการเรียงสับเปลี่ยนที่ดีก็มีเพียงเท่านี้ อัลกอริทึมในสร้างลำดับการเรียงสับเปลี่ยนโดยสุ่มแบบกระจายนั้นมีอีกมากมาย แต่อัลกอริทึมอื่นจะไม่ให้การสุ่มที่กระจายดี เช่นอัลกอริทึมที่ไม่ดีต่อไปนี้ ซึ่งแทนที่จะสุ่มตัวเลขตั้งแต่ k ถึง N-1 เราจะสุ่มตัวเลขตั้งแต่ 0 ถึง N-1 แทนในทุกๆการทำงาน แม้จะเปลี่ยนแค่นิดเดียว แต่ลำดับการเรียงสับเปลี่ยนที่ออกมาก็จะมีบางลำดับออกมาบ่อยกว่าลำดับอื่นๆ

Pseudocode ของการสร้างลำดับเรียงสับเปลี่ยนของอัลกอริทึมที่ไม่ดีเขียนได้ดังนี้

for k in 0 .. N-1:
 a[k] = k
for k in 0 .. N-1:
 p = randint(0 .. N-1)
 swap(a[k], a[p])

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

งานของคุณ

ในโจทย์ข้อนี้จะแตกต่างจากโจทย์ข้ออื่นๆ ในการแข่งขัน Code Jam ซึ่งคุณจะได้ลำดับการเรียงสับเปลี่ยน 120 ลำดับ ที่มีความยาว 1000 ตัว ซึ่งจะต้องปริ้นท์คำตอบสำหรับแต่ละเคส (ตรงนี้ก็ปกติแหละ) แต่ว่าไม่จำเป็นต้องตอบให้ถูกทุกเคส (จ้า) คำตอบที่ส่งเข้ามาจะถือว่าถูกต้อง หากตอบถูกอย่างน้อย 109 เคส แต่คำตอบต้องอยู่ในรูปแบบที่กำหนดให้ ถึงแม้ว่าจะผิดอย่างไรก็ตาม แต่ก็ยังตรวจให้ถูกได้ถ้าพิมพ์ GOOD กับ BAD สลับกันหมดทุกเคส

รับประกันว่าลำดับที่ให้มาจะถูกสร้างจากอัลกอริทึมทั้งสองเสมอ ซึ่งจะสร้างให้แต่ละคนไม่เหมือนกัน (?)

ปัญหาในข้อนี้เป็นเรื่องของการสุ่ม ซึ่งอาจทำให้คำตอบที่ออกมาถูกไม่ถึง 109 เคสเพราะอัลกอริทึมทั้งสองสามารถสร้างลำดับใดๆ มาก็ได้ ทำให้ปัญหาข้อนี้ไม่มีชุดทดสอบใหญ่ ซึ่งจะส่งได้เรื่อยๆถ้าผิด แต่ก็จะโดนเพิ่มเวลา Penalty อีก 4 นาทีเช่นเดียวกันกับการส่งคำตอบผิดในข้ออื่นๆ

จากประสบการณ์ที่ออกโจทย์แนวนี้มา ก็อาจจะมีการตอบผิดเพราะโชคร้ายมากๆ ดังนั้น ถ้ามั่นใจว่าอัลกอริทึมของตัวเองถูกต้อง ก็ส่งมาใหม่เถอะ

โชคดี

ข้อมูลนำเข้า

บรรทัดแรกรับจำนวนเคสย่อย T ซึ่งจะเป็น 120 เสมอ สำหรับเคสย่อยแต่ละเคสมีสองบรรทัด บรรทัดแรกเป็นจำนวนเต็มบวก N (เป็น 1000 เสมอ) บรรทัดที่สองเป็นลำดับการเรียงสับเปลี่ยน ความยาว N ตัว คั่นด้วยช่องว่าง (ซึ่งจะถูกสร้างจากอัลกอริทึมทั้งสองนี้เสมอ)

ข้อมูลส่งออก

สำหรับเคสย่อยใดๆ จะมีคำตอบบรรทัดเดียว อยู่ในรูป "Case #x: y" เมื่อ x เป็นหมายเลขเคสย่อย (เริ่มจากหนึ่ง) และ y เป็นสตริงคำว่า "GOOD" หรือ "BAD" โดยไม่มีเครื่องหมายคำพูด ซึ่งจะพิมพ์ว่า GOOD หากคิดว่าสร้างมาจากอัลกอริทึมที่ 1 และพิมพ์ว่า BAD หากสร้างจากอัลกอริทึมที่สอง

ขอบเขตข้อมูล

T = 120 G = 109 N = 1000 ตัวเลขในลำดับการเรียงสับเปลี่ยนจะมีค่าตั้งแต่ 0 ถึง N-1 และไม่ปรากฎซ้ำกันในลำดับ

ตัวอย่าง

ข้อมูลนำเข้า

2
3
0 1 2
3
2 0 1

ข้อมูลส่งออก

Case #1: BAD
Case #2: GOOD

หมายเหตุ

ข้อมูลจริงใหญ่กว่านี้นะ อย่าลืมว่ามี 1000 ตัวเสมอ