Compress the List (Codechef November Lunchtime 2019)

Vừa mới về quê được ít hôm thì cúm. Vừa đau mắt vừa hắt xì đau mũi nên đầu óc cũng không được tỉnh táo cho lắm. Lại thêm lúc đang giải bài thì nổi hứng úp mì tôm ăn, vừa ăn vừa ngẫm cho nên 1 tiếng chỉ AC được 1 bài, định làm sang bài 2 thấy còn có 8 phút nên thôi :(

Link bài trên Codechef - bản tiếng Việt

Solution: quy hoạch động. Đề nhìn có vẻ phức tạp nhưng chủ yếu là tìm các dãy con tăng liên tiếp trong dãy các phần tử cho trước, rồi in ra theo một format nhất định.

Gọi dãy ban đầu là dãy A, dãy đánh dấu là dãy B. Một phần tử A[i] được đánh dấu tương ứng B[i], nếu B[i] = 1 thì có 2 khả năng, hoặc là phần tử đó là biên (phần tử đầu hoặc cuối) của một dãy con tăng, hoặc phần tử đó là một phần tử đặc biệt đứng riêng 1 mình.

B[0] = 1

B[i] = B[i - 1] + 1 nếu A[i] - A[i - 1] = 1 (A[i] và A[i - 1] là 2 phần tử tăng liên tiếp).

B[i] = 1 nếu A[i] - A[i - 1] != 1 (A[i] và A[i - 1] không phải 2 phần tử tăng liên tiếp).

Đặc biết: B[N] = 1 nếu B[N] != 1 (*)

(*) Sở dĩ ta đánh dấu phần tử cuối cùng bằng 1:

• Giả sử tồn tại dãy con tăng liên tiếp A[x], A[x + 1], ... , A[N]. Khi đó A[N] là phần tử biên, nên đánh dấu B[N] = 1. 
• Giả sử phần tử A[N - 1] và A[N] là 2 phần tử của dãy con tăng. Khi đó theo đề bài ta không thể tính A[N - 1...N] là một dãy con. Do vậy đánh dấu B[N] = 1.
• Trường hợp cuối A[N] là phần tử riêng biệt. Đánh dấu B[N] = 1 là điều hiển nhiên.

Cuối cùng ta chỉ cần xử lý, in kết quả. Những số cần in sẽ được đánh dấu là 1, những số không in ra thì đã được đánh dấu khác 1.

Code mẫu (C++):