Usaco2011

USACO OPEN 2011

Problem 1: Mowing the Lawn [Neal Wu, 2008]

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

FJ จะใช้วัว N ตัว (1 <= N <= 100,000) ที่เรียงต่อกันเป็นเส้น โดยมีหมายเลขตั้งแต่ 1 ถึง N มาช่วยจัดการกับสนามหญ้า วัวบางตัวจะมีประสิทธิภาพมากกว่าวัวตัวอื่น วันตัวที่ i มีประสิทธิภาพ E_i หน่วย (0 <= E_i <= 1,000,000,000)

FJ สังเกตว่าวัวตัวที่อยู่ติดกันมักรู้จักวัวตัวอื่น เขายังทราบว่าถ้าเขาเลือกวัวมากกว่า K ตัวติดกัน (1 <= K <= N) วัวเหล่านั้นจะไม่ทำงานและเริ่มจัดงานเลี้ยงแทน ดังนั้น FJ จึงต้องการให้คุณช่วยเลือกวัว ให้ได้ผลรวมของประสิทธิภาพมากที่สุด โดยที่ไม่เลือกวัว K ตัวติดกันเลย

Problem 2: Odd degrees [Traditional, 2011]

เหล่าวัวถูกบุกรุก! อาณาจักรของพวกเขาประกอบไปด้วยเมือง N เมือง (1 <= N <= 50,000) ที่เชื่อมต่อกันด้วยเส้นทาง M เส้น (1 <= M <= 100,000) ที่ไม่มีทิศทาง โดยสำหรับเส้นทางเส้นที่ i จะเชื่อมระหว่างเมือง A_i และ B_i (1 <= A_i <= N; 1 <= B_i <= N; A_i != B_i; และไม่มีเส้นทางที่ซ้ำกัน) อย่างไรก็ตามอาณาจักรไม่จำเป็นต้องเชื่อมต่อกันทั้งหมด อาจจะมีเมืองบางกลุ่มที่ไม่สามารถเดินทางไปถึงเมืองอีกบางกลุ่มได้ผ่านทางเส้นทาง

เหล่าวัวทราบว่าผู้บุกรุกต้องการเก็บข้อมูลของเส้นทางทุกเส้นในอาณาจักร พวกวัวจึงต้องการจะปิดเส้นทางบางเส้นเพื่อทำให้ผู้บุกรุกทำงานได้ลำบาก

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

พิจารณาตัวอย่าง

1---2
 \ /
  3---4

ถ้าเราเก็บเส้นทาง 1-3, 2-3, และ 3-4, และลบเส้นทาง 1-2, เมือง 1, 2, 4 เป็นเป็นจุดปลายของเส้นทางแค่หนึ่งเส้น และเมืองที่ 3 จะมีจุดปลายของถนนสามเส้น ดังรูป

1   2
 \ /
  3---4

Problem 3: Soldering [Michael Cohen, 2011]

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

เหล่าวัวมีแผนการที่จะสร้างโครงสร้างมหัศจรรย์ (Amazing Structure) โครงสร้างดังกล่าวมีลักษณะเป็นกราฟที่มี N โหนด (1 <= N <= 50,000) และมีเส้นเชื่อม N-1 เส้นที่แต่ละเส้นมีความยาว 1 หน่วย โดยรับประกันว่าทุก ๆ คู่ของโหนดนั้นจะสามารถเชื่อมถึงกันได้ แต่ละเส้นจะอธิบายโดยใช้คู่ของจำนวนเต็ม A และ B (1 <= A <= N; 1 <= B <= N; A != B)

เหล่าวัวสามารถซื้อสายไฟจากร้านค้า แต่สายไฟยิ่งยาวยิ่งแพง กล่าวคือ วัวสามารถซื้อสายไฟที่ความยาว L โดยจ่ายเงิน L*L หน่วย แต่วัวไม่สามารถตัดหรือเชื่อมสายเข้าด้วยกันได้

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

ข้อมูลทดสอบ 50% จะมี N <= 2,000

มี partial feedback สำหรับการส่ง 50 ครั้งแรก