USACO Feb 2012

Problem 1: Cow Coupons [Neal Wu and Mark Gordon, 2012]

Source: USACO

ชาวนาจอห์นต้องการวัวเพิ่ม! มีวัว N ตัวที่พร้อมจะขาย (1 <= N <= 50,000), และ ชจ. จะต้องใช้เงินไม่เกิน M หน่วย (1 <= M <= 10^14)  วัวตัวที่ i มีราคา P_i หน่วย (1 <= P_i <= 10^9) แต่ ชจ. มีคูปอง K ใบ (1 <= K <= N), เมื่อใช้คูปองแล้ว วัวตัวที่ i จะมีราคาเหลือ C_i แทนที่จะเป็น P_i (1 <= C_i <= P_i)  ชจ สามารถใช้คูปองหนึ่งใบกับวัวหนึ่งตัวเท่านั้น

ชจ.จะสามารถซื้อว่ามาได้ทั้งหมดมากที่สุดกี่ตัว


Problem 2: Symmetry [Brian Dean, 2012]

Source: USACO

หลังจากที่ได้ลงเรียนวิชาศิลปะสมัยใหม่ ชาวนาจอห์น เริ่มสนใจที่จะหารูปแบบเชิงเรขาคณิตในทุก ๆ อย่างในฟาร์มของเขา  เขาได้หาตำแหน่งของวัวทุกตัวจำนวน N ตัว (2 <= N <= 1,000) ในฟาร์มของเขา แต่ละตัวจะมีตำแหน่งที่แตกต่างกันบนระนามสองมิติ  เขาสงสัยว่าจะมีเส้นสมมาตรกี่เส้นสำหรับเซตของจุดนี้  (เส้นสมมาตรคือเส้นตรงที่จุดที่อยู่สองด้านของเส้นเป็นภาพสะท้อนกันและกัน)

ช่วย ชจ. หาคำตอบนี้ด้วย


Problem 3: Nearby Cows [Neal Wu and Eric Price, 2011]

Source: USACO

ชาวนาจอห์นสังเกตว่าเหล่าวัวมักย้ายที่ไปมาระหว่างสนามที่อยู่ใกล้ ๆ กัน  ด้วยเหตุนี้ เขาต้องการปลูกหญ้าในแต่ละสนามให้มากพอไม่เฉพาะสำหรับวัวที่อยู่ในสนามนั้นเท่านั้น แต่รวมวัวในสนามหญ้าอื่น ๆ ข้างเคียงด้วย

กล่าวคือ ฟาร์มของชจ. มีสนามรวมทั้งสิ้น N สนาม (1 <= N <= 100,000) ที่บางคู่ของสนามจะเชื่อมต่อกันด้วยทางเดินที่เดินได้สองทิศทาง (จำนวน N-1 เส้น)  ชจ. ได้ออกแบบฟาร์มโดยรับประกันว่าระหว่างสองสนาม i และ j ใด ๆ จะมีเส้นทางที่ประกอบด้วยลำดับของทางเดินเชื่อมระหว่าง i และ j หนึ่งเส้นทาง  สนาม i เป็นบ้านของวัวจำนวน C(i)  ตัวแต่บางครั้งวัวก็อาจจะเดินไปยังสนามอื่น ๆ โดยเดินผ่านทางเดินจำนวน K เส้น (1 <= K <= 20)

ชจ.ต้องการปลูกหญ้าที่สนามที่ i ให้มากพอที่จะรองรับจำนวนวัวที่มากที่สุด M(i) ที่สามารถเดินมาในสนามนี้ได้  ให้โครงสร้างของสนามของชจ. และค่า C(i) ของทุก ๆ สนาม i, ช่วย ชจ. คำนวณค่า M(i) สำหรับทุกสนาม i ด้วย

Advertisements

USACO Jan 2012

Problem 1: Video Game Combos [Neal Wu, 2012]

Source: USACO

เบซซี่กำลังเล่นวิดีโอเกม ในเกมนี้ ตัวอักษร ‘A’, ‘B’, และ ‘C’ เป็นปุ่มที่กดได้เท่านั้น  เบซซี่สามารถกดปุ่มเหล่านี้ในลำดับใด ๆ ก็ได้ที่เธอชอบ อย่างไรก็ตาม จะมีรูปแบบคอมโบที่เป็นไปได้แตกต่งกันทั้งสิ้น N รูปแบบ  (1 <= N <= 20) คอมโบที่ i จะแสดงด้วยสตริง S_i ที่มีความยาวระหว่าง 1 ถึง 15 ที่ประกอบด้วยตัวอักษร ‘A’, ‘B’ หรือ ‘C’

