Making Towers solution codeforces – You have a sequence of 𝑛n colored blocks. The color of the 𝑖i-th block is 𝑐𝑖ci, an integer between 11 and 𝑛n.
Table of Contents
[Solution] Making Towers solution codeforces
You will place the blocks down in sequence on an infinite coordinate grid in the following way.
- Initially, you place block 11 at (0,0)(0,0).
- For 2≤𝑖≤𝑛2≤i≤n, if the (𝑖−1)(i−1)-th block is placed at position (𝑥,𝑦)(x,y), then the 𝑖i-th block can be placed at one of positions (𝑥+1,𝑦)(x+1,y), (𝑥−1,𝑦)(x−1,y), (𝑥,𝑦+1)(x,y+1) (but not at position (𝑥,𝑦−1)(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 (𝑥,𝑦),(𝑥,𝑦+1),…,(𝑥,𝑦+𝑠−1)(x,y),(x,y+1),…,(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 11 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.
The first line contains a single integer 𝑡t (1≤𝑡≤1041≤t≤104) — the number of test cases.
The first line of each test case contains a single integer 𝑛n (1≤𝑛≤1051≤n≤105).
The second line of each test case contains 𝑛n integers 𝑐1,𝑐2,…,𝑐𝑛c1,c2,…,cn (1≤𝑐𝑖≤𝑛1≤ci≤n).
It is guaranteed that the sum of 𝑛n over all test cases does not exceed 2⋅1052⋅105.
[Solution] Making Towers solution codeforces
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 00.
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
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
[Solution] Making Towers solution codeforces
In the first test case, one of the possible ways to form a tower of color 11 and size 33 is:
- place block 11 at position (0,0)(0,0);
- place block 22 to the right of block 11, at position (1,0)(1,0);
- place block 33 above block 22, at position (1,1)(1,1);
- place block 44 to the left of block 33, at position (0,1)(0,1);
- place block 55 to the left of block 44, at position (−1,1)(−1,1);
- place block 66 above block 55, at position (−1,2)(−1,2);
- place block 77 to the right of block 66, at position (0,2)(0,2).
[Solution] Making Towers solution codeforces
In the second test case, note that the following placement is not valid, since you are not allowed to place block 66 under block 55:
