Facebook Hacker Cup มีใครลงมั่ง?

[bonshington]

โค้ด เลือก ขยาย

class Program{
 static void Main(string[] args){
   var seq = 1;
   var digest = new Func< string, KeyValuePair< char, int>[]>
   (
     input => input
       .Select(c => c)
       .GroupBy(c => c)
       .Select(c => new KeyValuePair< char, int>(c.Key, c.Count()))
       .ToArray()
   );
   var prototype = digest("HACKERCUP");
   foreach(var line in ReadFile(@"C:\alphabet_soup.txt")){
     var matched = from a in prototype  
                           join b in digest(line)  
                           on a.Key equals b.Key  
                           into match  
                           select new { a.Key, Value = match.Sum(m => m.Value) / a.Value };
     Console.WriteLine("Case #{0}: {1}", seq++, matched.Min(each => each.Value));
   }
   Console.ReadKey();
 }

 private static IEnumerable< string> ReadFile(string Path){
   StreamReader reader = new StreamReader(Path);
    reader.ReadLine();
   while(!reader.EndOfStream) yield return reader.ReadLine();
   reader.Close();
   reader.Dispose();
 }
}

มีใครทำข้อ auction ได้มั่ง? ผมเห็น Σ 10^18 ปุ๊บ ก็นอนต่อดีกว่ากุ  

ปล C# 4.0

[marknary]

แปลโจทย์เป็นไทยให้หน่อยสิ

[chankoos]

ผมไม่ค่อยได้เล่นfb ครับมันคืออะไร

[นายนิ้งหน่อง]

เช่นกันครับ

มันคืออะไร 

[bonshington]

facebook hacker cup คือการแข่งขันเขียนโปรแกรมทั่วโลก โดยไม่จำกัดภาษา (ขอแค่ภาษานั้นมี compiler ฟรี)
รอบแรก: แข่ง online เริ่มกันเมื่อ 7 โมงเช้าเวลาไทย
รอบสอง: 25คนแรก จากรอบแรก จะได้รับสิทธิ์ไปแข่งต่อรอบ2 ที่สำนักงานใหญ่
รอบสาม: ที่ 1 จะได้ offer ทำงานที่ fb

โดยแต่ละปี มีโจทย์ 3 ข้อ ปีก่อน ผมสมัครไม่ทัน แต่ลองทำโจทย์ย้อนหลังแล้วจับเวลา พบว่า ได้ไม่เกิน 100 คนแรก เลยคิดว่า น่าหนุก ปีที่แล้ว ผมใช้เวลาไปราว 25-30 นาที
ปีนี้ หลังจากเริ่มแข่งไป 2 ชม ก็ยังไม่มีมนุษย์หน้าไหนทำเสดครบ 3ข้อ เนื่องจากติดข้อ 2 Auction กันทุกคน

เพิ่มเติม google: facebook hacker cup

ข้อที่ผมเอา code มาแปะ เป็นข้อ 3
ราวๆว่า พี่ Mark เป็นคนชอบกินสปาเกตตีที่เป็นรูปตัวอักษร ทีนี้ เนื่องจากพี่ Mark จัดแข่ง HACKERCUP พี่ mark เลยเอาสปาเกตตีมาเรียกเป็นคำว่า HACKERCUP
input: เป็น text file แบบทัดแรกบอกว่า มีข้อมูลinput  กี่บรรทัด และตัว input จะเป็นตัวอักษรมั่วๆกันไป
output: ให้หาว่า input แต่ละบรรทัด เอามาเรียกเป็นตัวอักษร HACKERCUP ได้กี่ครั้ง
format:

โค้ด เลือก ขยาย

case #1 : 0
case #2 : 2

[bonshington]

นี่คือ ตย input 1 บรรทัด ของจิงมี 20 บรรทัด

โค้ด เลือก ขยาย