เมื่อใดที่เบซซี่กดปุ่มแล้วได้รูปแบบตรงกับคอมโบ เธอจะได้รับคะแนนหนึ่งแต้มสำหรับคอมโบนั้น คอมโบสามารถซ้อนทับกันได้ หรือกระทั่งกดเสร็จได้พร้อมกัน  ยกตัวอย่างเช่น ถ้า N = 3 และคอมโบที่เป็นไปได้คือ “ABA”, “CB”, และ “ABACB”  ถ้าเบซซี่กด “ABACB” เธอจะได้คะแนน 3 แต้ม  เบซซี่สามารถได้คะแนนจากบางคอมโบได้มากกว่าหนึ่งครั้ง

แน่นอนที่เบซซี่ต้องการจะได้คะแนนให้ได้เร็วที่สุดเท่าที่จะทำได้ ถ้าเธอกดปุ่ม K ปุ่ม (1 <= K <= 1,000) คะแนนมากที่สุดที่เธอทำได้เป็นเท่าใด?


Problem 2: Cow Run [Mark Gordon, 2011]

Source: USACO

ชาวนาจอห์นและเบซซี่ได้คิดค้นเกมสำหรับออกกำลังกายแบบใหม่สำหรับวัว  เหล่าวัวจะวิ่งบนลู่วิ่งวงกลมความยาว M (2 <= M <= 1,000,000,000) โดยเริ่มจากจุดเริ่มต้นเดียวกัน  เกมจะดำเนินไป N รอบ (1 <= N <= 14) และใช้สำรับไพ่ขนาด 8N ใบ ที่แต่ละใบมีหมายเลข X_i (0 <= X_i < M) เขียนอยู่

ในแต่ละรอบ ชจ. จะแยกไพ่ด้านบนสุด 8 ใบไปยังกองไพ่ใหม่ จากนั้นจะเลือกไพ่ 4 ใบด้านบน หรือ 4 ใบด้านล่างให้เบซซี่นำไปเล่น  เบซซี่จะเลือกไพ่ด้านบน 2 ใบ หรือด้านล่าง 2 ใบจากไพ่ 4 ใบที่ ชจ. เลือก หลังจากนั้น ชจ. จะอ่านจำนวน X_top บนไพ่ใบบน และเหล่าวัวจะวิ่งไปเป็นระยะทาง R*X_top, โดยที่ R คือระยะทางที่วัววิ่งมาแล้ว.  เบซซี่ก็จะอ่านจำนวน X_bottom ที่อยู่ที่ไพ่ใบล่าง และเหล่าวัวก็จะวิ่งไปอีกเป็นระยะทาง X_bottom

ชจ. เป็นห่วงว่าหลังจากการออกกำลังกาย เหล่าวัวจะเหนื่อยเกินไปที่จะกลับไปที่จุดเริ่มต้นของลู่วิ่งถ้าพวกมันไปหยุดที่จุดที่ห่างไกลเกินไป  เขาเชื่อว่าถ้าวัวไปหยุดที่ระยะทางมากกว่า K (0 <= K <= floor(M/2)) จากจุดเริ่มต้น พวกมันจะไม่สามารถกลับบ้านได้

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


Problem 3: Bovine Alliance [Mark Gordon, 2011]

Source: USACO

เบซซี่และเพื่อนของเธอในฟาร์มใกล้ ๆ กันได้ตกลงว่าจะเชื่อมฟาร์มเข้าด้วยกันด้วยทางเดินเพื่อเป็นการสร้างพันธมิตรที่ต่อต้านเหล่าเหล่าชาวนา  เหล่าวัวในฟาร์มจำนวน N ฟาร์ม (1 <= N <= 100,000) ได้รับคำสั่งให้สร้างทางเชื่อมไปยังอีกหนึ่งฟาร์มพอดี (หนึ่งฟาร์มเท่านั้น ไม่มากไม่น้อยกว่านี้) ทำให้มีจำนวนทางเดินที่จะสร้างทั้งสิ้น N ทางเดิน อย่างไรก็ตาม ผ่านไปหลายเดือน ทางเดินที่สร้างเสร็จมีเพียงแค่ M ทางเท่านั้น (1 <= M < N)

ข้อถกเถียงระหว่างฟาร์มว่าฟาร์มใดสร้างทางไม่เสร็จแทบจะทำให้พันธมิตรแทบแตกสลาย  เพื่อลดความตึงเครียด เบซซี่ต้องการที่จะคำนวณหาจำนวนวิธีที่เป็นไปได้ที่ทางที่สร้างแล้ว M เส้นนี้จะถูกสร้างโดยฟาร์มใด  ยกตัวอย่างเช่น ถ้ามีทางเชื่อมระหว่างฟาร์ม 3 และ 4  ความเป็นไปได้หนึ่งก็คือฟาร์ม 3 สร้างทางเชื่อม อีกความเป็นไปได้หนึ่งก็คือฟาร์ม 4 สร้างทางเชื่อม  ช่วยเบซซี่คำนวณจำนวนวิธีที่จะกำหนดทางเชื่อมให้กับฟาร์มที่เป็นคนสร้าง (modulo 1,000,000,007)   วิธีสองวิธีจะแตกต่างกันถ้ามีอย่างน้อยหนึ่งเส้นทางที่ถูกเลือกฟาร์มที่สร้างที่แตกต่างกัน

 

