Facebook Hacker Cup 2020: Qualification Round

เง้ออออ แค่คิดว่าอยากจดไว้บ้างว่าแข่งอะไร โจทย์เป็นยังไง แล้วเราแก้โจทย์ยังไง ฉลาดขึ้นบ้างหรือเปล่าในการแข่งแต่ละครั้ง เพราะที่ผ่านมาไม่ได้ track อะไรแบบนี้เลย เล่าก่อนว่า Facebook Hacker Cup รอบ Qualification เปิดให้แข่ง 72 ชั่วโมง ทำโจทย์ผ่านอย่างน้อย 1 ข้อจะได้เข้ารอบถัดไป เรื่องมันมีอยู่ไว้ ลงไว้แล้วเกือบลืม ผ่าม 555555 แต่มีคนใจดี Padungkiat Tamasee ทักมาตอน 2 ทุ่ม ตามภาพด้านล่าง

ขอบคุณจริงๆ ไม่งั้นเหงาจ้อนน

มันคืออีก 4 ชั่วโมงหมดเวลา ละมีนัดเล่นเกมอีก สรุปเล่นเสร็จ 3 ทุ่มเหลือ 3 ชั่วโมงถ้วน เด็กโง่เอ้ย 55555 แต่มันไม่ได้จริงๆ น้าา กิจกรรมนี้ในเกมมันต้องทำพร้อมกับคนอื่นอีก 11 คน มันไม่ได้จริงจริ๊ง (ความจริงแค่ไม่อยากปฏิเสธแหละ เพราะรับปากไปแล้ว แหะๆ) เอาเป็นว่า ตอนนี้เราเหลือเวลาทำ 3 ชั่วโมง เราจะสู้วววว

ทุกคนสามารถเข้าไปดูโจทย์ได้นะงับ https://www.facebook.com/codingcompetitions/hacker-cup/2020/qualification-round link นี้เลยโจทย์มีอยู่ 5 ข้อ

ถ้าใครยังไม่อยากโดนสปอย ให้ไปทำมาก่อนค่อยกลับมาอ่านก็ได้งับ เริ่มกันที่ข้อแรกเลยดีกว่า

A: Travel Restrictions

แค่ 10 แต้มเองง คะแนนมันเต็ม 100 มันต้องจ้อนละป่ะ ก็อ่านโจทย์ไปเลยจ้า อ่านไปๆ มีทดนิดหน่อย ละก็ไปทำเลย ตอนแรกอ่านไม่จบด้วย คิดว่าเข้าใจดีแล้ว อันนี้ไม่ดีเลย อย่าทำตามนะ สรุปก็คือข้อนี้ให้หาว่า ถ้าเป็นเรามาจากประเทศที่ i จะไปประเทศไหนได้บ้าง แต่ว่าจะมี direct flight แค่ |i−j|=1 สมมติว่า i ไป j ได้ และ j ไป k ได้ก็จะบอกว่า i ไป k ได้เหมือนกันประมาณนี้ input จะมีอยู่ 3 อย่างคือ จำนวนประเทศ, I คือ incoming flight จะเข้าประเทศที่ i ได้ป่าว และ O คือ flight จากประเทศ i จะเข้าประเทศอื่นได้ป่าว

สมมติ

5
YNNYY #I
YYYNY #O

ประเทศที่ 1, 4, 5 ให้ flight จากประเทศอื่นเข้าได้ ส่วนประเทศที่ 2, 3 ไม่ให้เข้า

ประเทศที่ 1, 2, 3, 5 flight จากประเทศตัวเองเข้าประเทศอื่นได้ ส่วน 4 เข้าไม่ได้

output ของประเทศที่ 1 จะได้เป็น

YNNNN 

หมายความว่า 1 ไป 1 ได้ แต่ 1 ไป 2 ไม่ได้เพราะว่า 2 เป็นประเทศที่ไม่ให้ flight จากประเทศอื่นเข้า

output ทั้งหมดจะเป็น

YNNNN
YYNNN
NNYYN
NNNYN
NNNYY

วิธีทำเค้าคือ ทำ loop 2 รอบ รอบแรกดูก่อนว่าไปประเทศข้างๆ ได้ป่าว แล้วก็ mark ไว้ หลังจากนั้นทำอีกรอบนึงเป็น loop ที่บอกว่าสมมติว่าเจอ mark ประเทศที่ไปได้ละ ค่อยๆ -1 กับ +1 ไปเรื่อยๆ ว่าประเทศที่เราไปออกได้ป่าว ประเทศถัดไปเข้าได้ป่าว เพียงเท่านี้เราก็จะได้ครบตามที่โจทย์ต้องการ เขินจังต้องแปะโค้ดด้วยสินะ

ข้อแรกคิดว่าไม่ยากมาก แต่ทำนาน เพราะอ่านโจทย์ผิด แหะๆ ตอนแรกคิดว่าไปประเทศที่ไม่ใช่ ±1 ไม่ได้ ทำตั้งนาน นิทานเรื่องนี้สอนให้รู้ว่า ภาษาอังกฤษสำคัญนะเด็กๆ อ่อ ความจริง facebook ก็มี solution ให้อ่านนะ ลองเข้าไปอ่านกันได้งับ

B: Alchemy

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

hmmm มันดูจะเข้าเค้าแปลกๆ น้าาาา

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

จริงเฉยยยยยย

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