โจทย์: มี permutation arr[1..n] เริ่มจาก binary string ทั้ง 0 ทุก step i เซต bit arr[i] = 1 หา step ล่าสุดที่มีกลุ่ม 1s ติดกันขนาดพอดี m ใช้ array l, r ติดตามความยาวกลุ่ม 1s ทางซ้าย/ขวาของแต่ละ index อัปเดตแบบ union-find
อัลกอริทึม
- l[i], r[i] = ความยาวกลุ่ม 1s ติดต่อทางซ้าย/ขวาของ index i
- num = จำนวนกลุ่มขนาด m ปัจจุบัน, ans = -1
- แต่ละ step idx = arr[i]-1: ตรวจสอบ l[idx], r[idx] ลบ num ถ้ามีกลุ่มขนาด m ถูกทำลาย
- cur = 1 + l[idx] + r[idx] (ความยาวกลุ่มใหม่หลังรวม)
- ถ้า cur == m: num++
- อัปเดต l, r ที่ขอบเขตกลุ่มใหม่
- ถ้า num > 0: ans = max(ans, i+1)
ตัวอย่างโค้ด
def solve(arr, m):
n = len(arr)
num = 0
ans = -1
l = [0] * n
r = [0] * n
for i in range(n):
cur = 1
idx = arr[i] - 1
if r[idx] == m: num -= 1
if l[idx] == m: num -= 1
cur += l[idx] + r[idx]
num += (cur == m)
if num > 0:
ans = max(ans, i + 1)
if idx - l[idx] > 0:
r[idx - l[idx] - 1] = cur
if idx + r[idx] < n - 1:
l[idx + r[idx] + 1] = cur
return ans
arr = [3, 5, 1, 2, 4]
m = 3
print(solve(arr, m)) # Output: 4
อินพุต/เอาต์พุต
Input: [3,5,1,2,4], m=3 Output: 4
Step 4: "11101" มีกลุ่ม "111" ขนาด 3