USACO Dec 2011

Problem 1: Cow Photography [Brian Dean, 2011]

Source: usaco

วันนี้เหล่าวัวอยู่ในอารมณ์ซุกซน! ชาวนาจอห์นเพียงแค่ต้องการจะถ่ายรูปเหล่าวัวที่ยืนเป็นแถว แต่พวกวัวก็จะขยับก่อนที่เขาจะได้มีโอกาสกดถ่ายรูป

กล่าวคือ ชจ. มีวัวทั้งสิ้น N ตัว (1 <= N <= 20,000) วัวแต่ละตัวของ ชจ. จะมีหมายเลขประจำตัวเป็นจำนวนเต็มที่ไม่ซ้ำกัน  ชจ. ต้องการจะถ่ายรูปวัวยืนเป็นแถวในลำดับที่ต้องการ ซึ่งลำดับนี้จะระบุด้วยข้อมูลที่อยู่ในอาร์เรย์ A[1…N] โดยที่ A[j] ระบุหมายเลขประจำตัวของวัวลำดับที่ j ในแถว  ชจ.ได้จัดแถววัวตามลำดับนี้ แต่ก่อนที่เขาจะมีโอกาสได้กดถ่ายรูป กลุ่มของวัว (0 ตัวหรือมากว่านั้น, ไม่จำเป็นต้องยืนติดกัน) ก็จะย้ายตำแหน่งไปยังตำแหน่งใหม่ในแถว  กล่าวโดยละเอียดก็คือ กลุ่มของวัวกลุ่มหนึ่งจะเดินออกมาจากแถว วัวที่เหลือในแถวจะขยับไปติดกัน จากนั้นวัวที่ยืนออกมาจากแถวจะเดินเข้าไปแทรกในตำแหน่งต่าง ๆ ในแถว (ไม่จำเป็นต้องเป็นตำแหน่งเดิม)  ถึงแม้จะสับสน แต่ ชจ. ก็ไม่ย่อท้อ เขาจัดแถววัวใหม่ตามลำดับ A แต่ก็เช่นเคย ก่อนที่เขาจะได้ถ่ายรูป กลุ่มของวัวกลุ่มใหม่ก็จะย้ายตำแหน่งในแถวอีก

กระบวนการดังกล่าวเกิดขึ้นทั้งสิ้น 5 รอบ (และ ชจ. พลาดกดถ่ายรูปไปทุกครั้ง) ก่อนที่ ชจ. จะถอดใจ  ให้ข้อมูลของแต่ละรูปภาพ ให้คุณหาว่าคุณจะสามารถสร้างลำดับ A ที่ชจ.ต้องการได้หรือไม่   รูปภาพแต่ละรูปแสดงลำดับของวัวที่แตกต่างจาก A เนื่องจากกลุ่มของวัว (0 ตัวหรือมากกว่านั้น) ได้ย้ายที่  อย่างไรก็ตาม วัวหนึ่งตัวจะสามารถย้ายที่ได้แค่ในรูปเพียงรูปเดียวเท่านั้น: ถ้าวัวตัวใดอยู่ในกลุ่มที่มีการย้ายที่ในรูปภาพรูปหนึ่งแล้ว เธอจะไม่ย้ายที่อีกในรูปอื่น ๆ (แต่เธออาจจะอยู่ตำแหน่งที่ไม่ตรงกับตำแหน่งใน A ได้ ซึ่งเป็นผลจากที่วัวตัวอื่น ๆ ขยับ)


Problem 2: Simplifying the Farm [Nathan Pinsker, 2011]

Source: usaco

ชาวนาจอห์นได้ไปเรียนวิชาอัลกอริทึมภาคค่ำที่มหาวิทยาลัยแถวฟาร์มของเขา เขาเพิ่งได้เรียนเกี่ยวกับ minimum spanning tree  ซึ่งทำให้เขาได้ตระหนักว่า การออกแบบฟาร์มของเขานั้นมันไม่มีประสิทธิภาพอย่างที่ควรจะเป็น เขาต้องการจะทำให้แผนผัง (layout) ของฟาร์มง่ายขึ้น

ฟาร์มปัจจุบันนั้นมีลักษณะเป็นกราฟ ที่มีจุดยอดแทนสนาม และเส้นเชื่อม แทนทางเดินระหว่างสนามเหล่านี้ ทางเดินทุกเส้นมีความยาวระบุอยู่  ชาวนาจอห์นสังเกตว่าสำหรับความยาวค่าใด ๆ จะมีทางเดินไม่เกินสามทางที่มีค่าความยาวนี้  ชจ.ต้องการลบทางเดินในฟาร์มทิ้งเพื่อให้แผนผังกลายเป็นต้นไม้ (tree)   นั่นคือ สำหรับสนามคู่ใด ๆ จะมีเส้นทางเดินเพียงเส้นทางเดียวเท่านั้น  กล่าวคือ ชาวนาจอห์นต้องการให้ฟาร์มของเขาเป็น minimum spanning tree (ต้นไม้ที่มีผลรวมของความยาวเส้นเชื่อมน้อยที่สุด)

