Gcj2014 - ประวัติรุ่นแก้ไข

202.28.78.246: /* C. Proper Shuffle */

2015-03-08T13:07:24Z

C. Proper Shuffle

202.28.78.246: /* ตัวอย่าง */

2015-03-08T13:06:25Z

ตัวอย่าง

202.28.78.246: /* ขอบเขตข้อมูล */

2015-03-08T13:05:41Z

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

202.28.78.246: /* ข้อมูลส่งออก */

2015-03-08T13:05:02Z

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

202.28.78.246: /* ข้อมูลนำเข้า */

2015-03-08T13:04:44Z

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

202.28.78.246: /* C. Proper Shuffle */

2015-03-08T13:03:52Z

C. Proper Shuffle

202.28.78.246: /* C. Proper Shuffle */

2015-03-08T12:42:52Z

C. Proper Shuffle

Jittat: /* A. Charging Chaos */

2015-03-08T10:54:32Z

A. Charging Chaos

Jittat: /* B. Full Binary Tree */

2015-03-08T10:53:44Z

B. Full Binary Tree

Jittat: /* Round 1A */

2015-03-08T10:45:52Z

Round 1A

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 13:07, 8 มีนาคม 2558
แถว 105:		แถว 105:
	บรรทัดที่สองเป็นลำดับการเรียงสับเปลี่ยน ความยาว N ตัว คั่นด้วยช่องว่าง (ซึ่งจะถูกสร้างจากอัลกอริทึมทั้งสองนี้เสมอ)		บรรทัดที่สองเป็นลำดับการเรียงสับเปลี่ยน ความยาว N ตัว คั่นด้วยช่องว่าง (ซึ่งจะถูกสร้างจากอัลกอริทึมทั้งสองนี้เสมอ)

−	'''ข้อมูลส่งออก'''	+	'''ข้อมูลส่งออก'''

@@ แถว 117: / แถว 117: @@
 ตัวเลขในลำดับการเรียงสับเปลี่ยนจะมีค่าตั้งแต่ 0 ถึง N-1 และไม่ปรากฎซ้ำกันในลำดับ
-== '''ตัวอย่าง''' ==
+'''ตัวอย่าง'''
-'''ข้อมูลนำเข้า'''
+ข้อมูลนำเข้า
@@ แถว 128: / แถว 128: @@
 0 1
-'''ข้อมูลส่งออก'''
+ข้อมูลส่งออก
   Case #1: BAD

@@ แถว 110: / แถว 110: @@
 สำหรับเคสย่อยใดๆ จะมีคำตอบบรรทัดเดียว อยู่ในรูป "Case #x: y" เมื่อ x เป็นหมายเลขเคสย่อย (เริ่มจากหนึ่ง) และ y เป็นสตริงคำว่า "GOOD" หรือ "BAD" โดยไม่มีเครื่องหมายคำพูด ซึ่งจะพิมพ์ว่า GOOD หากคิดว่าสร้างมาจากอัลกอริทึมที่ 1 และพิมพ์ว่า BAD หากสร้างจากอัลกอริทึมที่สอง
-== '''ขอบเขตข้อมูล''' ==
+'''ขอบเขตข้อมูล'''
 T = 120
@@ แถว 118: / แถว 116: @@
 N = 1000
 ตัวเลขในลำดับการเรียงสับเปลี่ยนจะมีค่าตั้งแต่ 0 ถึง N-1 และไม่ปรากฎซ้ำกันในลำดับ
 == '''ตัวอย่าง''' ==

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

@@ แถว 98: / แถว 98: @@
-== '''ข้อมูลนำเข้า''' ==
+'''ข้อมูลนำเข้า'''
@@ แถว 104: / แถว 104: @@
 สำหรับเคสย่อยแต่ละเคสมีสองบรรทัด บรรทัดแรกเป็นจำนวนเต็มบวก N (เป็น 1000 เสมอ)
 บรรทัดที่สองเป็นลำดับการเรียงสับเปลี่ยน ความยาว N ตัว คั่นด้วยช่องว่าง (ซึ่งจะถูกสร้างจากอัลกอริทึมทั้งสองนี้เสมอ)
 == '''ข้อมูลส่งออก''' ==

@@ แถว 72: / แถว 72: @@
 0 3 1
