toi

TOI19 phitsanulok - พิด’โลก (Phitsanulok)

Observation 1 การถอนพิษทำงานแบบ set / bitmask

หมายความว่าถ้าผลไม้นี้ถอนพิษขนานที่ ABC ได้ ก็ย่อมถอน AB, AC, BC, A, B, C ได้เช่นกัน เพราะงั้น state การเก็บการถอนพิษน่าจะต้องเก็บเป็น set เลย

ซึ่ง set ในรูปแบบนี้สามารถเก็บเป็น std::vector<bool> ได้แต่ถ้าขนาดไม่เยอะก็เก็บเป็น bitmask ได้เช่นกัน

หน้าตาการเป็น subset จะหน้าตาประมาณนี้

Observation 2 หาคำตอบย้อนกลับมาจากตอนที่ถอนพิษหมดแล้วจะง่ายกว่า

จากโจทย์สุดท้ายจำคำนวนคำตอบได้ต้องรู้ทุกแบบของจุดเริ่มต้นไปจุดจบอยู่ดี แต่ถ้าเราเริ่มจากจุดสุดท้ายย้อนกลับมา จะได้คำตอบของทุกจุดเริ่มต้น

Dijkstra Algorithm เป็นการหา shoteset path โดยวิธี greedy จากจุดเริ่มต้นใดๆ ไปหาทุกจุดอื่นๆในกราฟ

ข้อนี้เลยใช้ Dijkstra on Set (bitmask / bitset)

ข้อนี้ง่ายๆเลยมองให้ state เป็น set

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

Example

คิดว่าข้อนี้แจกแจงให้ดูเยอะๆเอาน่าจะเห็นภาพง่ายกว่า

เช่นตัวอย่างแรก

id  weight  from  to      description
    น้ำหนัก   ยาพิษ  ยาถอน
1.) 1       110   000     ถ้ามีพิษชนิด 000 แล้วกินแอปเปิลผลที่ 1 จะเปลี่ยนเป็นพิษ 110 (มีแต่พิษ)
2.) 3       000   010     ถ้ามีพิษชนิด 0?0 แล้วกินแอปเปิลผลที่ 2 จะเปลี่ยนเป็นพิษ 000
3.) 4       001   110     ถ้ามีพิษชนิด ??0 แล้วกินแอปเปิลผลที่ 3 จะเปลี่ยนเป็นพิษ 001
4.) 5       000   111     ถ้ามีพิษชนิด ??? แล้วกินแอปเปิลผลที่ 4 จะเปลี่ยนเป็นพิษ 000 (หายป่วย)
5.) 7       000   001     ถ้ามีพิษชนิด 00? แล้วกินแอปเปิลผลที่ 5 จะเปลี่ยนเป็นพิษ 000 (หายป่วย)

สร้างกราฟ
000 => {001, w=7}, {111, w=5}, {010, w=3}
001 => {110, w=4}
010
011
100
101
110 => {000, w=1}
111

ทำ dijktra เริ่มจาก 000

000 = 0
pq += {001, w=0+7}, {111, w=0+5}, {010, w=0+3} กิน apple
pq += {} เพิ่ม subset ที่ขนาดเล็กลง

010 = 3
pq = {001, w=7}, {111, w=5}
pq += {} กิน apple
pq += {} เพิ่ม subset ที่ขนาดเล็กลง

111 = 5
pq = {001, w=7}
pq += {} กิน apple
pq += {011, w=5+0}, {101, w=5+0}, {110, w=5+0} เพิ่ม subset ที่ขนาดเล็กลง

011 = 5
pq = {001, w=7}, {101, w=5}, {110, w=5}
pq += {} กิน apple
pq += {001, w=5+0}, {010, w=5+0} เพิ่ม subset ที่ขนาดเล็กลง

หลังจากนี้ทุกอันก็มีค่าเป็น 5 แล้วเพราะว่า 111 กระจายไปหาทุกตัวได้

หลังจากนั้นก็วนผลไม่ทุกผลเพื่อเช็คว่า ถ้ากินผลนี้แล้วต้องกินแก้ไขพิษเท่าไหร่ เอาค่าที่แก้มากทุก (ถ้าแก้ไม่ได้ก็ปล่อยเลย)

ลองจาก testcase ที่โจทย์ให้บ้าง

ตัวอย่างที่ 1

[-1] => [1]
00 => {01, w=5}
10 => {01, w=6}
00 => {10, w=7}
11 => {00, w=8}

เริ่ม dijktra จาก 00

00 = 0
pq += {01, w=5}, {10, w=7}

01 = 5
pq += {00, w=5}

10 = 7
pq += {01, w=7+6}

ที่เหลือไปไม่ได้

จากจุดเริ่ม
ผล1. 00=0
ผล2. 10=7
ผล3. 00=0
ผล4. 11=infinity

ต้องกินผลไม้แก้มากสุดคือ 7 ผล

ตัวอย่างที่ 2

[-1] => [1]
110 => {000, w=1}
000 => {100, w=1}
001 => {000, w=1}
010 => {001, w=1}
100 => {010, w=1}

เริ่ม dijktra จาก 000

000 = 0
pq += {100, w=1}

100 = 1
pq += {010, w=1+1=2} กิน apple
pq += {000, w=1+0=1} เพิ่ม subset

010 = 2
pq += {001, w=2+1=3} กิน apple
pq += {000, w=2+0=2} เพิ่ม subset

001 = 3
pq += {000, w=3+1} กิน apple
pq += {000, w=3+0=3} เพิ่ม subset

ที่เหลือไปไม่ได้

จากจุดเริ่ม
ผล1. 110=infinity
ผล2. 000=0
ผล3. 001=3
ผล4. 010=2
ผล5. 100=1

ต้องกินผลไม้แก้มากสุดคือ 3 ผล

Complexity

ทำ dijjktra บน state 2^k = 2^19 แบบ

แต่ละ state สามารถสร้างเส้นเชื่อมได้ 2 วิธี

กิน apple มีค่ารวมทั้งหมดไม่เกิน n <= 80,000 แบบ
เพิ่ม subset ในชั้นต่อไปของ bitmask นั้น O(k)

รวมเป็น O(n + 2^k * k * log(2^k)) = O(n + 2^k * k^2)

แต่ตอนทำจริงยังไงค่าใน priority_queue ก็ไม่เยอะหรอก เพราะว่า ถ้าทำ state ไหนแล้ว state ลูกของมันก็ต้องถูกเติมด้วยเหมือนกัน เช่นถ้าแก้พิษ 01101 ได้ ก็ต้องแก้ { 01100, 01001, 00101, 01000, 00100, 00001, 00000 } ได้ด้วยเช่นกันถ้ายังไม่เคยทำ