ช่วยชาวนาจอห์นหาความยาวของ minimum spanning tree พร้อมกับคำนวณว่าจำนวนของ minimum spanning tree ที่เป็นไปได้ทั้งหมด มีกี่แบบ


Problem 3: Grass Planting [Travis Hance, 2011]

Source: usaco

ชาวนาจอห์นมีทุ่งหญ้าเลี้ยงสัตว์ที่แห้งแร้งอยู่ N ทุ่ง (2 <= N <= 100,000) เชื่อมต่อกันด้วยถนนสองทางจำนวน N-1 เส้น ในรูปแบบที่ทำให้มีเส้นทางเชื่อมระหว่างทุ่งหญ้าสองทุ่งใดๆ หนึ่งทาง    เบซซี่เป็นวัวที่ชอบกินหญ้ามาก ๆ มักจะชอบบ่นว่าไม่มีหญ้าให้กินบนเส้นทางเชื่อมระหว่างทุ่งหญ้าเลย  ชาวนาจอห์นรักเบซซี่มาก และวันนี้ล่ะ จะเป็นวันที่เขาจะเริ่มปลูกหญ้าบนถนน  เขาจะดำเนินการดังกล่าวเป็นขั้น ๆ จำนวน M ขั้น (1 <= M <= 100,000)

แต่ละขั้น มีเหตุการณ์เกิดขึ้นได้สองแบบ:

  • ชจ. จะเลือกทุ่งหญ้าสองแห่ง จากนั้นจะปลูกหญ้าหนึ่งผืนในถนนทุก ๆ เส้นระหว่างทุ่งหญ้าทั้งสองนั้น
  • เบซซีจะเลือกถนนมาหนึ่งเส้น และถาม ชจ. ว่ามีหญ้ากี่ผืนในถนนเส้นนั้น

ชาวนาจอห์นความจำไม่ค่อยจะดี — ช่วยเขาตอบคำถามของเบซซี่ด้วย!

USACO Nov 2011

Problem 1: Above the Median [Brian Dean]

Source: [1]

ชาวนาจอห์นได้ให้วัว N ตัวของเขายืนเรียงเป็นหน้ากระดาน (1 <= N <= 100,000) เพื่อที่จะวัดส่วนสูง; วัวที่ i มีความสูง H_i (1 <= H_i <= 1,000,000,000) นาโนเมตร (ชจ.เชื่อในการวัดที่แม่นยำ!!) เขาต้องการจะถ่ายรูปของลำดับย่อยที่ต่อเนื่องกันของวัว เพื่อที่จะส่งประกวดภาพถ่ายที่งานประจำเมือง

งานดังกล่าวมีเงื่อนไขแสนประหลาดในการส่งภาพถ่าย: ภาพถ่ายจะใช้ส่งประกวดได้เมื่อเป็นภาพถ่ายที่แสดงกลุ่มของวัวที่ความสูง มัธยฐานไม่น้อยกว่าค่าขอบเขต X ค่าหนึ่ง (1 <= X <= 1,000,000,000)

สำหรับโจทย์นี้ เรานิยามมัธยฐานของอาร์เรย A[0…K] ให้เป็น A[ceiling(K/2)] หลังจากที่ A ถูกจัดเรียงแล้ว เมื่อ ceiling(K/2) ให้ค่า K/2 ปัดขึ้นไปยังจำนวนเต็มที่ใกล้ที่สุด (หรือ K/2 เองถ้า K/2 นั้นเป็นจำนวนเต็มอยู่แล้ว) ตัวอย่างเช่น มัธยฐานของ {7,3,2,6} คือ 6 และ มัธยฐานของ {5,4,8} คือ 5

ช่วย ชจ. นับจำนวนลำดับย่อยที่ต่อเนื่องกันของวัวที่สามารถถ่ายเป็นรูปที่สามารถส่งประกวดได้


 

Problem 2: Binary Sudoku [Brian Dean]

Source: [2]

วัวของชาวนาจอห์นชอบเล่นเวอร์ชันหนึ่งของเกม “Sudoku” เวอร์ชันนี้มีตารางขนาด 9 x 9 ที่ประกอบไปด้วยกริดย่อยขนาด 3 x 3 เหมือน Sudoku ปกติ แต่ในเวอร์ชันของวัวจะเป็นเลขฐานสอง:

000 000 000 
001 000 100 
000 000 000 

000 110 000 
000 111 000 
000 000 000 

000 000 000 
000 000 000 
000 000 000 