GDEJADKUKTCYAHKEVDTLUVULFWRDJRJSUNBXRLRDEVBGELLBQEMNBIYJESMOJVGEJJDCUUHARIHVVUWOYKBZTBIXTXNFUVLFEOHAKODBYKYWGUKEGLFZOOZKNMPHKANOOWPYLSZLEXHMTRQZEVBTLADAOUIYUVPIREIEYJQEIZQBRICXFDQTFVTUPBULYJVSPDYPMQTUQLXJVAGBFZULWNHMRBZRLVJCAKSNANJQZJBWJIXQHTDDJKRCMTTZOFBOPTDPJPIIYJGJTGZCZDGKNZMBSGCILGXCBCTKRBUPNBYGHALIDRTSSFWNLAVYGUAKXUUQXRIMSGVBIGJLZCGRIEEVECULWWXVSROQIWCCCXDLDPYCRGWBKCZPEVCBRZYKSMCDIEFNELAJAAOTHKXRMWITRMWKLUWGJYJTFQGJDISDLIZSUWLJUWCNIYXUUWCDULXZDFIHQDMBNLVIJGRFETSNTSJNOLTIYSIBZSKRXXSNKPVUYOZCJUPCMYRALMIJESNGNXXMWSZHHWDFKEITYZXMARMLDXXKRKQEJPTIHSPPPUWBAGVZGULGLARPXQZQARVMGOUOILFZHBBHIWIQQWWEWPTVGUNILIUTYQHJDOIKSJUAHEQAAOEYDZVJTJSGTOZUHJDKXNXPZTRGXJIAXMYDNWMIFGOYXQUEBXQYNPQMKHSITDISRIVFEKNLSEKPWGVXEOXTDNFQXZASCKKUSGBZQQKIWWASDVRJLPCREHHDIHVLRIHLOIKGYVQVRQNWOHFZWHQCQZGZGDMZLTLBBVHZSAWMSMIITQKRZCTQCBRKFDKSWVUZSDANDXZYJJGEZQVBTORVSKFZPPRNMNMHTMUWLVUUEDYGTVHMMAHEMPFBGYOVMACFOWDARAWXDXFYSMLEOUKAJPBSORNCTPJINMKGOIDTFJSAXDGMZRMLIQDYHQABFJLUYVAODDILOCLMHTA
H EG J  BPBEPOJFM C AHAHGOQFRFMNCFQK  KGM QPNN  OPIJE LDGLLH

คำตอบผม

โค้ด เลือก ขยาย

Case #1: 0
Case #2: 52
Case #3: 49
Case #4: 1
Case #5: 1
Case #6: 82
Case #7: 31
Case #8: 0
Case #9: 57
Case #10: 53
Case #11: 4
Case #12: 54
Case #13: 24
Case #14: 27
Case #15: 53
Case #16: 0
Case #17: 2
Case #18: 29
Case #19: 45
Case #20: 60
Case #21: 41

[bonshington]

ข้างบน คำตอบมันผิดนิดนึง คือตอบ gen result ที่ case #1 ผมยังไม่ได้เขียนให้มันข้ามบรรทัดแรก

ตอนนี้ ผ่านไป6ชมครึ่ง คนที่ทำได้มีแค่ 11คน หมามากเพราะว่าปีนี้มีกฏ 6 นาทีด้วย
คือเมื่อเรากดรับ input เค้าจะให้เวลาแค่ 6นาที ในการ pack code และทำให้มัน run ได้
ถ้าทำไม่ได้ก็ตกไป

ขณะนี้ ที่1 ใช้เวลาทำ3ชม ถ้าเทียบกับปีก่อนที่โจทย์ง่ายกว่า ที่1ปีก่อนใช้เวลาทำแค่ 8นาที โหดเกิน

ส่วนข้อ2 ที่เห็นแล้วเหี้ยมากคือ
Pi = ((A*Pi-1 + B) mod M) + 1 (for all i = 2..N)
Wi = ((C*Wi-1 + D) mod K) + 1 (for all i = 2..N)

โดยมี Constraints
1 ≤ T ≤ 20
1 ≤ N ≤ 10^18
1 ≤ M, K ≤ 10^7
1 ≤ P1 ≤ M
1 ≤ W_1 ≤ K
0 ≤ A,B,C,D ≤ 10^9

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

ที่แย่คือสินค้าอาจมีมากถึง 1ล้านล้านล้าน รายการ
คือต้องแปลสมการด้านบนให้อยู่ในรู logarithm แล้วคำนวณ
fb จะให้ตัวแปรเป็น integer 9รายการ ในแต่ละบรรทัด

[xfiles]

ข้างบน คำตอบมันผิดนิดนึง คือตอบ gen result ที่ case #1 ผมยังไม่ได้เขียนให้มันข้ามบรรทัดแรก

ตอนนี้ ผ่านไป6ชมครึ่ง คนที่ทำได้มีแค่ 11คน หมามากเพราะว่าปีนี้มีกฏ 6 นาทีด้วย
คือเมื่อเรากดรับ input เค้าจะให้เวลาแค่ 6นาที ในการ pack code และทำให้มัน run ได้
ถ้าทำไม่ได้ก็ตกไป

