Making Towers
Contest: Codeforces Round 809 (Div. 2)
Difficulty rating: 1100
Tags: dp, greedy, math

You have a sequence of $$$n$$$ colored blocks. The color of the $$$i$$$-th block is $$$c_i$$$, an integer between $$$1$$$ and $$$n$$$.

You will place the blocks down in sequence on an infinite coordinate grid in the following way.

1. Initially, you place block $$$1$$$ at $$$(0, 0)$$$.
2. For $$$2 \le i \le n$$$, if the $$$(i - 1)$$$-th block is placed at position $$$(x, y)$$$, then the $$$i$$$-th block can be placed at one of positions $$$(x + 1, y)$$$, $$$(x - 1, y)$$$, $$$(x, y + 1)$$$ (but not at position $$$(x, y - 1)$$$), as long no previous block was placed at that position.

A tower is formed by $$$s$$$ blocks such that they are placed at positions $$$(x, y), (x, y + 1), \ldots, (x, y + s - 1)$$$ for some position $$$(x, y)$$$ and integer $$$s$$$. The size of the tower is $$$s$$$, the number of blocks in it. A tower of color $$$r$$$ is a tower such that all blocks in it have the color $$$r$$$.

For each color $$$r$$$ from $$$1$$$ to $$$n$$$, solve the following problem independently:

- Find the maximum size of a tower of color $$$r$$$ that you can form by placing down the blocks according to the rules.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le n$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output $$$n$$$ integers. The $$$r$$$-th of them should be the maximum size of an tower of color $$$r$$$ you can form by following the given rules. If you cannot form any tower of color $$$r$$$, the $$$r$$$-th integer should be $$$0$$$.

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

Note:
In the first test case, one of the possible ways to form a tower of color $$$1$$$ and size $$$3$$$ is:

- place block $$$1$$$ at position $$$(0, 0)$$$;
- place block $$$2$$$ to the right of block $$$1$$$, at position $$$(1, 0)$$$;
- place block $$$3$$$ above block $$$2$$$, at position $$$(1, 1)$$$;
- place block $$$4$$$ to the left of block $$$3$$$, at position $$$(0, 1)$$$;
- place block $$$5$$$ to the left of block $$$4$$$, at position $$$(-1, 1)$$$;
- place block $$$6$$$ above block $$$5$$$, at position $$$(-1, 2)$$$;
- place block $$$7$$$ to the right of block $$$6$$$, at position $$$(0, 2)$$$.

The blocks at positions $$$(0, 0)$$$, $$$(0, 1)$$$, and $$$(0, 2)$$$ all have color $$$1$$$, forming an tower of size $$$3$$$.

In the second test case, note that the following placement is not valid, since you are not allowed to place block $$$6$$$ under block $$$5$$$:

It can be shown that it is impossible to form a tower of color $$$4$$$ and size $$$3$$$.

Example input:
6
7
1 2 3 1 2 3 1
6
4 2 2 2 4 4
1
1
5
5 4 5 3 5
6
3 3 3 1 3 3
8
1 2 3 4 4 3 2 1

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

Editorial:
When can two blocks of the same color form two consecutive elements of a tower? Formally, if we have two blocks of the same color at indices $$$i$$$ and $$$j$$$ such that $$$i < j$$$, how can we tell if it is possible to place them at $$$(x_i, y_i)$$$ and $$$(x_i, y_i + 1)$$$ respectively?
As it turns out, they can be placed like this if and only if $$$i$$$ and $$$j$$$ have different parities.
First, if they have the same parity, it is impossible to place them this way. Note that $$$x_i + y_i$$$ must have a different parity from $$$x_{i + 1} + y_{i + 1}$$$, since these sums must differ by exactly $$$1$$$. So, if $$$i$$$ and $$$j$$$ have the same parity, then $$$x_i + y_i$$$ must also have the same parity as $$$x_j + y_j$$$. But we want them to be vertically adjacent, which is not possible if their parities must be the same. So, it is impossible to make two blocks with indices of the same parity adjacent to each other.
Next, there is a valid construction if you want to put blocks $$$i$$$ and $$$j$$$ together when they have different parities. Say that block $$$i$$$ will go at position $$$(x_i, y_i)$$$ and block $$$j$$$ goes at position $$$(x_i, y_{i}+1)$$$. If $$$j=i+1$$$, then we are done. Now, let's say that $$$j=i+3$$$. Then, we can place block $$$i+1$$$ at $$$(x_i+1,y_i)$$$ and block $$$j-1$$$ at position $$$(x_i+1,y_{i}+1)$$$. What if $$$j=i+5$$$? Then we can do the same as the previous case, and then put block $$$i+2$$$ at $$$(x_i+2,y_i)$$$ and block $$$j-2$$$ at $$$(x_i+2,y_i+1)$$$. Essentially, we are making the blocks between $$$i$$$ and $$$j$$$ into a horizontal line extending out for $$$\frac{j-i-1}{2}$$$ blocks then coming back in.
If there are already blocks to the right of $$$(x_i, y_i)$$$, then we can do the same construction but extending out to the left. Note that since we cannot move down, at least one of the right and left side must be open.
There are two ways we can go from here:
First, there is a DP solution. Let's imagine the naive $$$\mathcal{O}(n^2)$$$ dp: We say that $$$dp[i][c]$$$ is the maximum size of a tower with color $$$c$$$, such that the last block placed was at index $$$i$$$. The transitions look like this: $$$dp[i][c_i] = \max\limits_{j < i, j \not \equiv i \pmod 2}(dp[j][c_i] + 1)$$$. We check all $$$j < i$$$ such that $$$j$$$ and $$$i$$$ have different parities, then see if adding a block to this tower makes a better solution. To optimize it, we can notice that for the first DP dimension (index), only the parity of the index matters  — for each color, we just need to keep track of the maximum $$$dp[i][c]$$$ for even and odd $$$i$$$.
We will iterate through all blocks $$$a_i$$$, maintaining $$$dp[p][c]$$$, which contains the maximum size of a tower with color $$$c$$$, where the last block included in the tower had an index with parity $$$p$$$ ($$$p=0$$$ indicates an even index, $$$p=1$$$ indicates an odd index). If the current index is even, we set $$$dp[0][c_i] = \max(dp[0][c_i], dp[1][c_i] + 1)$$$. If it is odd, we set $$$dp[1][c_i] = \max(dp[1][c_i], dp[0][c_i] + 1)$$$. The solution runs in linear time.
Alternatively, there's a greedy solution. After selecting a block, the next block selected must always have the opposite parity. Therefore, it makes sense to greedily select the first block of the same color with opposite parity, since it will never improve the answer if we select a later block. For each color, we start from the first block and iterate through, adding each block to the sequence if and only if it has a different parity from the last one.