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

ขั้นตอนการสุ่มลำดับการเรียงสับเปลี่ยนที่ดีก็มีเพียงเท่านี้ There are many other algorithms that produce a random permutation uniformly. However, there are also many algorithms to generate a random permutation that look very similar to this algorithm, but are not uniform — some permutations are more likely to be produced by those algorithms than others. อัลกอริทึมในสร้างลำดับการเรียงสับเปลี่ยนโดยสุ่มแบบกระจายนั้นมีอีกมากมาย แต่อัลกอริทึมอื่นจะไม่ให้ Here's one bad algorithm of this type. Take the good algorithm above, but at each step, instead of picking pk randomly between k and N-1, inclusive, let's pick it randomly between 0 and N-1, inclusive. This is such a small change, but now some permutations are more likely to appear than others!

Here's the pseudocode for this algorithm (we'll call it the bad algorithm below):

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

In each test case, you will be given a permutation that was generated in the following way: first, we choose either the good or the bad algorithm described above, each with probability 50%. Then, we generate a permutation using the chosen algorithm. Can you guess which algorithm was chosen just by looking at the permutation?

Solving this problem

This problem is a bit unusual for Code Jam. You will be given T = 120 permutations of N = 1000 numbers each, and should print an answer for each permutation – this part is as usual. However, you don't need to get all of the answers correct! Your solution will be considered correct if your answers for at least G = 109 cases are correct. However, you must follow the output format, even for cases in which your answer doesn't turn out to be correct. The only thing that can be wrong on any case, yet still allow you to be judged correct, is swapping GOOD for BAD or vice versa; but you should still print either GOOD or BAD for each case.

It is guaranteed that the permutations given to you were generated according to the method above, and that they were generated independently of each other.

This problem involves randomness, and thus it might happen that even the best possible solution doesn't make 109 correct guesses for a certain input, as both the good and the bad algorithms can generate any permutation. Because of that, this problem doesn't have a Large input, and has just the Small input which you can try again if you think you got unlucky. Note that there is the usual 4-minute penalty for incorrect submissions if you later solve that input, even if the only reason you got it wrong was chance.

In our experience with this problem, that did happen (getting wrong answer just because of chance); so if you are confident that your solution should be working, but it failed, it might be a reasonable strategy to try again with the same solution which failed.

Good luck!

Input

The first line of the input gives the number of test cases, T (which will always be 120). Each test case contains two lines: the first line contains the single integer N (which will always be 1000), and the next line contains N space-separated integers - the permutation that was generated using one of the two algorithms.

Output

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is either "GOOD" or "BAD" (without the quotes). You should output "GOOD" if you guess that the permutation was generated by the first algorithm described in the problem statement, and "BAD" if you guess that the permutation was generated by the second algorithm described in the problem statement.

Limits

T = 120 G = 109 N = 1000 Each number in the permutation will be between 0 and N-1 (inclusive), and each number from 0 to N-1 will appear exactly once in the permutation.

Sample

Input

Output

2 3 0 1 2 3 2 0 1

Case #1: BAD Case #2: GOOD

Note

The sample input doesn't follow the limitations from the problem statement - the real input will be much bigger.