Facebook Hacker Cup Qualification Round เล่า solution ที่ส่งไป เย้

วนมาครบปีแล้วหรอเนี้ยยย กับ fb hacker cup ไวจังน้า

เผื่อใครไม่รู้จัก link นี้เลยงับ https://www.facebook.com/codingcompetitions/hacker-cup เป็นการแข่งเขียนโปรแกรมที่จัดโดย facebook ที่มีทุกๆ ปีเลยล่ะ เห็นโพสต์เพื่อนใน fb บอกว่าเริ่มแล้ว เราก็แบบ แง้ ลืมสมัคร อดแข่งเลย หลังจากนั้นวันนึง ก็มีเพื่อนคุยในแชทว่า ไม่แข่งอันนี้หรอ เราก็เลยกดเข้าไปดู อ่ออ มันลงได้ 5555 เค้าเปิดให้แข่ง 72 hr ตอนนั้นเหลือประมาณ 30 hr ก็เลยแบบ เดี๋ยวค่อยทำ ชิวววว เอาอะไรมามั่นใจ หลังจากเลิกงานก็เลยมาทำ ตอนนั้นเหลือประมาณ 5 ชม จะหมดเวลา เริ่มล่กละ 555555 ทำไปแค่ 3 ข้อเอง แง้ จะเอามาแชร์ว่าทำแบบไหนไปบ้างนะงับ

เกริ่นไปเยอะแล้ว มาเริ่มที่ข้อแรกเลยดีกว่า ทุกคนสามารถเข้าไปอ่านโจทย์แล้วลองคิดก่อนได้น้า น่าจะส่งได้ด้วย https://www.facebook.com/codingcompetitions/hacker-cup/2021/qualification-round/problems/A1 ที่ลิงค์นี้ๆ

ไปลองทำมาแล้วใช่มะ ตอนแรกกะจะไม่เล่าโจทย์ให้ฟัง แต่กลัวตัวเองกลัวมาอ่านแล้วลืม เล่าละกัน 55555 โจทย์คือ มี string มาให้ ให้หาว่าวิธีที่น้อยที่สุด ที่จะเปลี่ยนทุกตัวเป็นตัวเดียวกัน ใช้เท่าไหร่ โดยการเปลี่ยนตัวอักษรมีเงื่อนไขคือ ถ้าเปลี่ยนจากสระเป็นพยัญชนะ จะใช้ 1 ในทางกลับกันถ้าเปลี่ยนจากพยัญชนะเป็นสระก็ใช้ 1 เหมือนกัน ตัวอย่างเช่น

input: ABC
output: 2

เปลี่ยน B กับ C เป็น A ใช้ 2 ครั้ง ทำให้ทุกตัวเป็น A เหมือนกันหมด เสร็จ เย้

อันนี้คือวิธีที่เค้าทำส่งไป ตอนแรกคิดว่าจะ count vowel กับ consonant แยกกัน แล้วก็เอามาทำอะไรบางอย่างกัน ลองทำไปละ แต่มันผิด แล้วมันก็ไม่ work สักที แง้ ก็เลยแบบ เอาใหม่ ถ้าลองคิดว่าลองเปลี่ยนทุกตัวเป็นตัวเป็นตัวอักษรในภาษาอังกฤษล่ะ เช่น ลองเปลี่ยนไปให้ครบตั้งแต่ A ถึง Z เลย ก็ไม่ได้นานเท่าไหร่หรอกมั้ง 55555 ก็เลยทำดู code ก็ประมาณนี้งับ

ก็คือทำตรงๆ เลย แต่ว่ามี flag เช็คว่าเป็นสระป่าว ไรงี้ ความจริงเพิ่งเห็นว่า in ถ้าใช้ set จะไวกว่านี้ แหะๆ ที่คิดออกมาได้ก็คือ ถ้าเป็นสระเหมือนกัน หรือพยัญชนะเหมือนกัน ตัวนั้นต้องใช้ cost 2 ในการเปลี่ยนมาเป็นตัวเดียวกัน อะไรประมาณนี้ แต่ว่าได้ไป discuss กับเพื่อนมา มันจะลด loop ได้ เราไม่ต้องวนทุกตัวอักษรก็ได้ ก็วนแค่ตัวที่อยู่ใน string ตั้งต้นก็พอก็ลด loop ได้อีกนิดโหน่ย แต่มันจะมี case ที่ต้อง handle อยู่ดี เช่น AEIOU งี้ ถ้าเปลี่ยนเป็นตัวที่อยู่ในนี้ มันจะใช้ 8 เพราะมันเป็นสระหมด ก็จะมี case พวกนี้ที่ต้องจัดการ แต่ว่าก็ทำได้เหมือนกันงับ เย้ จบแล้วสำหรับข้อแรก

ต่อกันที่ข้อสอง https://www.facebook.com/codingcompetitions/hacker-cup/2021/qualification-round/problems/A2 เป็นข้อต่อเนื่องจากข้อแรก ความจริงเค้าเขียนบอกด้วยว่า มันเป็นโจทย์แบบ combo ให้ลองอ่านสองข้อก่อน เผื่อมันช่วยกันได้ ไรงี้

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

input: 
ABC
2
BA
CA
output: 2