เป้าหมายของ Sudoku ฐานสองคือการสลับบิตจำนวนน้อยที่สุดเพื่อให้ทุก ๆ แถว ทุก ๆ คอลัมน์ และทุก ๆ กริดย่อยขนาด 3 x 3 จะต้องมีค่าพาริตี้เป็นคู่ (นั่นคือมีจำนวน 1 เป็นจำนวนคู่) ตัวอย่างเช่น จากด้านบนถ้าเราสลับบิตจำนวน 3 บิต จะทำให้ได้คำตอบหนึ่งที่ถูกต้อง

000 000 000 
001 000 100 
001 000 100 

000 110 000 
000 110 000 
000 000 000 

000 000 000 
000 000 000 
000 000 000 

ให้สถานะตั้งต้นของ Sudoku ฐานสอน ให้หาจำนวนครั้งที่น้อยที่สุดที่ต้องสลับบิตเพื่อแก้ตาราง Sudoku นี้


 

Problem 3: Cow Steeplechase [Brian Dean]

Source: [3]

ชาวนาจอห์นมีไอเดียชั้นยอดสำหรับกีฬาที่ดึงดูดใจผู้ชม: การแข่งขี่วัวข้ามสิ่งกีดขวาง (Cow Steeplechase) อย่างที่หลาย ๆ คนทราบ การแข่งขี่ม้าข้ามสิ่งกีดขวาง (steeplechase) นั้นจะมีกลุ่มของม้าที่วิ่งไปมาบนสนามแข่งที่มีสิ่งกีดขวางที่ม้าจะต้อง กระโดดข้ามให้ได้ ชจ.คิดว่าการแข่งขันรูปแบบเดียวกันจะใช้ได้สำหรับวัวที่ผ่านการฝึกมาอย่างดี แล้ว เมื่อสิ่งกีดขวางนั้นไม่สูงจนเกินไป

เพื่อที่จะออกแบบสนามแข่ง ชจ.ได้ตระเตรียมวาดแผนผังที่แสดงสิ่งกีดขวางที่เขาอาจจะสร้างได้ทั้งหมด N ชิ้น (1 <= N <= 250) แต่ละชิ้นแสดงเป็นส่วนของเส้นตรงในระนามสองมิติ ขนานกับแกน x หรือแกน y สิ่งกีดขวางที่ i จะมีจุดปลายสองจุดที่แตกต่างกัน (X1_i, Y1_i) และ (X2_i, Y2_i) (1 <= X1_i, Y1_i, X2_i, Y2_i <= 1,000,000,000) ตัวอย่างแสดงดังด้านล่าง:

steeple-fig1

ชจ.ต้องการที่สร้างสิ่งกีดขวางนี้ให้มากที่สุด แต่ต้องไม่ให้สิ่งกีดขวางคู่ใด ๆ ตัดกัน (intersect) จากแผนผังด้านบน ชจ. สามารถสร้างสิ่งกีดขวางได้ 7 ชิ้น:

steeple-fig2

ส่วนของเส้นตรงสองเส้นจะเรียกว่าตัดกัน (intersect) ถ้ามีการใช้จุดใด ๆ ร่วมกัน ซึ่งรวมถึงจุดปลายของบางเส้นหรือของทั้งสองเส้น ชจ.มั่นใจว่าไม่มีคู่ของส่วนของเส้นตรงในแกนนอนใด ๆ ในข้อมูลนำเข้าที่ตัดกัน และในทำนองเดียวกัน ไม่มีคู่ของส่วนของเส้นตรงในแนวตั้งใด ๆ ที่ตัดกัน

ช่วย ชจ. หาว่าจำนวนสิ่งกีดขวางที่มากที่สุดที่เขาสามารถสร้างได้ เป็นเท่าใด

ความสลับซับซ้อนในคำ

เรื่องสมมติทั้งนั้นนะครับ:

1. เด็กคนหนึ่ง ขโมยของไปให้มารดา

2. เด็กคนหนึ่ง ขโมยส้มแสนอร่อยจากบ้านขุนนาง ไปให้มารดา

3. เด็กคนหนึ่ง ขโมยส้มแสนอร่อยไปให้มารดาที่นั่งดูโทรทัศน์

4. เด็กคนหนึ่ง ขโมยอาหารไปให้มารดาที่ป่วยหนัก

5. เด็กคนหนึ่ง ขโมยยารักษาโรคไปให้มารดาที่ป่วยหนัก

6. เด็กคนหนึ่ง ขโมยส้มแสนอร่อยไปให้มารดาที่นั่งดูโทรทัศน์ จากนั้นเขาทำงานเก็บเงินนำไปชดใช้ค่าส้มที่ขโมยมานั้น

7. เด็กคนหนึ่ง ขโมยยารักษาโรคราคาแพงไปให้มารดาที่ป่วยหนัก จากนั้นเขาทำงานเก็บเงินนำไปชดใช้ค่ายารักษาโรคนั้น

