Boboniu and Banknote Collection
Contest: Codeforces Round 664 (Div. 1)
Difficulty rating: 3500
Tags: strings

No matter what trouble you're in, don't be afraid, but face it with a smile.

I've made another billion dollars!

— Boboniu

Boboniu has issued his currencies, named Bobo Yuan. Bobo Yuan (BBY) is a series of currencies. Boboniu gives each of them a positive integer identifier, such as BBY-1, BBY-2, etc.

Boboniu has a BBY collection. His collection looks like a sequence. For example:

We can use sequence $$$a=[1,2,3,3,2,1,4,4,1]$$$ of length $$$n=9$$$ to denote it.

Now Boboniu wants to fold his collection. You can imagine that Boboniu stick his collection to a long piece of paper and fold it between currencies:

Boboniu will only fold the same identifier of currencies together. In other words, if $$$a_i$$$ is folded over $$$a_j$$$ ($$$1\le i,j\le n$$$), then $$$a_i=a_j$$$ must hold. Boboniu doesn't care if you follow this rule in the process of folding. But once it is finished, the rule should be obeyed.

A formal definition of fold is described in notes.

According to the picture above, you can fold $$$a$$$ two times. In fact, you can fold $$$a=[1,2,3,3,2,1,4,4,1]$$$ at most two times. So the maximum number of folds of it is $$$2$$$.

As an international fan of Boboniu, you're asked to calculate the maximum number of folds.

You're given a sequence $$$a$$$ of length $$$n$$$, for each $$$i$$$ ($$$1\le i\le n$$$), you need to calculate the maximum number of folds of $$$[a_1,a_2,\ldots,a_i]$$$.

Input format:
The first line contains an integer $$$n$$$ ($$$1\le n\le 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le n$$$).

Output format:
Print $$$n$$$ integers. The $$$i$$$-th of them should be equal to the maximum number of folds of $$$[a_1,a_2,\ldots,a_i]$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
Formally, for a sequence $$$a$$$ of length $$$n$$$, let's define the folding sequence as a sequence $$$b$$$ of length $$$n$$$ such that:

- $$$b_i$$$ ($$$1\le i\le n$$$) is either $$$1$$$ or $$$-1$$$.
- Let $$$p(i)=[b_i=1]+\sum_{j=1}^{i-1}b_j$$$. For all $$$1\le i<j\le n$$$, if $$$p(i)=p(j)$$$, then $$$a_i$$$ should be equal to $$$a_j$$$.

($$$[A]$$$ is the value of boolean expression $$$A$$$. i. e. $$$[A]=1$$$ if $$$A$$$ is true, else $$$[A]=0$$$).

Now we define the number of folds of $$$b$$$ as $$$f(b)=\sum_{i=1}^{n-1}[b_i\ne b_{i+1}]$$$.

The maximum number of folds of $$$a$$$ is $$$F(a)=\max\{ f(b)\mid b \text{ is a folding sequence of }a \}$$$.

Example input:
9
1 2 3 3 2 1 4 4 1

Example output:
0 0 0 1 1 1 1 2 2

Example input:
9
1 2 2 2 2 1 1 2 2

Example output:
0 0 1 2 3 3 4 4 5

