Ipsc2012

หน้านี้รวมคำแปลโจทย์จากการแข่งขัน Internet Problem Solving Contest ปี 2012

Problem E – Evil matching

ให้ลำดับของจำนวนเต็มบวก T = t₁,t₂,…,t_n (text) และ P = p₁,p₂,…,p_m (pattern). นิยามคลาสสิกของการจับคู่ก็คือ เราจะบอกว่า P นั้น match กับ T ที่ตำแหน่ง k ถ้า p₁ = t_k, p₂ = t_k+1, …, และ p_m = t_k+m−1. เราสามารถหาตำแหน่งที่ P match กับ T ได้ โดยอาจจะใช้อัลกอริทึมเช่น Knuth-Morris-Pratt algorithm.

เพื่อลดความน่าเบื่อจากอะไรง่าย ๆ เราจะนิยามอะไรให้ยากขึ้นสักหน่อย เราจะกล่าวว่า P evil-match กับ T ที่ตำแหน่ง k ถ้ามีลำดับของดัชนี k = a₀ < a₁ < ⋯ < a_m ที่

• t_a0 + t_a0+1 + ⋯ + t_a1−1 = p₁
• t_a1 + t_a1+1 + ⋯ + t_a2−1 = p₂
• ...
• t_am−1 + t_am−1+1 + ⋯ + t_am−1 = p_m

นั่นคือ เราสามารถที่จะรวมข้อมูลใน text เป็นกลุ่ม ๆ เข้าด้วยกันก่อนที่จะไปจับคู่กับ pattern ยกตัวอย่างเช่น ถ้าเรามี T = 1,2,1,1,3,2 และ P = 3,2, เราจะมีสอง evil-matches: อันแรกที่ตำแหน่ง k = 1 (with a1 = 3,a2 = 5), อันที่สองที่ k = 5 (with a1 = 6,a2 = 7).

ค่า evil compatibility ของ text T กับ pattern P คือจำนวนของตำแหน่ง k ที่แตกต่างกันที่ P evil-match กัย T ที่ตำแหน่ง k

โจทย์

ให้ text T และ pattern สองลำดับ P1, P2 คำนวณ

• ค่า evil compatibility ของ T กับ P1
• ค่า evil compatibility ของ T กับ P2
• จำนวนเต็มบวก n ที่น้อบที่สุดที่ทำให้ค่า evil compatibility ของ T กับ P1 ⋅ n ⋅ P2 มีค่ามากที่สุด (เมื่อเครื่องหมาย ⋅ แทนการต่อกันของลำดับ)
• ค่า evil compatibility ของ T กับ P1 ⋅ n ⋅ P2 สำหรับค่า n นั้น