golions's blog

By golions, history, 4 years ago, In English

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:

Problem A

Code (Java): 89214023

1393B - Applejack and Storages:

Problem B

Code (Java): 89220791

1393C - Pinkie Pie Eats Patty-cakes

Problem C

Code (Java): 89231755

1393D - Rarity and New Dress

Problem D

Code (Java): 89257786

  • Vote: I like it
  • +229
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by golions (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

golions orz

»
4 years ago, # |
  Vote: I like it +55 Vote: I do not like it

Great solutions! However, there exists a

shorter solution for D.
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Do you have to check for $$$\verb#board#[i-1][j-1] == \verb#board#[i-1][j] == \verb#board#[i-1][j+1] == \verb#board#[i-2][j] == \verb#board#[i][j]$$$ before doing the dp state? Just making sure that I understand your solution correctly.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      Yes, you do. Sorry, forgot to include that inside the solution. Good catch.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Cool. Thanks for sharing this solution!

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please elaborate a bit, why we used min().

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Why this transition won't work for problem D? (with appropriate checks that the characters are same):

    dp[i][j]=1+min(dp[i−1][j−1],dp[i−1][j+1],dp[i−1][j])
    

    It gives correct output for first 3 testcases, but fails on 4th one.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is the best solution I found. The official solution was very poorly written.

»
4 years ago, # |
Rev. 4   Vote: I like it +24 Vote: I do not like it

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:

  • if $$$freq_i$$$ is increased and is now equal to $$$0$$$ $$$(mod$$$ $$$2)$$$, then the number of $$$2s$$$ is increased.
  • if $$$freq_i$$$ is increased and is now equal to $$$0$$$ $$$(mod$$$ $$$4)$$$, then the number of $$$4s$$$ is increased.
  • if $$$freq_i$$$ is decreased and is now equal to $$$1$$$ $$$(mod$$$ $$$2)$$$, then the number of $$$2s$$$ is decreased.
  • if $$$freq_i$$$ is decreased and is now equal to $$$3$$$ $$$(mod$$$ $$$4)$$$, then the number of $$$4s$$$ is decreased.

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++)

»
4 years ago, # |
Rev. 2   Vote: I like it +17 Vote: I do not like it

Nice solutions!

I had an alternate approach for D, which I thought was interesting even if it might not be the most elegant.

My idea
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is this idea managable to pass TL. I thought to implement this idea then saw TL 1 second and gave up.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I had the same idea, though I used DP instead
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

golions Can you mention the binary_search + priority_queue solution that people have solved it with. Intuitively, I thought of that solution but couldn't come up with it. Hope you explain it.

»
4 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

You can check out my video solutions (A — D) here:

https://youtu.be/NMbqtVdVZqI

»
4 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

I solved A by simply finding a pattern:

3 -> 2
4 -> 3
5 -> 3
6 -> 4
 ...

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)

Problem A
Problem B
Problem C
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    what a super duper big hand you have =)))))

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

can we apply binary search in C??

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

The explanation of C is daaam good! Thank you for doing the hard work

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

thank you brother for the solutions :)

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Mindblowing explanation for problem C kudos

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Problem C Explaination is MIND_BLOWING
Thanks golions

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

upperleft[k][j]=min(upperleft[k−1][j],upperleft[k][j−1]) i think a +1 is missing here

»
4 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

In problem D, I considered the rhombus as two triangles: left and right.
For each cell $$$(i,j)$$$, I calculated two values:

  • $$$b_{i,j}$$$ = Max size of the left triangle if this cell is the centre of the rhombus
  • $$$c_{i,j}$$$ = Max size of the right triangle if this cell is the centre of the rhombus

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:

  • $$$up_{i,j}$$$ = Number of cell with same color above this cell
  • $$$dn_{i,j}$$$ = Number of cell with same color below this cell
  • $$$a_{i,j}$$$ = $$$min(up_{i,j},dn_{i,j})$$$

Then, $$$b_{i,j}$$$ and $$$c_{i,j}$$$ can be calculated easily using $$$a_{i,j}$$$ and dynamic programming:

  • $$$b_{i,j}$$$ = $$$min(a_{i,j},b_{i,j-1})+1$$$
  • $$$c_{i,j}$$$ = $$$min(a_{i,j},c_{i,j+1})+1$$$

This solution includes calculations of several arrays, but each of them can be calculated using simple iteration.

My submission

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

You missed adding 1 in the DP update of last solution.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by golions (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

This editorial was far better than codeforces editorial thanks for this editorial :)

»
4 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can u explain problem c using binary search

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Better than official

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Very good editorial.Thanks a lot brother

»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Thanks, Your solution for C is better than original editorial's sol.