ผลต่างระหว่างรุ่นของ "Gcj2014"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
แถว 72: แถว 72:
 
2 0 3 1
 
2 0 3 1
  
−
ขั้นตอนการสุ่มลำดับการเรียงสับเปลี่ยนที่ดีก็มีเพียงเท่านี้
+
ขั้นตอนการสุ่มลำดับการเรียงสับเปลี่ยนที่ดีก็มีเพียงเท่านี้   อัลกอริทึมในสร้างลำดับการเรียงสับเปลี่ยนโดยสุ่มแบบกระจายนั้นมีอีกมากมาย แต่อัลกอริทึมอื่นจะไม่ให้การสุ่มที่กระจายดี เช่นอัลกอริทึมที่ไม่ดีต่อไปนี้ ซึ่งแทนที่จะสุ่มตัวเลขตั้งแต่ k ถึง N-1 เราจะสุ่มตัวเลขตั้งแต่ 0 ถึง N-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):
+
Pseudocode ของการสร้างลำดับเรียงสับเปลี่ยนของอัลกอริทึมที่ไม่ดีเขียนได้ดังนี้
  
 
  for k in 0 .. N-1:
 
  for k in 0 .. N-1:
 
   a[k] = k
 
   a[k] = k
−
for k in 0 .. N-1:
+
for k in 0 .. N-1:
 
   p = randint(0 .. N-1)
 
   p = randint(0 .. N-1)
 
   swap(a[k], a[p])
 
   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
+
ในชุดทดสอบแต่ละชุดทดสอบ จะมีลำดับการเรียงสับเปลี่ยนมาให้ ซึ่งจะสุ่มสร้างจากอัลกอริทึมที่ดีและที่ไม่ดี งานของคุณคือเดามาว่าลำดับที่ให้มาใช้อัลกอริทึมไหนในการสร้าง
 +
 
 +
'''งานของคุณ'''
 +
 
 +
ในโจทย์ข้อนี้จะแตกต่างจากโจทย์ข้ออื่นๆ ในการแข่งขัน Code Jam ซึ่งคุณจะได้ลำดับการเรียงสับเปลี่ยน 120 ลำดับ ที่มีความยาว 1000 ตัว ซึ่งจะต้องปริ้นท์คำตอบสำหรับแต่ละเคส (ตรงนี้ก็ปกติแหละ) แต่ว่าไม่จำเป็นต้องตอบให้ถูกทุกเคส (จ้า) คำตอบที่ส่งเข้ามาจะถือว่าถูกต้อง หากตอบถูกอย่างน้อย 109 เคส แต่คำตอบต้องอยู่ในรูปแบบที่กำหนดให้ ถึงแม้ว่าจะผิดอย่างไรก็ตาม แต่ก็ยังตรวจให้ถูกได้ถ้าพิมพ์ GOOD กับ BAD สลับกันหมดทุกเคส
 +
 
 +
รับประกันว่าลำดับที่ให้มาจะถูกสร้างจากอัลกอริทึมทั้งสองเสมอ ซึ่งจะสร้างให้แต่ละคนไม่เหมือนกัน (?)
 +
 
 +
 
 +
ปัญหาในข้อนี้เป็นเรื่องของการสุ่ม ซึ่งอาจทำให้คำตอบที่ออกมาถูกไม่ถึง 109 เคสเพราะอัลกอริทึมทั้งสองสามารถสร้างลำดับใดๆ มาก็ได้ ทำให้ปัญหาข้อนี้ไม่มีชุดทดสอบใหญ่ ซึ่งจะส่งได้เรื่อยๆถ้าผิด แต่ก็จะโดนเพิ่มเวลา Penalty อีก 4 นาทีเช่นเดียวกันกับการส่งคำตอบผิดในข้ออื่นๆ 
 +
 
 +
จากประสบการณ์ที่ออกโจทย์แนวนี้มา ก็อาจจะมีการตอบผิดเพราะโชคร้ายมากๆ ดังนั้น ถ้ามั่นใจว่าอัลกอริทึมของตัวเองถูกต้อง ก็ส่งมาใหม่เถอะ
 +
 
 +
โชคดี
 +
 
 +
 
 +
== '''ข้อมูลนำเข้า''' ==
  
−
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.
+
บรรทัดแรกรับจำนวนเคสย่อย T ซึ่งจะเป็น 120 เสมอ
 +
สำหรับเคสย่อยแต่ละเคสมีสองบรรทัด บรรทัดแรกเป็นจำนวนเต็มบวก N (เป็น 1000 เสมอ)
 +
บรรทัดที่สองเป็นลำดับการเรียงสับเปลี่ยน ความยาว N ตัว คั่นด้วยช่องว่าง (ซึ่งจะถูกสร้างจากอัลกอริทึมทั้งสองนี้เสมอ)
  
−
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
+
สำหรับเคสย่อยใดๆ จะมีคำตอบบรรทัดเดียว อยู่ในรูป "Case #x: y" เมื่อ x เป็นหมายเลขเคสย่อย (เริ่มจากหนึ่ง) และ y เป็นสตริงคำว่า "GOOD" หรือ "BAD" โดยไม่มีเครื่องหมายคำพูด ซึ่งจะพิมพ์ว่า GOOD หากคิดว่าสร้างมาจากอัลกอริทึมที่ 1 และพิมพ์ว่า BAD หากสร้างจากอัลกอริทึมที่สอง
  
−
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
 
T = 120
 
G = 109
 
G = 109
 
N = 1000
 
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.
+
ตัวเลขในลำดับการเรียงสับเปลี่ยนจะมีค่าตั้งแต่ 0 ถึง N-1 และไม่ปรากฎซ้ำกันในลำดับ
  
−
Sample
 
  
 +
== '''ตัวอย่าง''' ==
  
−
Input
+
 
 +
'''ข้อมูลนำเข้า'''
 
 
 
 
−
Output
+
  2
−
   
+
3
−
2
+
0 1 2
−
3
+
3
−
0 1 2
+
2 0 1
−
3
+
 
−
2 0 1
+
'''ข้อมูลส่งออก'''
  
−
Case #1: BAD
+
Case #1: BAD
−
Case #2: GOOD
+
Case #2: GOOD
  
−
Note
+
''หมายเหตุ''
  
−
The sample input doesn't follow the limitations from the problem statement - the real input will be much bigger.
+
ข้อมูลจริงใหญ่กว่านี้นะ อย่าลืมว่ามี 1000 ตัวเสมอ

รุ่นแก้ไขเมื่อ 13:03, 8 มีนาคม 2558

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 ตัวเสมอ

ดึงข้อมูลจาก "http://158.108.32.49/wiki/index.php?title=Gcj2014&oldid=48272"