-ขั้นตอนการสุ่มลำดับการเรียงสับเปลี่ยนที่ดีก็มีเพียงเท่านี้
+ขั้นตอนการสุ่มลำดับการเรียงสับเปลี่ยนที่ดีก็มีเพียงเท่านี้   อัลกอริทึมในสร้างลำดับการเรียงสับเปลี่ยนโดยสุ่มแบบกระจายนั้นมีอีกมากมาย แต่อัลกอริทึมอื่นจะไม่ให้การสุ่มที่กระจายดี เช่นอัลกอริทึมที่ไม่ดีต่อไปนี้ ซึ่งแทนที่จะสุ่มตัวเลขตั้งแต่ k ถึง N-1 เราจะสุ่มตัวเลขตั้งแต่ 0 ถึง N-1 แทนในทุกๆการทำงาน แม้จะเปลี่ยนแค่นิดเดียว แต่ลำดับการเรียงสับเปลี่ยนที่ออกมาก็จะมีบางลำดับออกมาบ่อยกว่าลำดับอื่นๆ
-Here's the pseudocode for this algorithm (we'll call it the bad algorithm below):
+Pseudocode ของการสร้างลำดับเรียงสับเปลี่ยนของอัลกอริทึมที่ไม่ดีเขียนได้ดังนี้
   for k in 0 .. N-1:
    a[k] = k
-for k in 0 .. N-1:
+ for k in 0 .. N-1:
    p = randint(0 .. N-1)
    swap(a[k], a[p])
-Solving this problem
+ในชุดทดสอบแต่ละชุดทดสอบ จะมีลำดับการเรียงสับเปลี่ยนมาให้ ซึ่งจะสุ่มสร้างจากอัลกอริทึมที่ดีและที่ไม่ดี งานของคุณคือเดามาว่าลำดับที่ให้มาใช้อัลกอริทึมไหนในการสร้าง
-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 เสมอ
-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.
+== '''ข้อมูลส่งออก''' ==
-Input
+สำหรับเคสย่อยใดๆ จะมีคำตอบบรรทัดเดียว อยู่ในรูป "Case #x: y" เมื่อ x เป็นหมายเลขเคสย่อย (เริ่มจากหนึ่ง) และ y เป็นสตริงคำว่า "GOOD" หรือ "BAD" โดยไม่มีเครื่องหมายคำพูด ซึ่งจะพิมพ์ว่า GOOD หากคิดว่าสร้างมาจากอัลกอริทึมที่ 1 และพิมพ์ว่า BAD หากสร้างจากอัลกอริทึมที่สอง
-Output
+== '''ขอบเขตข้อมูล''' ==
 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.