8. เด็กคนหนึ่ง ลืมหยิบเงินไปที่ร้านอาหาร เลยขโมยอาหารไปให้มารดาที่ป่วยหนัก แล้วกลับมาที่ร้านอาหารเอาเงินมาชำระ

9. เด็กคนหนึ่ง ลืมหยิบเงินไปที่ร้านขายยา เลยขโมยยารักษาโรคไปให้มารดาที่ป่วยหนัก แล้วกลับมาที่ร้านอาหารเอาเงินมาชำระ

10. เด็กคนหนึ่ง ขโมยส้มแสนอร่อยไปให้มารดาที่นั่งดูโทรทัศน์ จากนั้นเขาทำงานเก็บเงินนำไปชดใช้ค่าส้มที่ขโมยมานั้น พร้อมด้วยดอกเบี้ย

11. เด็กคนหนึ่ง ขโมยยารักษาโรคราคาแพงไปให้มารดาที่ป่วยหนัก จากนั้นเขาทำงานเก็บเงินนำไปชดใช้ค่ายารักษาโรคนั้น พร้อมด้วยดอกเบี้ย

เด็กคนไหนบ้าง ที่คุณยอมรับได้ครับ ว่าเป็น “เด็กดี”?

ตัวอย่างเรื่องสมมติข้างต้น พยายามจะนำแนวคิดและพฤติกรรมหลายอย่างมาพบปะกัน เช่น แนวคิดเกี่ยวการเป็นคนดี แนวคิดเกี่ยวกับความกตัญญู ความซื่อสัตย์ การลักขโมย

ถ้าการเป็นเด็กดีนั้นหมายถึงการเป็นเด็กดี (ยังไม่ได้นิยาม) ไม่มีความด่างพร้อย เราอาจจะบอกได้ว่าเด็กในตัวอย่างด้านบนนั้น ย่อมไม่มีใครเป็นคนดีได้ เพราะว่าได้มีการขโมยของมาทุกคน

[นอกเรื่อง: อย่างไรก็ตาม ถ้าเราพยายามตั้งคำถามเข้าไปอีกว่า ความเชื่ออะไรทำให้เราสรุปว่าการขโมยของเป็นสิ่งไม่ดี? อาจจะเป็นความเชื่อในเรื่องของทรัพย์สินส่วนบุคคล ถ้าเราไม่เชื่อในเรื่องทรัพย์สินส่วนบุคคล และเด็กคนนั้นเป็นโรบินฮู้ด ปล้นคนรวยมาช่วยคนจน เราอาจจะยอมรับในเรื่องการขโมยก็ได้]

ในทางกลับกัน เราก็ต้องยอมรับว่า เด็กหลายคนในตัวอย่างสมมติด้านบน ก็ไม่ใช่เด็กที่ “ไร้คุณสมบัติ” ของการเป็นคนดีโดยสิ้นเชิง

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

เราลองพิจารณาตัวอย่างสมมติข้างต้นอีกสักหน่อย แต่ลองพิจารณาแค่ครึ่ง ๆ กลาง ๆ ดู กล่าวคือ เราจะตัดส่วนหลังออก

6a. เด็กคนหนึ่ง ขโมยส้มแสนอร่อยไปให้มารดาที่นั่งดูโทรทัศน์ จากนั้นเขาทำงานเก็บเงินนำไปชดใช้ค่าส้มที่ขโมยมานั้น

7a. เด็กคนหนึ่ง ขโมยยารักษาโรคราคาแพงไปให้มารดาที่ป่วยหนัก จากนั้นเขาทำงานเก็บเงินนำไปชดใช้ค่ายารักษาโรคนั้น

8a. เด็กคนหนึ่ง ลืมหยิบเงินไปที่ร้านอาหาร เลยขโมยอาหารไปให้มารดาที่ป่วยหนัก แล้วกลับมาที่ร้านอาหารเอาเงินมาชำระ

9a. เด็กคนหนึ่ง ลืมหยิบเงินไปที่ร้านขายยา เลยขโมยยารักษาโรคไปให้มารดาที่ป่วยหนัก แล้วกลับมาที่ร้านอาหารเอาเงินมาชำระ

10a. เด็กคนหนึ่ง ขโมยส้มแสนอร่อยไปให้มารดาที่นั่งดูโทรทัศน์ จากนั้นเขาทำงานเก็บเงินนำไปชดใช้ค่าส้มที่ขโมยมานั้น พร้อมด้วยดอกเบี้ย

11a. เด็กคนหนึ่ง ขโมยยารักษาโรคราคาแพงไปให้มารดาที่ป่วยหนัก จากนั้นเขาทำงานเก็บเงินนำไปชดใช้ค่ายารักษาโรคนั้น พร้อมด้วยดอกเบี้ย

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