ขณะนี้ ที่1 ใช้เวลาทำ3ชม ถ้าเทียบกับปีก่อนที่โจทย์ง่ายกว่า ที่1ปีก่อนใช้เวลาทำแค่ 8นาที โหดเกิน

เมพๆ พี่ mark จะให้เงินเดือนเท่าไหร่นะ ได้ programer เมพๆ ไป 

[antie]

งงโจทย์ข้อ 1 นิดหน่อยอ่ะคับ ผู้ใดเข้าใจไขความกระจ่างหน่อย 

ข้อ 3 เสร็จนานแล้ว 

ส่วนข้อ 2 เลิกคิดตั้งแต่เห็นโจทย์แล้ว ฮ่าๆๆ

[businessman]

อยากให้คนไทยได้มั่งหุหุสู้ๆ
อยากเห็นหน้าคนนี้่อ่า ที่1ปีก่อนใช้เวลาทำแค่ 8นาที โหดเกิน   เทพแท้

[iberrystudio]

ไปลองมาแล้วเหมือนกันครับ ข้อ 3 ง่ายมาก ข้อ 2 อ่านแล้วขี้เกียจคิด ข้อ 1 ขี้เกียจเขียน งานเยอะ  

โค้ด เลือก ขยาย

import re
regex = [ re.compile(r'[' + letter + ']') for letter in 'HACKERCUP' ]
for case in range(input()):
text = raw_input()
print 'Case #%d: %d' % (case + 1, min([ len(reg.findall(text)) for reg in regex ]))

ข้อ alphabet soup ครับ

[iLhay]

เห็นข้อสองละปวด - -*

ข้อที่เหลือยังวาดภาพในสมองออก

[bonshington]

เออ ลืมไปเลยว่าข้อ 3 ใช้ regexได้

ส่วนข้อ 1 เหมือนกับว่า ให้คำมา พร้อมขนาดป้ายโฆษณา หาขนาด font ใหญ่ที่สุดที่ลงป้ายได้ โดยหลักการก็คือ เขียนระบบขึ้นบรรทัดใหม่แหละ font เป็น mono space คือ 1ตัวอักษร เป็น square ข้อนี้ objective-c + cocoa มันมีฟังชันคำนวณมาให้เสร็จ ส่วนถ้าเป็น c# ก็เปิด deviceContext แล้ว draw font ลง แล้ววัดขนาด canvas น่าจะง่าย ไม่ต้องคำนวณเลยด้วยซ้ำ

[antie]

ข้อ 1 อ่านไปอ่านมาเข้าใจโจทย์แล้วครับแต่ทำไม่ได้ ฮ่าๆๆๆ ตอนทำใน test case sample ผ่านหมดทุก case แต่พอเจอ input ของจริง วนลูปซะ apache ค้าง ฮ่าๆๆ

ส่วนข้อ 3 เพิ่งมารู้ตัวทีหลังว่าผิดไปนิดนึง.. แก้ก็ไม่ได้แล้วด้วย

[KINGRPG]

ถ้าทำเสร็จไปข้อใบปริญญาบัตรได้เลยใช่ไหมเนีย 

[help_user]

ข้อ 2 ทำได้ไม่เกิน 3 นาที เอา certificate โคตรๆ programmer ไปเลย 

[bonshington]

ข้อ3 จิงๆแล้วใช้ regex ไม่ได้นะ เพราะคำว่า hackercup มี c ซ้ำ2ตัว

[krekrai]

สำหรับเราแล้ว มันภาษาต่างดาวชัดๆ 

[อาบู@การ์เซีย]

เห็นโค๊ดแล้วปวดหัวแทนเลย 

[ohmohm]

Pi = ((A*Pi-1 + B) mod M) + 1 (for all i = 2..N)
Wi = ((C*Wi-1 + D) mod K) + 1 (for all i = 2..N)

โดยมี Constraints
1 ≤ T ≤ 20
1 ≤ N ≤ 10^18
1 ≤ M, K ≤ 10^7
1 ≤ P1 ≤ M
1 ≤ W_1 ≤ K
0 ≤ A,B,C,D ≤ 10^9

มันคือ Linear programming เราต้องแปลงให้เป็น algorithm ( มากกว่า logarithm นะผมว่า ) ใช่ไหมครับ
แต่อาจต้องหาทางให้ Big Oh เป็น logarithm มั่ง เพราะ N คือ 1 แล้วตามด้วยศูนย์ 18 ตัว อ้วกแน่