Editorial:
At first, I'd like to explanation the fold operation in a intuitive way.
Section 1 Fold
To be exact, the origin problem isn't ask us to calculate the number of folds, but the number of folding marks.
Section 1.1 Example 1
For example, you can fold $$$[1,1,1,1]$$$ three times, but you have different method to fold it:
Method 1:
Method 2:
The first method can be represent by folding sequence (defined in the statement) $$$[1,-1,1,-1]$$$. The second method seems to be invalid under the definition of fold (in statement). But really?
In fact, those methods are equivalent. The position of their folding marks are exactly the same, but different in whether it's valley folds or mountain folds.
• For the first method, the folding type of each fold mark is: mountain, valley, mountain.
• For the second method, it's: mountain, mountain, valley.
(Try it yourself!)
Although the second method does only two folds, it folds two layers of paper together so it gets two folding marks in one fold.
Section 1.2 Example 2
For $$$[1,2,2,2,2,1,1,2,2]$$$, there are different folding methods. I'll display two of them:
Firstly to be notice, they have same number of folding marks. The first method can be represent by folding sequence $$$[1,1,-1,1,-1,-1,1,1,1]$$$.
We can change the result of the second method to the first method:
Just change the blue part to red part.
Section 1.3 Summary
In fact, the definition of fold in statement always lead to alternate mountain and valley folds. But you can also use different folding method, because any results can be transform into alternate mountain and valley folds.
key point 1: While folding, we don't care whether it's mountain or valley folds, we just care about the position of folding marks (and the rule in statement).
key point 2: Fix the sequence $$$a$$$, for all folding methods of $$$a$$$, as long as the results of them don't have any available folds, then the number of folding marks of them must be equal, and their results must be the same (or simply reverse sequence).
Although I'll provide proof for these key points, I want you to first think of it intuitively.
Section 2 X-Y-X Folding Method
If understanding the folding operation intuitively, it'll be quite easy to come up with a naive algorithm runs in polynomial time. Now I'll describe a general folding method.
Note: I will consider sequence as a string (with a large character set). The definition of substring, palindrome is similar for sequence.
Let's consider $$$[\ldots,a,b,b,b,c,\ldots]$$$, we can fold three $$$b$$$ into one $$$b$$$ with a mountain fold and a valley fold.
Similarly, consider three continuous substring $$$\textit{XYX}$$$, where $$$Y$$$ is the reverse string of $$$X$$$:
We can fold them into one $$$X$$$ with a mountain fold and a valley fold, according to the first two key points.
Let's call it X-Y-X substring and the folding method X-Y-X fold.
The questions are:
• How many layers of paper are folded during a X-Y-X fold? Can we find a proper folding method where each fold contains only one layer of paper?
• How to fold a string which doesn't contain X-Y-X substring?
Section 3 Key Points
(For high level competitor) I display all the key points firstly which may lead you to final solution quickly.
Intuitively, we will fold $$$a$$$ from left to right. Let's maintain another string $$$b$$$. Each time:
• Push $$$a_i$$$ to the end of $$$b$$$ and check if $$$b$$$ contains new X-Y-X substring. If it does, then fold it.
• Calculate the number of folds of $$$b$$$. Note that this step won't actually change $$$b$$$. After that you get the answer of $$$[a_1,a_2,\cdots,a_i]$$$.
key point 3: Using this folding method, each fold contains exactly one layer of paper.
key point 4: After pushing $$$a_i$$$ to the end of $$$b$$$, $$$b$$$ contains at most one X-Y-X substring and it must be a suffix if exists.
lemma: For string $$$s$$$ and two even palindromic substring $$$s[l_1,r_1]$$$, $$$s[l_2,r_2]$$$ of it, if $$$[l_1,r_1]$$$ contains center position of $$$s[l_2,r_2]$$$ and $$$[l_2,r_2]$$$ contains center position of $$$s[l_1,r_1]$$$, then $$$s$$$ must contain X-Y-X substring.
Use information above, we can figure out a $$$O(n^3)$$$ or $$$O(n^2)$$$ solution.
key point 5: For a string $$$b$$$ which doesn't contain X-Y-X substring, we can only fold its prefix or suffix. And it can be folded at most $$$O(\sqrt{|b|})$$$ times.
key point 6: For a string $$$b$$$ which doesn't contain X-Y-X substring, after pushing an element to the end of $$$b$$$, it has at most $$$O(\log_2|b|)$$$ even palindromic suffixes.
Use information above, we can figure out a $$$O(n\log_2n+n\sqrt{n})$$$ or $$$O(n\log_2n)$$$ solution, which is enough to pass.
Section 3.1 Example
Let's say $$$a=[1,2,2,2,2,1,1,2,2]$$$. So the folding method performs like:
1. $$$b=[1]$$$. It doesn't have any available folds. The answer is $$$0$$$.
2. $$$b=[1,2]$$$. It doesn't have any available folds. The answer is $$$0$$$.
3. $$$b=[1,2,2]$$$. It can be folded once. The answer is $$$1$$$.
4. $$$b=[1,2,2,2]$$$, has X-Y-X substring $$$[2,2,2]$$$, so $$$b$$$ is changed to $$$[1,2]$$$. Plus X-Y-X counter by $$$2$$$. After that, $$$b$$$ doesn't have any available folds. The answer is $$$2$$$.
5. $$$b=[1,2]+a_5=[1,2,2]$$$. It can be folded once. The answer is $$$3$$$.
6. $$$b=[1,2,2]+a_6=[1,2,2,1]$$$. It can be folded once. The answer is $$$3$$$.
7. $$$b=[1,2,2,1]+a_7=[1,2,2,1,1]$$$. It can be folded twice. The answer is $$$4$$$.
8. $$$b=[1,2,2,1,1]+a_8=[1,2,2,1,1,2]$$$, has X-Y-X substring $$$[1,2,2,1,1,2]$$$, so $$$b$$$ is changed to $$$[1,2]$$$. Plus X-Y-X counter by $$$2$$$. After that, $$$b$$$ doesn't have any available folds. The answer is $$$4$$$.
9. $$$b=[1,2]+a_9=[1,2,2]$$$. It can be folded once. The answer is $$$5$$$.
Each time the answer is the sum of X-Y-X counter and number of folds of $$$b$$$.
So the total output will be $$$[0,0,1,2,3,3,4,4,5]$$$.
Section 4 Proof and Understanding
Now I'll describe the proof of some key points. If you have already understand them, skip this section and read the algorithm part.
Section 4.1 Lemma
Description: For string $$$S$$$ and two even palindromic substring $$$S[l_1,r_1]$$$, $$$S[l_2,r_2]$$$ of it, if $$$[l_1,r_1]$$$ contains center position of $$$S[l_2,r_r]$$$ and $$$[l_2,r_2]$$$ contains center position of $$$S[l_1,r_1]$$$, then $$$S$$$ must contain X-Y-X substring.
Lets say $$$l_1<l_2$$$ and $$$|r_1-l_1|\ge |r_2-l_2|$$$. By construction we can get:
Blue lines denotes the center position of two substrings and the red part forms a X-Y-X substring.
Q. E. D.
Section 4.2 X-Y-X and Simple X-Y-X
Let define Simple X-Y-X substring (S-X-Y-X) as a X-Y-X string which doesn't contain any X-Y-X substring except itself.
key point 7: S-X-Y-X string contains exactly one even palindromic suffix. i. e. the Y-X part of it.
Proof: Use reduction to absurdity and the lemma.
Section 4.3 Key Point 4
Description: After pushing $$$a_i$$$ to the end of $$$b$$$, $$$b$$$ contains at most one X-Y-X substring and it must be a suffix if exists.
Let $$$b'=b+a_i$$$.
Just like the picture above, if $$$b'$$$ contains two or more X-Y-X substring, there are three cases:
• black and red
• black and blue
• black and green
All of the three cases can be negate by the lemma or plain discovery.
Q. E. D.
By the way:
• key point 4 shows us that if $$$b'$$$ has a X-Y-X substring, it must be a S-X-Y-X substring.
• key point 7 shows us that that if $$$b'$$$ has a X-Y-X substring, it must be produced by its shortest even palindromic suffix.
Section 4.4 Key Point 5
Description: For a string $$$b$$$ which doesn't contain X-Y-X substring, we can only fold its prefix or suffix. And it can be folded at most $$$O(\sqrt{|b|})$$$ times.
Let's take suffix for example. Each time you can fold an even palindromic suffix if exists. And the length of it must be increasing:
So that it won't contain X-Y-X substring. Similar for prefix. So the folds will end up being
Thus you can fold less than $$$2\sqrt{|b|}$$$ times.
Q. E. D.
Section 4.5 Key Point 6
Description: For a string $$$b$$$ which doesn't contain X-Y-X substring, after pushing an element to the end of $$$b$$$, it has at most $$$O(\log_2|b|)$$$ even palindromic suffixes.
Because of the lemma, even palindromic suffixes of $$$b$$$ cannot both contain center position of each other, so that if we sort them by length, then every even palindromic suffix must be at least twice as long as the previous one:
Thus $$$b$$$ has at most $$$O(\log_2|b|)$$$ even palindromic suffixes.
Q. E. D.
Section 5 Algorithm
The algorithm itself is quite simple. Remember that:
Intuitively, we will fold $$$a$$$ from left to right. Let's maintain another string $$$b$$$. Each time:
• Push $$$a_i$$$ to the end of $$$b$$$ and check if $$$b$$$ contains new X-Y-X substring. If so, then fold it.
• Calculate the number of folds of $$$b$$$. Note that this step won't change $$$b$$$. After that you get the answer of $$$[a_1,a_2,\cdots,a_i]$$$.
Section 5.1 Part 1
Let's maintain $$$S_i$$$, the set of even palindromic suffixes of $$$b$$$ after the $$$i$$$-th time. Since the size of it is $$$O(\log_2n)$$$, use any data structure you want.
Calculate $$$S_i$$$ from $$$S_{i-1}$$$ in $$$O(\log_2n)$$$ is trivial.
Then we simply find the shortest even palindromic suffix of $$$b$$$ and check if it produce a X-Y-X substring in $$$O(\log_2n)$$$.
If it does produce, then we simply fold it, which means remove the shortest even palindromic suffix of $$$b$$$.
Don't forget to update X-Y-X counter.
Section 5.2 Part 2
To calculate the number of folds of $$$b$$$, which doesn't contain X-Y-X substring:
• Let $$$p_i$$$ denote the length of shortest even palindromic suffix of $$$b[1,i]$$$ (index starts from $$$1$$$).
• Let $$$q_i$$$ denote that, if we fold the shortest even palindromic prefix start from $$$b[1,i]$$$ and repeat folding until you can't fold, the position of the first character of the result. i. e. $$$b[1,i]$$$ is folded to $$$b[q_i,i]$$$ finally. Let $$$c_i$$$ denote the number of folds during the process.
Calculate $$$q_i$$$ from $$$q_{i-1}$$$ in $$$O(\log_2n)$$$. Don't forget $$$c_i$$$.
Get $$$p_i$$$ from $$$S_i$$$.
$$$c_i$$$ denotes the number of prefix folds of $$$b$$$.
You can fold suffix of $$$b$$$ using $$$p$$$ and calculate the number of suffix folds in $$$O(\sqrt{n})$$$.
The sum of two above is the number of folds of $$$b$$$. Plus it by X-Y-X counter you'll get the answer.
Remove suffix of $$$b$$$ is trivial.
The total time complexity is $$$O(n\log_2n+n\sqrt{n})$$$.
Section 5.3 Bonus
Can you optimize the time complexity of part 2 to $$$O(\log_2n)$$$ and implement the algorithm in $$$O(n\log_2n)$$$?