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

Jittat: /* Charing Chaos */

2014-04-26T01:58:05Z

Charing Chaos

Jittat: /* Charing Chaos */

2014-04-26T01:57:44Z

Charing Chaos

Jittat: /* 4 */

2014-04-26T01:43:44Z

Jittat: /* 2 */

2014-04-26T01:43:29Z

Jittat: /* 3 */

2014-04-26T01:43:07Z

110.77.225.59: /* Charing Chaos */

2014-04-26T01:42:03Z

Charing Chaos

110.77.225.59: /* Charing Chaos */

2014-04-26T01:41:31Z

Charing Chaos

Nattee: /* 2 */

2014-04-26T01:39:56Z

110.77.225.59: /* Charging Chaos */

2014-04-26T01:38:26Z

Charging Chaos

Jittat: /* 3 */

2014-04-26T01:38:06Z

@@ แถว 6: / แถว 6: @@
 โชตะต้องการให้ฟาร์ทใหม่ของเขาสามารถชาร์จไฟโทรศัพท์มือถือทั้ง '''N''' เครื่องในเวลาเดียวกัน บังเอิญยิ่งนัก ในบ้านของเขาก็มีรูปลั๊กไฟทั้งสิ้น '''N''' รูเช่นเดียวกัน ในการที่จะตั้งค่าปลั๊กไฟทั้งหมดนั้น จะใช้ มาสเตอร์สวิตช์ซึ่งมีปุ่มอยู่ '''L''' ปุ่ม โดยสวิทช์ ตัวที่ '''i''' จะทำการสลับ บิทที่ '''i''' ของปลั๊กไฟทุกรูในบ้าน
 เช่น
   ปลั๊กไฟ 0: 10
   ปลั๊กไฟ 1: 01
   ปลั๊กไฟ 2: 11
 เมื่อปรับสวิทช์ตัวที่ 2 ผลลัพธ์ที่ได้คือ
   ปลั๊กไฟ 0: 1'''1'''

@@ แถว 11: / แถว 11: @@
-ปลั๊กไฟ 0: 10
+ ปลั๊กไฟ 0: 10
+ ปลั๊กไฟ 1: 01
+ ปลั๊กไฟ 2: 11
@@ แถว 23: / แถว 19: @@
-ปลั๊กไฟ 0: 11
+ ปลั๊กไฟ 0: 1'''1'''
+ ปลั๊กไฟ 1: 0'''0'''
+ ปลั๊กไฟ 2: 1'''0'''
 ถ้าโชตะมี smartphone ึ่งใช้กระแสแบบ "11" และ tablet ซึ่งใช้กระแสแบบ "10" รวมทั้งแลบท๊อปที่ใช้กระแสแบบ "00" การสับสวิทซ์ที่ 2 จะทำให้เค้ามีความสุขถึงขั้นสุดยอด
@@ แถว 35: / แถว 27: @@
 โชตะได้ทำการจ้างมิซากิมาเพื่อแก้ไขปัญหานี้โดยเฉพาะ โดยเธอเป็นช่างไฟฟ้า ที่มีหน้าที่วัดไฟ และปรับสวิทช์ไฟภายในบ้าน ให้คุณตัดสินให้เธอทีว่า เป็นไปได้มั้ยที่โชตะจะปรับแต่งสวิทช์ไฟตามที่เขาต้องการ ถ้าเป็นไปได้ เขาจะต้องปรับแต่งน้อยที่สุดกี่ครั้ง เนื่องจากสวิทช์มีขนาดใหญ่มาก โชตะจึงไม่อยากให้มิซากิต้องปรับแต่งสวิทช์ จำนวนมากเกินกว่าที่เธอต้องทำ
-ข้อมูลนำเข้า
+'''ข้อมูลนำเข้า'''
 บรรทัดแรก ให้จำนวนเทสทั้งหมด '''T''' ตามด้วย '''T''' เทสเคส
@@ แถว 43: / แถว 35: @@
 บรรทัดที่ 3 ให้สตริงขนาด '''L''' ซึ่งแทนกระแสไฟที่อุปกรณ์ของเขาต้องการทั้งหมด '''N''' ตัว
-ข้อมูลส่งออก
+'''ข้อมูลส่งออก'''
 ในแต่ละเทส ให้แสดง หนึ่งบรรทัดในรูปแบบ "Case #x: y" โดย '''x''' แทนหมายเลขเทส เริ่มต้นจาก 1 และ '''y''' แทนจำนวนสวิทช์น้อยที่สุดที่มิซากิต้องสลับ เพื่อให้โชตะชาร์จไฟได้ ถ้าโชตะไม่มีวันชาร์จไฟได้ '''y''' จะเป็น string "NOT POSSIBLE"