ความดีไม่ดี หรือแนวคิดที่เป็นนามธรรมทั้งหลาย จริง ๆ มีความสลับซับซ้อนมากมาย แต่บางครั้งเรากล่าวถึงมันบ่อยโดยที่คิดว่าจริง ๆ แล้วมันมีแค่ขาวกับดำ (เป็นหรือไม่เป็น)  หรือบางครั้งเรากล่าวถึงแนวคิดดังกล่าวว่ามีเพียงแค่มิติเดียว (ขาว ไล่ไปเทา ไล่ไปดำ) แต่จริง ๆ แนวคิดดังกล่าวผูกผันกับแนวคิดอื่น ๆ แตกแขนงออกเป็นมิติของแนวคิดต่าง ๆ มากมาย

แม้ว่าความพยายามลดทอนความซับซ้อน ทำให้เราสามารถใช้ตรรกะเข้ามาพิจารณาและตัดสินใจได้ง่าย แต่บางครั้ง ตรรกะที่ตั้งอยู่บนภาพที่ถูกกรอบบางอย่างลดทอนความซับซ้อนลงมากนั้น อาจจะไม่ทำให้เราเข้าใจอะไรเกินไปกว่ากรอบของภาพดังกล่าวนั่นเอง

หลายปัจจัย

ร้านหมูปิ้งสองร้าน ร้านแรกอยู่หน้าบ้านของคุณ ขายหมูปิ้งไม้ละ 6 บาท  อีกร้านอยู่ปากซอย ห่างจากบ้านของคุณไป 500 เมตร ร้านที่สองขายหมูปิ้งไม้ละ 5 บาท

ถ้าหมูปิ้งทั้งสองร้านเหมือนกัน คุณจะซื้อหมูปิ้งร้านไหน?

ถ้าหมูปิ้งร้านที่สอง อร่อยกว่าหมูปิ้งร้านแรกมาก ๆ คุณจะเดินไปซื้อหรือไม่?  ถ้าร้านที่สองเปิดหน้าบ้านคุณเหมือนกันและอร่อยกว่า คุณจะซื้อที่ร้านแรกหรือร้านที่สอง?

สำหรับตัวอย่างที่ยกมา เรามีปัจจัยที่เราสนใจอยู่ 2 – 3 ปัจจัยในการเลือกซื้อหมูปิ้ง  ในคำถามแรกปัจจัยที่เราสนใจมีแค่ราคาหมูปิ้ง และระยะทางการเดินไปซื้อ

ในคำถามที่สอง ความอร่อยของหมูปิ้งเริ่มมีผล และเป็นอีกปัจจัยที่เราสามารถใช้เพื่อพิจารณา

ในบางปัญหาและเงื่อนไขที่เรากล่าวมาข้างต้น เรายากที่จะคาดเดาคำตอบ สังเกตว่าความไม่แน่นอนนี้ขึ้นกับจำนวนปัจจัยที่เราสนใจ

ถ้าเรามีแค่หนึ่งปัจจัย เช่น ถ้าเรามีร้านหมูปิ้งสองร้าน หมู่อร่อยเท่ากัน ตั้งอยู่ติดกัน แต่ร้านหนึ่งขาย 5 บาทต่อไม้ ในขณะที่อีกร้านขาย 6 บาทต่อไม้ เราคงตอบได้ไม่ยากว่าเราจะซื้อร้านที่ขาย 5 บาท

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

แต่สังเกตว่า ถ้าเรามีสองร้านที่มีข้อได้เปรียบ/เสียเปรียบ ที่ไม่ได้ชนะกันในทุก ๆ ปัจจัย การเลือกว่าจะซื้อร้านใดนั้น เราอาจจะต้องใช้ข้อมูลหรือความเชื่ออื่น ๆ ในการตัดสินใจ

เพื่อความชัดเจน ผมจะนำข้อมูลของร้านหมูปิ้งเขียนโดยใช้ตาราง และจะสนใจปัจจัยแค่ระยะทางกับราคา เพื่อความสนุกผมจะเพิ่มอีกร้านหนึ่งด้วย

ร้านที่ ระยะทางจากบ้าน
(เมตร – ยิ่งน้อยยิ่งดี)
ราคาหมูปิ้ง
(บาท – ยิ่งน้อยยิ่งดี)
1 10 6
2 500 5
3 1000 7

สำหรับร้านที่ 1 ถ้าเราลองนึกดูจะพบได้ว่ามีหลายเหตุผลที่ทำให้เราซื้อหมูปิ้งจากร้านที่ 1 ตั้งแต่ว่าเราไม่ชอบเดินไกล, จากบ้านไปปากซอยมีสุนัขดุ จนกระทั่งสำหรับเราแล้วเงิน 6 บาทกับ 5 บาทมีมูลค่าไม่แตกต่างกัน

สำหรับร้านที่ 2 ก็เช่นเดียวกัน  ถ้าเรามีเงินติดตัวแค่ 5 บาท ต่อให้ไม่อยากเดินไกล ต้องฝ่าฟันสุนัขดุ ถ้าเราจะกินหมูปิ้ง ก็ต้องยอมเดิน  หรือถ้าเดินไกล ๆ จนเป็นเรื่องปกติอยู่แล้ว ร้านที่ 2 นี่ย่อมเป็นร้านที่เรายิ่งถูกใจ