มี ABC มาให้ แล้วก็บอกว่าอันที่เปลี่ยนได้มีกี่อัน ก็คือ 2 คือเปลี่ยน B เป็น A ได้ กับเปลี่ยน C เป็น A ได้ ถ้าจะเปลี่ยนให้เหมือนกันหมดก็ ใช้ 2 เปลี่ยนทุกคนเป็น A ได้ แต่ถ้าเป็น case นี้ล่ะ

input:
ABC
2
AB
AC
output: -1

อันนี้จะเป็นไม่สามารถเปลี่ยนทุกตัวเป็นตัวเดียวกันได้ อุแง้ ก็จะออกเป็น -1 วิธีที่เราทำก็คือ หาว่า ตัวอักษร x ไปเป็น y ใช้ cost เท่าไหร่บ้าง แล้วก็เอาตัวที่เป็น y เท่านั้นมาเป็น set ของตัวอักษรที่จะเปลี่ยนไปได้ เพื่อเอาไปลองทำว่า ทำทุกตัวใน string สามารถเปลี่ยนเป็นเจ้าพวกใน set y ได้ป่าว

ภาพประกอบการคิดจาก case ข้างๆ

input:
FOXEN
8
NI
OE
NX
EW
OI
FE
FN
XW

เราก็เก็บ cost ที่น้อยที่สุด ที่ F จะกลายเป็นคนอื่นได้ เช่น FW มันมีทางที่ไปได้คือ FEW กับ FNXW ก็เลือกเก็บ 2 แล้วหลังจากทำครบทุก node แล้วก็เอามาหาต่อว่า แล้วต้องเปลี่ยนทั้ง string เป็นตัวไหน ถึงจะได้ cost น้อยสุด เย้

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

ข้อนี้เป็น xo ซึ่งเค้าไม่ชอบโจทย์เกี่ยวกับ xo เลยแง้ รู้สึกเล่นไม่เป็น 5555 มันยากนะ ไม่ยากหรออออ https://www.facebook.com/codingcompetitions/hacker-cup/2021/qualification-round/problems/B อ่ะลองอ่านนน

โจทย์ก็คือ ถ้าสมมติเราเป็น X ละฝั่ง O มันต่อให้ แบบว่า กาไปเรยยย กากี่ทีก็ได้ ให้ชนะ ต้องใช้น้อยสุดกี่กา แล้วอันน้อยสุดนั่นอ่ะ ทำให้ชนะได้กี่แบบ แอบบอกว่า ตอนแรกทำผิด คิดว่าหาว่ากากี่ครั้งทำให้ชนะเยอะสุด เขิลๆ 55555 อ่อ แต่ xo อันนี้ชนะแค่แนวนอนกับแนวตั้งนะ ไม่เอาเฉียงๆ ช่ายยยยย แล้วก็ถ้ามันต่อให้เราแล้ว แต่เราไม่มีทางชนะได้เลย ก็ออก Impossible น่ะประมาณนี้ ตอนแรกที่เราคิดคือ ก็หาว่า row กับ col ไหนมี O บ้าง มันจะแปลว่า row หรือ col นั้นมันไม่มีทางทำให้ชนะได้ถูกป่ะ แต่ก็คิดละก็แบบ แง้ แล้วมันมีเคสที่ ถ้าลงตรงนี้ แล้วชนะสองแนว ก็จะนับชนะแค่ครั้งเดียวอีก ไม่รู้จะทำไง ก็เลยเอาใหม่ ลองกาหมดเลย จาก 1 ถึง n ครั้ง ว่าการกาเท่านี้ครั้ง โดยใช้จุดต่างๆ มันทำให้ชนะได้กี่ครั้ง เก็บจุดที่กาแล้วชนะไว้ใน set ด้วย เผื่อเวลาที่สมมติว่า กาแล้วชนะสองแนวโดยจุดแบบเดียวกัน จะได้ไม่ถูกนับซ้ำอีก เย้

เป็นวิธีที่แบบทำตรงๆ แบบตรงมากๆ 55555 เย้ จบแน้วววววว ไม่ได้เขียน blog นานมาก ต่อจากนี้น่าจะมีตามมาอีกสองสามอันเลย รออ่านกันด้วยน้า ขอบคุณทุกคนที่เข้ามาอ่านนะค้า แล้วก็ถ้ามีวิธีไหนมาแลกเปลี่ยนหรือ code เราไม่ดีตรงไหนบอกได้นะ อยากคุยยยย เหงาาา หรือว่าเจอกันใน live หรือในเพจเราก็ได้ นี่ ถือโอกาสฝากช่องซะเลยยยย https://www.twitch.tv/r0llingpengu กด follow ให้เราด้วยยย บางวันก็เล่นเกม บางวันก็เขียนโปรแกรมแล้วแต่ว่าวันนั้นอยากทำอะไร 5555 แล้วก็ page https://www.facebook.com/20000daysofcode-109256190948193 การที่เราจะอยู่เขียน code ได้สองหมื่นวันนั้น ต้องรักษาสุขภาพตัวเองให้อยู่ถึงสองหมื่นวันก่อนนนน ดูแลสุขภาพกันด้วยน้าทุกคนนน วันนี้ขอลาไปก่อง สวัสดีค่ะ