-ข้อจำกัด
+'''ข้อจำกัด'''
 <= '''T''' <= 100

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 01:43, 26 เมษายน 2557
แถว 187:		แถว 187:

	โชคดี!		โชคดี!
−
−	~~== 4 ==~~

@@ แถว 67: / แถว 67: @@
 <= '''L''' <= 40
-== 2 ==
+== Problem B. Full Binary Tree ==
 ต้นไม้ก็คือกราฟที่ไม่มี cycle

@@ แถว 132: / แถว 132: @@
 ใน test case สุดท้าย เราสามารถลบปม 1 แล้วเลือกปม 3 เป็นรากของต้นไม้ไบนารี่แบบเต็มได้ (อีกกรณีหนึ่งคือเราสามารถลบปม 4 แล้วเลือก 2 เป็นรากก็ได้)
-== 3 ==
+== Problem C. Proper Shuffle ==
 ''permutation'' ขนาด N เป็นลำดับของจำนวน N ตัว แต่ละตัวมีค่าระหว่าง 0 ถึง N-1 โดยที่แต่ละตัวปรากฏแค่หนึ่งครับ และสามารถปรากฏในลำดับใดก็ได้

@@ แถว 60: / แถว 60: @@
 <= '''N''' <= 10
 <= '''L''' <= 10
 เทสใหญ่

@@ แถว 63: / แถว 63: @@
 <= T <= 100
 <= xi, yi <= N
 รับประกันว่าแต่ละ test case เป็นต้นไม้ที่ต่อถึงกันแน่นอน
-ชุดข้อมูลทดสอบเล็ก
+==== ชุดข้อมูลทดสอบเล็ก ====
 <= N <= 15
-ชุดข้อมูลทดสอบใหญ่
+==== ชุดข้อมูลทดสอบใหญ่ ====
 <= N <= 1000
 === ตัวอย่าง ===
+==== ข้อมูลนำเข้า ====
@@ แถว 95: / แถว 93: @@
 4
-=== ข้อมูลส่งออก ===
+==== ข้อมูลส่งออก ====
   Case #1: 0
   Case #2: 2
   Case #3: 1
 === อธิบายตัวอย่าง ===

@@ แถว 1: / แถว 1: @@
-== 1 ==
+== Charing Chaos   ==
 == 2 ==
 ต้นไม้ก็คือกราฟที่ไม่มี cycle

@@ แถว 77: / แถว 77: @@
 ด้านล่างเป็นโค้ดที่เป็นไปได้แบบหนึ่งที่จะทำงานนี้  (เราจะเรียกมันว่า ''good'' algorithm ต่อไป)
-(ดูในโจทย์ภาษาอังกฤษ)
+(ดูในโจทย์ภาษาอังกฤษประกอบด้วย)
-ในโค้ดด้านบน <tt>readint(a .. b)</tt> จะคืนค่าจำนวนเต็มที่สุ่มแบบ uniform จาก a ถึง b (รวม a และ b ด้วย)
+ for k in 0 .. N-1:
 นี่คืออัลกอริทึมนั้นถ้าอธิบายเป็นภาษาพูด: เราเริ่มที่ ''identity'' permutation จากนั้น for each k ตั้งแต่ 0 ถึง N-1 (inclusive), เราจะสุ่มเลือกจำนวนเต็ม pk แบบเป็นอิสระและ uniform จาก k ถึง N-1 (inclusive) และสลับข้อมูลตำแหน่งที่ k กับตำแหน่งที่ pk (ดัชนีเริ่มที่ 0)
@@ แถว 87: / แถว 93: @@
 1 2 3
-(ดูต่อในโจทย์ภาษาอังกฤษ)
+(ดูต่อในโจทย์ภาษาอังกฤษ -- โจทย์จะอธิบายการทำงานของ good algorithm)
 0 3 1
 กระบวนการดังกล่าวจบลง และเราจะได้ random permutation
@@ แถว 97: / แถว 103: @@
 ด้านล่างเป็นอัลกอริทึมในกลุ่มดังกล่าว  (เราจะเรียกว่าเป็น ''bad'' algorithm ต่อไป)
-(ดูโค้ดในภาษาอังกฤษ)
+(ดูโค้ดในภาษาอังกฤษประกอบด้วย)
 ในแต่ละ test case คุณจะได้รับ permutation ที่ถูกสร้างด้วยวิธีดังนี้: เราจะเริ่มจากการเลือกอัลกอริทึมจาก good algoroithm กับ bad algorithm ด้วยความน่าจะเป็น 50%.  จากนั้นเราจะสร้าง permutation ด้วยอัลกอริทึมนั้น.  คำถามคือคุณสามารถเดาได้หรือไม่ว่า อัลกอริทึมใดที่เราเลือก โดยดูจาก permutation ที่ถูกสร้างขึ้นมา