แต่สำหรับร้านที่ 3 ถ้าเราไม่คิดว่าการเดินเยอะ ๆ เป็นเรื่องดีกว่าเดินน้อย ๆ หรือการจ่ายเงินเยอะ ๆ เป็นเรื่องดีกว่าการจ่ายเงินน้อย ๆ เราก็จะไม่มีวันไปซื้อหมูปิ้งร้านที่ 3 เลย  (แต่ถ้าเราได้ข่าวว่าหมูปิ้งร้านที่ 1 และ 2 ทานไปแล้วท้องเดิน เราก็อาจจะยอมเดินไกล และจ่ายแพงเพื่อร้านที่ 3 ก็ได้)

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

จากการพิจารณาด้วยตัวอย่างง่าย ๆ นี้ ก็อาจจะพอช่วยให้เข้าใจได้ว่าทำไม ภายใต้เงื่อนไข ข้อจำกัดและความเชื่อที่แตกต่างกัน บางคนจึงเลือกของหรือทางเลือกบางอย่างที่เราคิดว่าไม่น่าจะมีใครอยากจะเลือกได้

ทำได้พอดี

cross post จาก wonam.tumblr.com

Daphne Koller (co-founder ของ Coursera) ใน TED Talk ที่เธอได้กล่าวถึงการเรียนการสอนออนไลน์และ Coursera ได้อ้างคำพูดของ Thomas Friedman ที่กล่าวว่า

Big breakthroughs happen when what is suddenly possible meets what is desperately necessary.

การเรียนการสอนออนไลน์สมัยใหม่ ในเว็บเช่น Coursera, Khan Academy, EdX, หรือ Udacity  (มักเรียกรวม ๆ ว่า MOOC – Massively Open Online Courses) ที่มีผู้เรียนจำนวนมากนั้นมีความแตกต่างจากการเรียนทางไกลสมัยก่อนที่เรียนทางโทรทัศน์ หรือการเรียนผ่านวิดีโอตามโรงเรียนกวดวิชาบ้านเรา

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

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

ผมคิดว่ามีประเด็นที่น่าสนใจ 2 ประเด็น

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

รูปแบบการเรียนการสอนที่ระบบออนไลน์พยายามจะเลียนแบบนั้น ผมเชื่อว่าทางนักวิจัยทางด้านศึกษาศาสตร์น่าจะมีการศึกษาและทดลองมาจนมากแล้ว

ใน TED Talk ข้างต้น Koller ได้กล่าวถึงงานวิจัยของ Benjamin Bloom ในปี 1984 ที่ได้เปรียบเทียบการเรียนการสอน 3 รูปแบบ คือแบบการบรรยาย (lecture-based classroom) การเรียนการสอนแบบบรรยายแต่มีเงื่อนไขว่าผู้เรียนต้องแสดงความเชี่ยวชาญในหัวข้อเดิมก่อนจะขึ้นหัวข้อใหม่ได้ (mastery-based approach) และแบบการเรียนการสอนแบบหนึ่งต่อหนึ่งกับผู้สอน   งานวิจัยดังกล่าวพบว่าการเรียนการสอนในแบบผู้เรียนต้องแสดงความเชี่ยวชาญจะให้ผลดีกว่าการเรียนการสอนแบบบรรยายธรรมดา และการเรียนการสอนแบบหนึ่งต่อหนึ่งจะให้ผลลัพธ์ดีกว่าทั้งสองวิธีอย่างมาก

ความเข้าใจว่าเทคโนโลยีสามารถทำอะไรได้ และในที่นี้รวมไปถึงความสามารถในการพัฒนาเทคโนโลยีให้รองรับกับเป้าหมาย  เมื่อมารวมกับความเข้าใจในเป้าหมาย (ที่ถ้าปราศจากเทคโนโลยีแล้วก็อาจจะเป็นแค่ความฝัน) ทำให้เกิดระบบการเรียนการสอนออนไลน์ที่มีการออกแบบเพื่อให้เกิดสภาวะใกล้เคียงกับการเรียนแบบหนึ่งต่อหนึ่งดังกล่าวมากขึ้น

2. ขณะนี้เราเข้าสู่ช่วงเวลาของการ personalization ของทุก ๆ อย่าง

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

ในกรณีของการเรียนข้างต้น การเลือกเนื้อหาได้เอง หรือในอนาคตก็เป็นไปได้ที่ระบบอาจจะแนะนำเนื้อหาเพิ่มเติมที่เหมาะสมให้กับผู้เรียนโดยอัตโนมัติ รวมทั้งการได้รับ feedback ที่เฉพาะเจาะจงกับผู้เรียน ก็เป็นส่วนหนึ่งของทิศทางนี้ด้วย

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