Codejam2014

Charing Chaos

โชตะเป็นชาวนา โชตะกำลังมีปัญหา โชตะพึ่งย้ายมายังฟาร์มใหม่เอี่ยมล่าสุดที่พึ่งสร้างของเขา แต่แล้ว ปรากฏว่าไฟฟ้ากลับไม่ได้ถูกตั้งค่าอย่างถูกต้องสำหรับอุปกรณ์ของเขา ในฐานะที่โชตะเป็นชาวนายุคใหม่ โชตะมี smartphone แฃะ laptop มากมาย มากซะจนมีเพียงพอให้ วากิว ซึ่งเป็นวัวตัวโปรด ยืมไปใช้เสียด้วยซ้ำ โดยเขามีมือถือทั้งหมด N เครื่อง

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

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

เช่น

ปลั๊กไฟ 0: 10

ปลั๊กไฟ 1: 01

ปลั๊กไฟ 2: 11

เมื่อปรับสวิทช์ตัวที่ 2 ผลลัพธ์ที่ได้คือ

ปลั๊กไฟ 0: 11

ปลั๊กไฟ 1: 00

ปลั๊กไฟ 2: 10

ถ้าโชตะมี smartphone ึ่งใช้กระแสแบบ "11" และ tablet ซึ่งใช้กระแสแบบ "10" รวมทั้งแลบท๊อปที่ใช้กระแสแบบ "00" การสับสวิทซ์ที่ 2 จะทำให้เค้ามีความสุขถึงขั้นสุดยอด

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

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

บรรทัดแรก ให้จำนวนเทสทั้งหมด T ตามด้วย T เทสเคส โดยในแต่ละเทสจะมีข้อมูล 3 บรรทัด บรรทัดแรก ให้จำนวนเต็มสองจำนวน N และ L คั่นด้วยช่องว่าง บรรทัดที่สอง ให้สตริงขนาด L ซึ่งแทนกระแสไฟเริ่มต้นของปลั๊กไฟในบ้านจำนวน N ตัว คั่นด้วยช่องว่าง บรรทัดที่ 3 ให้สตริงขนาด L ซึ่งแทนกระแสไฟที่อุปกรณ์ของเขาต้องการทั้งหมด N ตัว

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

ในแต่ละเทส ให้แสดง หนึ่งบรรทัดในรูปแบบ "Case #x: y" โดย x แทนหมายเลขเทส เริ่มต้นจาก 1 และ y แทนจำนวนสวิทช์น้อยที่สุดที่มิซากิต้องสลับ เพื่อให้โชตะชาร์จไฟได้ ถ้าโชตะไม่มีวันชาร์จไฟได้ y จะเป็น string "NOT POSSIBLE"

ข้อจำกัด

1 <= T <= 100

ไม่มีปลั๊กไฟใด ๆ ให้กระแสไฟที่เหมือนกัน ไม่มีอุปกรณ์ใด ๆ ต้องการกระแสไฟที่เหมือนกัน

เทสเล็ก

1 <= N <= 10 2 <= L <= 10

เทสใหญ่

1 <= N <= 150 10 <= L <= 40

2

ต้นไม้ก็คือกราฟที่ไม่มี cycle

ต้นไม้แบบมีราก คือการเลือกปมพิเศษขึ้นมาปมหนึ่ง และถือว่าปมนี้เป็นปมรากของต้นไม้ สำหรับสองปม x y ใด ๆ ที่มีเส้นเชื่อมระหว่างกัน เราจะถือว่า y เป็นลูกของ x ถ้า x อยู่ใกล้ปมรากมากกว่า y

ต้นไม้ไบนารี่แบบเต็ม (full binary tree) คือต้นไม้แบบมีรากที่ปมทุกปมมีลูก 2 ลูก หรือ 0 ลูกเสมอ

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

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

บรรทัดแรกของข้อมูลนำเข้าเป็นจำนวนเต็ม T ที่ระบุจำนวน test case ทั้งหมด โดยที่แต่ละ test case เป็นดังนี้ บรรทัดแรกมีจำนวนเต็ม N ซึ่งระบุจำนวนของปมในต้นไม้ หลังจากนั้นอีก N-1 บรรทัด แต่ละบรรทัดมีจำนวนเต็มสองตัวคือ xi และ yi ซึ่งระบุว่ามีเส้นเชื่อมแบบไม่มีทิศทางระหว่างปม xi และ yi

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

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

ข้อจำกัด

1 <= T <= 100

1 <= xi, yi <= N

รับประกันว่าแต่ละ test case เป็นต้นไม้ที่ต่อถึงกันแน่นอน

ชุดข้อมูลทดสอบเล็ก

2 <= N <= 15

ชุดข้อมูลทดสอบใหญ่

2 <= N <= 1000

ตัวอย่าง

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

3
3
2 1
1 3
7
4 5
4 2
1 2
3 1
6 4
3 7
4
1 2
2 3
3 4

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

Case #1: 0
Case #2: 2
Case #3: 1

อธิบายตัวอย่าง

