Hello everyone! At the time I am writing this, there is still no editorial for Round #662. I did very well on this contest and I think my solutions are interesting, so hopefully this can help some people. ↵
↵
[problem:1393A]:↵
↵
<spoiler summary="Problem A">↵
After each turn, you can get 1 block closer to the center from the edge, so you know that answer is probably very close to $n/2$. After drawing out a few cases ($n=4, n=5, n=6$) you can see that the answer is $n/2 + Consider the center column (or column closest to the center if $n$ is even). For that column, you get closer to the center from the edge each time. For even columns, the first turn gets one block, while every turn after that gets two blocks, until the last turn, which fills in the last block, so that takes $\frac{n}{2}+1$ turns. For odd columns, every turn fills two blocks, except for the last turn, which fills in the last block, so that takes $\lfloor \frac{n}{2} \rfloor +1$ turns. The other columns are filled at least as fast. ↵
↵
The answer is thus $\lfloor \frac{n}{2} \rfloor+1$. ↵
</spoiler>↵
↵
Code (Java): [submission:89214023]↵
↵
[problem:1393B]:↵
↵
<spoiler summary="Problem B">↵
There are a few different cases that would allow you to make a square and rectangle:↵
You can have at least8$8$ of one number, which would allow you to make two squares.↵
You can have at least6$6$ of one number and at least 2$2$ of another number.↵
You can have at least4$4$ of 2$2$ different numbers.↵
You can have at least4$4$ of one number, and at least 2$2$ of two different numbers.↵
↵
At any given point, you can store the number of numbers that have at least2, 4, 6$2$, $4$, $6$, and 8$8$ occurrences. You can just use 4$4$ different variables. To start, make a frequency table of the original array and every time a number exceeds 2, 4, 6$2$, $4$, $6$, or 8$8$, increment the corresponding variable. For plus queries, increment the corresponding frequency and increment the corresponding variable if the frequency now equals 2, 4, 6$2$, $4$, $6$, or 8$8$. For minus queries, decrement the corresponding frequency and decrement the corresponding variable if the frequency was equal to 2, 4, 6, 8$2$, $4$, $6$, $8$ (and is now lower because you had to decrement it).↵
↵
Using those four variables, you can calculate if it is possible to make a square and rectangle using the cases described above. Note that in my implementation, for the2second case for example, I had to check that there were at least 2$2$ numbers with at least 2$2$ occurrences because the number that occurs at least 6$6$ times is included in the count of numbers that occur two$2$ times.↵
</spoiler>↵
↵
Code (Java): [submission:89220791]↵
↵
[problem:1393C]↵
↵
<spoiler summary="Problem C">↵
Count the maximum number of times that a number appears, let’s call that $max$. Count the number of numbers thata number appears $max$ times, let’s call that $maxfreq$. The answer is $\lfloor \frac{n-maxfreq}{max-1} \rfloor -1$. ↵
↵
Intuition/how this works: Logically, the numbers that occur the most number of times would have to be closest together, so let’s set those first. We want to make blocks of all the numbers that occur a max number of times and set those as far apart as possible.↵
↵
Say the numbers that occur a max number of times area, b$a$, $b$, and c$c$. We would want to make a sequence that looks like `abc...abc...abc`. ↵
↵
The distance between the a’s is the formula I mentioned above. $n-maxfreq$ subtracts that last block, so you have something like `abc...abc…`. There are now $max-1$ blocks of abc, because there used to be $max$, and you just cut one off. Dividing, $\lfloor \frac{n-maxfreq}{max-1} \rfloor$ gives `abc…`. The distance that you want is `bc…` because that is the distance between the twoa$a$’s, so you have to subtract 1$1$ to get $\lfloor \frac{n-maxfreq}{max-1} \rfloor -1$. The distance between the b$b$’s and c$c$’s and all the other numbers occur $max$ number of times is the same thing.↵
↵
You are always able to place the remaining numbers in such a way that there are no two numbers closer than the distance between thea$a$’s. I do not have a rigorous proof at the moment, but if someone can provide one, that would be great. Intuitively speaking, there are $max-1$ number of gaps between the blocks, and no remaining number occurs more than $max-1$ times, so you never have to place more than 1$1$ of the same number in the same gap.↵
</spoiler>↵
↵
Code (Java): [submission:89231755]↵
↵
[problem:1393D]↵
↵
<spoiler summary="Problem D">↵
We can think of a rhombus as4$4$ triangles (that overlap). The upper left triangle is the triangle between the topmost point, leftmost point, and center. The upper right triangle is the triangle between the topmost point, rightmost point, and center. Each triangle forms what looks like a staircase.↵
↵
For every cell, we calculate the maximum triangle with that cell as the center going in each direction (up left, up right, down left, and down right). The answer is the minimum of the maximum triangle going in each direction.↵
↵
We can calculate the maximum triangle going in each direction using dp. Let’s say we are calculating the upper left triangle. We need to loop from up to down ($k$ goes from0$0$ to n$n$ and left to right, $j$ goes from 0$0$ to m$m$ for my implementation). If $\verb#board#[k-1][j] == \verb#board#[k][j]$ and $\verb#board#[k][j-1] == \verb#board#[k][j]$, then $\verb#upperleft#[k][j] = \min({(\verb#upperleft#[k-1][j],\verb#upperleft#[k][j-1])}$ because you can extend the two upper left triangles to a triangle that is one bigger. If $\verb#board#[k-1][j] != \neq \verb#board#[k][j]$ or $\verb#board#[k][j-1] != \neq \verb#board#[k][j]$, then $\verb#upperleft#[k][j] = 1$ because you cannot extend any triangle, so you have to start over at 1$1$.↵
↵
The direction that you loop for each direction is important. For the down right triangle, you need to loop from down to up and right to left ($k$ goes from $n-1$ to0$0$ and $j$ goes from $m-1$ to 0$0$ for my implementation). For the up right triangle, you need to loop from up to down and right to left, and so on.↵
</spoiler>↵
↵
Code (Java): [submission:89257786]↵
↵
Contest Thoughts:↵
↵
Overall, I actually liked the problems because I was able to find nice solutions. I have no problem with the problems themselves because there are solutions that are easy to implement and interesting to think of (to me). However, I agree with most people that statements could have been better. I didn’t understand Problem A at first. I was fortunately able to understand Problem B correctly the first time I read it, but I agree with everyone who says that the statement was hard to understand.↵
↵
↵
[problem:1393A]:↵
↵
<spoiler summary="Problem A">↵
↵
The answer is thus $\lfloor \frac{n}{2} \rfloor+1$. ↵
</spoiler>↵
↵
Code (Java): [submission:89214023]↵
↵
[problem:1393B]:↵
↵
<spoiler summary="Problem B">↵
There are a few different cases that would allow you to make a square and rectangle:↵
You can have at least
You can have at least
You can have at least
You can have at least
↵
At any given point, you can store the number of numbers that have at least
↵
Using those four variables, you can calculate if it is possible to make a square and rectangle using the cases described above. Note that in my implementation, for the
</spoiler>↵
↵
Code (Java): [submission:89220791]↵
↵
[problem:1393C]↵
↵
<spoiler summary="Problem C">↵
Count the maximum number of times that a number appears, let’s call that $max$. Count the number of numbers that
↵
Intuition/how this works: Logically, the numbers that occur the most number of times would have to be closest together, so let’s set those first. We want to make blocks of all the numbers that occur a max number of times and set those as far apart as possible.↵
↵
Say the numbers that occur a max number of times are
↵
The distance between the a’s is the formula I mentioned above. $n-maxfreq$ subtracts that last block, so you have something like `abc...abc…`. There are now $max-1$ blocks of abc, because there used to be $max$, and you just cut one off. Dividing, $\lfloor \frac{n-maxfreq}{max-1} \rfloor$ gives `abc…`. The distance that you want is `bc…` because that is the distance between the two
↵
You are always able to place the remaining numbers in such a way that there are no two numbers closer than the distance between the
</spoiler>↵
↵
Code (Java): [submission:89231755]↵
↵
[problem:1393D]↵
↵
<spoiler summary="Problem D">↵
We can think of a rhombus as
↵
For every cell, we calculate the maximum triangle with that cell as the center going in each direction (up left, up right, down left, and down right). The answer is the minimum of the maximum triangle going in each direction.↵
↵
We can calculate the maximum triangle going in each direction using dp. Let’s say we are calculating the upper left triangle. We need to loop from up to down ($k$ goes from
↵
The direction that you loop for each direction is important. For the down right triangle, you need to loop from down to up and right to left ($k$ goes from $n-1$ to
</spoiler>↵
↵
Code (Java): [submission:89257786]↵
↵
↵
Overall, I actually liked the problems because I was able to find nice solutions. I have no problem with the problems themselves because there are solutions that are easy to implement and interesting to think of (to me). However, I agree with most people that statements could have been better. I didn’t understand Problem A at first. I was fortunately able to understand Problem B correctly the first time I read it, but I agree with everyone who says that the statement was hard to understand.