+ตัวเลขในลำดับการเรียงสับเปลี่ยนจะมีค่าตั้งแต่ 0 ถึง N-1 และไม่ปรากฎซ้ำกันในลำดับ
-Input
-Output
-−
+1 2
-−
-1 2
+0 1
-−
-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 ตัวเสมอ

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 12:42, 8 มีนาคม 2558
แถว 44:		แถว 44:

	Source: [https://code.google.com/codejam/contest/2984486/dashboard#s=p2]		Source: [https://code.google.com/codejam/contest/2984486/dashboard#s=p2]
		+
		+	ลำดับการเรียงสับเปลี่ยนของ 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.

@@ แถว 5: / แถว 5: @@
 Source: [https://code.google.com/codejam/contest/2984486/dashboard#s=p0]
-ชาวนา Shota มีปัญหา เขาเพิ่งจะย้ายไปที่บ้านฟาร์ม แต่ระบบปลั๊กไฟนั้นมีการติดตั้งที่ผิดพลาด  เนื่องจากเขาเป็นชาวนายุคใหม่ Shota จึงมีมือถือและแลบทอปจำนวนมาก  เขามีอุปกรณ์รวมทั้งสิ้น N ชิ้น
+ชาวนา Shota มีปัญหา เขาเพิ่งจะย้ายไปที่บ้านฟาร์ม แต่ระบบปลั๊กไฟนั้นมีการติดตั้งที่ผิดพลาด  เนื่องจากเขาเป็นชาวนายุคใหม่ Shota จึงมีมือถือและแลบทอปจำนวนมาก  เขามีอุปกรณ์รวมทั้งสิ้น '''N''' ชิ้น
-อุปกรณ์เหล่านี้มี spec ที่แตกต่างกันและทำโดยบริษัทที่แตกต่างกันด้วย อุปกรณ์เหล่านี้จึงมีความต้องการการไหลของกระแสไฟที่แตกต่างกัน  ในทำนองเดียวกันปลั๊กไฟแต่ละอันก็มีการปล่อยกระแสไฟที่แตกต่างกันด้วย  กระแสไฟที่ปล่องนี้ สามารถแทนได้ด้วยสตริงของ 0 และ 1 ความยาว L ตัวอักษร
+อุปกรณ์เหล่านี้มี spec ที่แตกต่างกันและทำโดยบริษัทที่แตกต่างกันด้วย อุปกรณ์เหล่านี้จึงมีความต้องการการไหลของกระแสไฟที่แตกต่างกัน  ในทำนองเดียวกันปลั๊กไฟแต่ละอันก็มีการปล่อยกระแสไฟที่แตกต่างกันด้วย  กระแสไฟที่ปล่องนี้ สามารถแทนได้ด้วยสตริงของ 0 และ 1 ความยาว '''L''' ตัวอักษร
-Shota ต้องการที่จะชาร์ตอุปกรณ์ทั้ง N ชิ้นนี้พร้อม ๆ กัน และก็เป็นเหตุบังเอิญเลยทีเดียวที่ในบ้านก็มีปลั๊กจำนวน N อันเช่นเดียวกัน  ในการปรับแต่งกระแสไฟฟ้า จะมีแป้นควบคุมที่ประกอบไปด้วยสวิตช์จำนวน L อัน สวิตช์อันที่ i จะสลับบิตที่ i ของกระแสไฟฟ้าของทุก ๆ ปลั๊กในบ้าน ยกตัวอย่างเช่น ถ้ากระแสของแต่ละปลั๊กเป็นดังนี้:
+Shota ต้องการที่จะชาร์ตอุปกรณ์ทั้ง '''N''' ชิ้นนี้พร้อม ๆ กัน และก็เป็นเหตุบังเอิญเลยทีเดียวที่ในบ้านก็มีปลั๊กจำนวน '''N''' อันเช่นเดียวกัน  ในการปรับแต่งกระแสไฟฟ้า จะมีแป้นควบคุมที่ประกอบไปด้วยสวิตช์จำนวน '''L''' อัน สวิตช์อันที่ '''i''' จะสลับบิตที่ '''i''' ของกระแสไฟฟ้าของทุก ๆ ปลั๊กในบ้าน ยกตัวอย่างเช่น ถ้ากระแสของแต่ละปลั๊กเป็นดังนี้:
 <pre>

@@ แถว 32: / แถว 32: @@
 Source: [https://code.google.com/codejam/contest/2984486/dashboard#s=p1]
 === C. Proper Shuffle ===
 Source: [https://code.google.com/codejam/contest/2984486/dashboard#s=p2]

@@ แถว 1: / แถว 1: @@
-== Round 1A ==
+== Round 1A 2014 ==
-=== Charging Chaos ===
+=== A. Charging Chaos ===
 Source: [https://code.google.com/codejam/contest/2984486/dashboard#s=p0]
@@ แถว 29: / แถว 29: @@
 Misaki ได้รับการว่าจ้างจาก Shota ให้ช่วยเขาแก้ปัญหา  เธอได้วัดกระแสจากทุก ๆ ปลั๊กในบ้านและสังเกตว่ามันแตกต่างกันทั้งหมด  ให้ตรวจสอบว่าเป็นไปได้หรือไม่ที่ Shota จะสามารถชาร์ตอุปกรณ์ทั้งหมดของเขาในเวลาเดียวกันได้หรือไม่ ถ้าเป็นไปได้ ให้หาว่าจำนวนสวิชต์ที่ต้องสลับทั้งหมดที่น้อยที่สุดเป็นเท่าใด (เนื่องจาก Misaki ไม่อยากจะเหนื่อยกดสวิชต์มากเกินความจำเป็น)
-=== Full Binary Tree ===
+=== B. Full Binary Tree ===
 Source: [https://code.google.com/codejam/contest/2984486/dashboard#s=p1]
-=== Proper Shuffle ===
+=== C. Proper Shuffle ===
 Source: [https://code.google.com/codejam/contest/2984486/dashboard#s=p2]