[Solution] Making Towers solution codeforces

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.

  1. Initially, you place block 11 at (0,0)(0,0).
  2. 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.

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.
Input

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 21052⋅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.

Example
input

Copy
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
output

Copy
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).

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

[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:

It can be shown that it is impossible to form a tower of color 44 and size 33.

 

For Solution

Click Here

Leave a Comment