ใน test case แรก G เป็นต้นไม้ไบนารี่แบบเต็มอยู่แล้ว ถ้าเราเลือกปม 1 เป็นราก ดังนั้นก็ไม่ต้องทำอะไร (ตอบ 0)

ใน test case ที่สอง เราสามารถลบปม 3 และ 7 แล้วเลือกปม 2 เป็นรากของต้นไม้ไบนารี่แบบเต็มได้

ใน test case สุดท้าย เราสามารถลบปม 1 แล้วเลือกปม 3 เป็นรากของต้นไม้ไบนารี่แบบเต็มได้ (อีกกรณีหนึ่งคือเราสามารถลบปม 4 แล้วเลือก 2 เป็นรากก็ได้)

Problem C. Proper Shuffle

permutation ขนาด N เป็นลำดับของจำนวน N ตัว แต่ละตัวมีค่าระหว่าง 0 ถึง N-1 โดยที่แต่ละตัวปรากฏแค่หนึ่งครับ และสามารถปรากฏในลำดับใดก็ได้

มี permutation ขนาด N จำนวนมากมาย (มี N factorial แบบ แต่นั่นไม่จำเป็นสำหรับข้อนี้) บางทีเราต้องการสุ่มหยิบ permutation มาหนึ่งอัน และแน่นอนเราต้องการหยิบหนึ่งอันแบบ uniform (นั่นคือ ทุก ๆ permutation ขนาด N ต้องมีความน่าจะเป็นที่จะถูกเลือกเท่า ๆ กัน)

ด้านล่างเป็นโค้ดที่เป็นไปได้แบบหนึ่งที่จะทำงานนี้ (เราจะเรียกมันว่า good algorithm ต่อไป)

(ดูในโจทย์ภาษาอังกฤษประกอบด้วย)

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) จะคืนค่าจำนวนเต็มที่สุ่มแบบ uniform จาก a ถึง b (รวม a และ b ด้วย)

นี่คืออัลกอริทึมนั้นถ้าอธิบายเป็นภาษาพูด: เราเริ่มที่ identity permutation จากนั้น for each k ตั้งแต่ 0 ถึง N-1 (inclusive), เราจะสุ่มเลือกจำนวนเต็ม pk แบบเป็นอิสระและ uniform จาก k ถึง N-1 (inclusive) และสลับข้อมูลตำแหน่งที่ k กับตำแหน่งที่ pk (ดัชนีเริ่มที่ 0)

นี่คือตัวอย่างสำหรับ N=4, เราเริ่มด้วย identity permutation:

0 1 2 3

(ดูต่อในโจทย์ภาษาอังกฤษ -- โจทย์จะอธิบายการทำงานของ good algorithm)

2 0 3 1

กระบวนการดังกล่าวจบลง และเราจะได้ random permutation

มีอัลกอริทึมอื่น ๆ อีกที่จะสร้าง random permutation อย่างไรก็ตาม มีอีกหลายอัลกอริทึมที่ดูคล้าย ๆ อัลกอริทึมด้านบน แต่ไม่ได้สร้าง random permutation ที่ uniform บาง permutation จะมีความน่าจะเป็นที่จะถูกสร้างมากกว่าอันอื่น

ด้านล่างเป็นอัลกอริทึมในกลุ่มดังกล่าว (เราจะเรียกว่าเป็น bad algorithm ต่อไป)

(ดูโค้ดในภาษาอังกฤษประกอบด้วย)

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])

ในแต่ละ test case คุณจะได้รับ permutation ที่ถูกสร้างด้วยวิธีดังนี้: เราจะเริ่มจากการเลือกอัลกอริทึมจาก good algoroithm กับ bad algorithm ด้วยความน่าจะเป็น 50%. จากนั้นเราจะสร้าง permutation ด้วยอัลกอริทึมนั้น. คำถามคือคุณสามารถเดาได้หรือไม่ว่า อัลกอริทึมใดที่เราเลือก โดยดูจาก permutation ที่ถูกสร้างขึ้นมา

การแก้ปัญหานี้

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

รับประกันว่า permutation ทั้งหมดที่คุณได้รับนั้นถูกสร้างตามเงื่อนไขข้างต้น และถูกสร้างโดยเป็นอิสระต่อกัน

ปัญหานี้มีความสุ่มเกี่ยวข้อง ดังนั้นเป็นไปได้ที่ว่าคำตอบที่ถูกต้องอาจจะเดาถูกไม่ถึง 109 กรณีทดสอบ ด้วยเหตุนี้โจทย์ข้อนี้จึงไม่มี Large input แต่จะมีกรณีทดสอบแบบ Small ที่คุณจะสามารถทดลองได้เรื่อย ๆ แน่นอนว่ายังมี penalty 4 นาทีอยู่ ถึงแม้ว่าการที่คุณแก้ไม่ได้ จะมาจากที่คุณโชคไม่ดีก็ตาม

ในประสบการณ์ของเรา เหตุการณ์นั้นเกิดขึ้นได้ ดังนั้น ถ้าคุณมั่นใจว่าคำตอบของคุณควรจะถูกต้อง เป็นการเหมาะสมที่คุณจะทดลองส่งใหม่

โชคดี!