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.
1393A - Rainbow Dash, Fluttershy and Chess Coloring:
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$$$.
Code (Java): 89214023
1393B - Applejack and Storages:
There are a few different cases that would allow you to make a square and rectangle: You can have at least $$$8$$$ of one number, which would allow you to make two squares. You can have at least $$$6$$$ of one number and at least $$$2$$$ of another number. You can have at least $$$4$$$ of $$$2$$$ different numbers. You can have at least $$$4$$$ of one number, and at least $$$2$$$ of two different numbers.
At any given point, you can store the number of numbers that have at least $$$2$$$, $$$4$$$, $$$6$$$, and $$$8$$$ occurrences. You can just use $$$4$$$ different variables. To start, make a frequency table of the original array and every time a number exceeds $$$2$$$, $$$4$$$, $$$6$$$, or $$$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$$$, or $$$8$$$. For minus queries, decrement the corresponding frequency and decrement the corresponding variable if the frequency was equal to $$$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 the second case for example, I had to check that there were at least $$$2$$$ numbers with at least $$$2$$$ occurrences because the number that occurs at least $$$6$$$ times is included in the count of numbers that occur $$$2$$$ times.
Code (Java): 89220791
1393C - Pinkie Pie Eats Patty-cakes
Count the maximum number of times that a number appears, let’s call that $$$max$$$. Count the number of numbers that appear $$$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 are $$$a$$$, $$$b$$$, and $$$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 two $$$a$$$’s, so you have to subtract $$$1$$$ to get $$$\lfloor \frac{n-maxfreq}{max-1} \rfloor -1$$$. The distance between the $$$b$$$’s and $$$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 the $$$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$$$ of the same number in the same gap.
Code (Java): 89231755
We can think of a rhombus as $$$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 from $$$0$$$ to $$$n$$$ and left to right, $$$j$$$ goes from $$$0$$$ to $$$m$$$ for my implementation). If $$$\replacedVerb {board}[k-1][j] == \replacedVerb {board}[k][j]$$$ and $$$\replacedVerb {board}[k][j-1] == \replacedVerb {board}[k][j]$$$, then $$$\replacedVerb {upperleft}[k][j] = \min{(\replacedVerb {upperleft}[k-1][j],\replacedVerb {upperleft}[k][j-1])} +1$$$ because you can extend the two upper left triangles to a triangle that is one bigger. If $$$\replacedVerb {board}[k-1][j] \neq \replacedVerb {board}[k][j]$$$ or $$$\replacedVerb {board}[k][j-1] \neq \replacedVerb {board}[k][j]$$$, then $$$\replacedVerb {upperleft}[k][j] = 1$$$ because you cannot extend any triangle, so you have to start over at $$$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$$$ to $$$0$$$ and $$$j$$$ goes from $$$m-1$$$ to $$$0$$$ for my implementation). For the up right triangle, you need to loop from up to down and right to left, and so on.
Code (Java): 89257786
Auto comment: topic has been updated by malachi_toney_goat (previous revision, new revision, compare).
golions orz
Great solutions! However, there exists a
Let $$$dp[i][j$$$] be the number of dress patterns where $$$i, j$$$ is the bottom-most vertex.
Then, $$$dp[i][j] = 1 + min (dp[i - 1][j - 1], dp[i - 1][j + 1], dp[i - 2][j])$$$. 1 is added at the beginning as it is the case that the point $$$i, j$$$ is a solution, and min() is the furthest the pattern exists in the right, top, and left directions.
Note that $$$2 \lt = i \lt n$$$ and $$$1 \lt = j \lt n-1$$$.
Do you have to check for $$$\replacedVerb {board}[i-1][j-1] == \replacedVerb {board}[i-1][j] == \replacedVerb {board}[i-1][j+1] == \replacedVerb {board}[i-2][j] == \replacedVerb {board}[i][j]$$$ before doing the dp state? Just making sure that I understand your solution correctly.
Yes, you do. Sorry, forgot to include that inside the solution. Good catch.
Cool. Thanks for sharing this solution!
Can you please elaborate a bit, why we used min().
$$$dp[i - 1][j - 1]$$$ shows how far in the left direction the dress can extend. Similarly, $$$dp[i - 1][j + 1]$$$ is for the right direction, and $$$dp[i - 2][j]$$$ is for the up direction. We take min() of these values because when we cannot extend one of these directions, we cannot extend $$$dp[i][j]$$$ any more. If we choose a value greater than the min(), in the direction that the min() of the values is facing, the letters would be different from the current letter.
Thanks, I got it.
Why this transition won't work for problem D? (with appropriate checks that the characters are same):
It gives correct output for first 3 testcases, but fails on 4th one.
$$$dp[i - 1][j]$$$ should be $$$dp[i - 2][j]$$$. There is actually parity difference — you can see this by drawing the graph out. Look at the biggest picture provided in the statement. If we want $$$dp[5][4]$$$ to be 2, it means that the character 4 blocks above $$$arr[5][4]$$$ must also be 'd'. This is not checked when you call $$$dp[i - 1][j]$$$. In other words, $$$dp[i - 1][j]$$$ does not check enough nodes in the upward direction.
Got it, great solution!
This is the best solution I found. The official solution was very poorly written.
Nice work! I have an alternate solution for B:
Note that since $$$1$$$ $$$\leq$$$ $$$a_i$$$ $$$\leq$$$ $$$10^5$$$, and similarly for $$$x$$$, we can store the frequencies of each plank length in an array aptly named $$$freq$$$, and increase/decrease it as we gain/remove plank lengths of that type.
We can store the amount of lengths that have frequencies of $$$2s$$$ and $$$4s$$$ in separate variables, with each stick's frequency contributing $$$\lfloor{\frac{freq_i}{2}}\rfloor$$$ and $$$\lfloor{\frac{freq_i}{4}}\rfloor$$$ respectively. Note that the amount of $$$2s$$$ and $$$4s$$$ aren't mutually exclusive, and must be accounted for at the end.
After each operation, we must check whether the number of $$$2s$$$ and $$$4s$$$ are changed. This can be done easily by checking:
This is because when an integer is increased from $$$k-1$$$ $$$(mod$$$ $$$k)$$$ to $$$0$$$ $$$(mod$$$ $$$k)$$$, it is divisible an "extra" time when performing floor division. The opposite is also true for when an integer is decreased from $$$0$$$ $$$(mod$$$ $$$k)$$$ to $$$k-1$$$ $$$(mod$$$ $$$k)$$$.
Finally, to answer each query, we must check if both $$$fours$$$ $$$\geq$$$ $$$1$$$, and $$$twos - 2$$$ $$$\geq$$$ $$$2$$$. This is to account for the planks used for the squares, the $$$4s$$$ being included in the number of $$$2s$$$. If this condition is true, we print "Yes", otherwise "No".
A link to my submission (C++)
Nice solutions!
I had an alternate approach for D, which I thought was interesting even if it might not be the most elegant.
Let's define the one-square pattern as a size $$$1$$$ pattern, the five-square pattern as a size $$$2$$$ pattern, and so on.
Now, let's consider patterns that are centered at each cell individually. Note that if a pattern of size $$$n$$$ centered at a cell $$$(a, b)$$$ exists, then every single pattern of size $$$1$$$ to $$$n-1$$$ centered at a cell $$$(a, b)$$$ also exists. Therefore, to count all the patterns, it suffices to calculate the largest pattern centered at each cell.
Next, note that a pattern of size $$$n$$$ centered at $$$(a, b)$$$ contains all the cells that are a Manhattan distance of $$$n-1$$$ or less away from $$$(a, b)$$$. So, in order for a pattern of size $$$n$$$ to exist at $$$(a, b)$$$, every single cell that is a Manhattan distance of $$$n-1$$$ or less away from $$$(a, b)$$$ must be the same color as $$$(a, b)$$$. This means that, for a cell $$$(a, b)$$$, the size of the largest pattern that is centered at that cell is equal to the smallest Manhattan distance between $$$(a, b)$$$ and any cell that is not the same color as $$$(a, b)$$$.
We can use a multi-source BFS to calculate this value for all the cells. Let's define a "boundary" cell as a cell that is either on the edge of the grid or that is not surrounded on all four sides by cells of the same color. These cells all have values of $$$1$$$. We then just BFS from all the "boundary" cells and update the values for all the remaining cells. The sum of all the values is the answer.
My solution (Java)
(Since the TL was 1 second, I had to make several optimizations to make the BFS run in time. I eventually ended up using an array with two pointers as my queue, which made it work.)
Is this idea managable to pass TL. I thought to implement this idea then saw TL 1 second and gave up.
Ideally the recurrence for $$$dp[i][j]$$$ would be:
(You also have to check whether the up/right/down/left characters are same for each DP direction, i.e. $$$board[i][j] == board[i-1][j]$$$ for $$$dp[i-1][j]$$$)
However, where do you start? The key is that you do 2 passes, one from the top left corner towards the bottom right corner and one from the bottom right corner towards the top left corner.
First pass: $$$dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1])$$$
Second pass: $$$dp[i][j] = max(dp[i][j], 1 + min(dp[i+1][j], dp[i][j+1])$$$
It's a bit tricky to understand why this works, but consider the corners of any rectangle in the grid (with the grid extending further out than shown):
Suppose that for cell
a, the closest different character is at celld. In the 1st pass, we update $$$dp[d_r][d_c] = 1$$$ because the character above and to the left are different (otherwise celldwouldn't have the closest different character from cella). Then, in the 2nd pass, we update the cells on the shortest path from celldtoain the order of the actual path since we're moving up and left in our DP pass.Now suppose that for cell 'c', the closest different character is at cell 'b'. In the 1st pass, we update $$$dp[b_r][b_c] = 1$$$ because the character below and to the left are different (same reasoning as above). Also in the 1st pass, we update the cells on the shortest path from
btod. We know that cellbis the closest different character to celldsince if there were a closer one, it would also be the closest different character to cellc. Finally, in the 2nd pass, we update the cells in the shortest path fromdtoc.You can find similar arguments for the other corner combinations, but I'll leave that as an exercise for the reader.
My submission
malachi_toney_goat Can you mention the
binary_search + priority_queuesolution that people have solved it with. Intuitively, I thought of that solution but couldn't come up with it. Hope you explain it.I thought about binary search for a long time in contest but I didn't find a solution. Here is someone else's comment about how to solve C with binary search and priorityqueue: https://codeforces.me/blog/entry/81216?#comment-677558
You can check out my video solutions (A — D) here:
https://youtu.be/NMbqtVdVZqI
I solved A by simply finding a pattern:
My approach for B was to keep a map and then have three lists: pairs of same numbers (pair), quadruplets of same numbers (quad), and a list of numbers with more than 7 occurrences (many). Then there are three cases to check, using just one element from the "many" list to make two squares right off the bat, using two elements from the "quad" list to make two squares, and finally using one element from the "pair" and one element from the "quad" list to make a rectangle and a square. One thing to keep track of was making sure that you don't use the same number more than it can be used, but you can just do some simple conditional checking to account for that.
I did C by binary searching for the answer. Each time, I would do a validity check by maintaining a queue to keep track of the "unusable" ones. I would loop through each of the n spots and remove and add from the unusable accordingly and then always put the maximum occurrence number. Then, if the map ever turns empty, then return "not valid".
IMPLEMENTATIONS [JAVA] (Might be a bit messy as I am not the best implementer)
what a super duper big hand you have =)))))
can we apply binary search in C??
yes I used binary search .
The explanation of C is daaam good! Thank you for doing the hard work
thank you brother for the solutions :)
Mindblowing explanation for problem C kudos
Problem C Explaination is MIND_BLOWING
Thanks malachi_toney_goat
upperleft[k][j]=min(upperleft[k−1][j],upperleft[k][j−1])i think a +1 is missing hereYes, thank you for pointing that out.
In problem D, I considered the rhombus as two triangles: left and right.
For each cell $$$(i,j)$$$, I calculated two values:
Then, $$$m_{i,j}$$$ = $$$min(b_{i,j},c_{i,j})$$$ is the max size of a rhombus centered in this cell.
The final answer is the sum of all $$$m_{i,j}$$$.
To calculate $$$b_{i,j}$$$ and $$$c_{i,j}$$$, we need:
Then, $$$b_{i,j}$$$ and $$$c_{i,j}$$$ can be calculated easily using $$$a_{i,j}$$$ and dynamic programming:
This solution includes calculations of several arrays, but each of them can be calculated using simple iteration.
My submission
Why is not it enough to have just 2 counters to solve problem B? oO
I have solved the problem this way and the editorial slightly confused me.
You missed adding 1 in the DP update of last solution.
Yes, thank you for pointing that out.
Auto comment: topic has been updated by malachi_toney_goat (previous revision, new revision, compare).
This editorial was far better than codeforces editorial thanks for this editorial :)
My Proof for DIV2 C,extending your logic
Let us assume that there are max-1 boxes and we have to fill them with numbers, and we have to maximize the size of the smallest box, let us first ensure that size of all boxes are 1, we have a list of frequences say
cnt1 , cnt2 , ...but none of these are greater than the number of boxes so let us distribute the first number equally among boxes, if we run out of the first number, let us take the next number and start distributing them equally ( i.e one number per box), by the time we complete the first round we would have exhausted a few numbers, and no box is empty now, size of each box is 1 and we would have used max-1 numbers it reduces to the same problem again, so we can proceed with the same algorithm ,no 2 numbers in the same box will be identical and we can always rearrange numbers within a box to ensure they are max apart.can u explain problem c using binary search
Given a distance D, can you place cakes in some order such that the distance between any 2 cakes of the same filling is >= D?
To solve this sub-problem, we employ a constructive alg:
let's say you're choosing which cake to place on the i-th iteration, among all cakes which are valid (previous cake of same filling is >= D away), greedily place the cake with the max # of occurrences remaining.
Now, we want to find largest D such that there exists some ordering of cakes. We can find max D with binary search
89236305
lrvideckis I cnt understand how that possible function in your code is working (the sub-problem). Can you explain its logic?
I resubmitted with more comments: 94602302
Better than official
Better explanations than the original editorial. Especially in problem B. Thanks a ton for this. If someone wants implementation of the above in C++, here is my solution.
93437519
Very good editorial.Thanks a lot brother
Thanks, Your solution for C is better than original editorial's sol.