Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

Endagorion's blog

By Endagorion, history, 9 months ago, In English

Keeping track of both Codeforces round and online team contest was a doozy, so this is only the best draft of the editorial I have. Missing problems will gradually be added, and existing explanations may improve over time. Hope you enjoyed the problems, and let me know if anything can be explained better!

UPD: okay, all of the problems are out, and most of the bugs are fixed (I hope). By the way, we had a nice discussion with Errichto on his stream about Div. 2 problems, which some of you may find more approachable. Be sure to check it out, as well as other stuff Errichto creates!

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

(Kudos to Golovanov399 for his neat grid drawing tool)

Tutorial is loading...
 
 
 
 
  • Vote: I like it
  • +217
  • Vote: I do not like it

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

https://codeforces.com/contest/1459/submission/101773389 Why my solution fails in test case 21 . problem div2c

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i don't know that as i was just doing div2 B Now can you help me with div2 B. in very simple language as i didn't get editorial posted here.

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

    No clue what you're trying to do with the mod 3s. Try checking other's solutions for a simpler answer.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    5 1 1 5 9 3 3 1

    Try this test with your code and you'll get 4 as result, which is not correct. The reason it doesn't work is because you didn't count a[3] — a[2] while calculating the gcd of all (a[i] — a[i — 1])

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain why the property used in Problem C is also valid for multiple arguments?

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it +83 Vote: I do not like it

    We can show these properties by definition of $$$\gcd$$$.

    • $$$\gcd(a, b) = \gcd(a, b-a)$$$
    • $$$\gcd(a, b, c) = \gcd(a, \gcd(b, c)) = \gcd(\gcd(a, b), c)$$$

    Then we can extend our claim to multiple arguments by mathematical induction.

    $$$ \gcd(a_1, a_2, \cdots, a_{n-2}, a_{n-1}, a_n) \\ = \gcd(a_1, a_2, \cdots, a_{n-2}, \gcd(a_{n-1}, a_n)) \\ = \gcd(a_1, a_2, \cdots, a_{n-2}, \gcd(a_{n-1}, a_n-a_{n-1})) \\ = \gcd(a_1, a_2, \cdots, a_{n-2}, a_{n-1}, a_n-a_{n-1}) \\ = \gcd(a_1, a_2, \cdots, \gcd(a_{n-2}, a_{n-1}), a_n-a_{n-1}) \\ = \gcd(a_1, a_2, \cdots, \gcd(a_{n-2}, a_{n-1}-a_{n-2}), a_n-a_{n-1}) \\ = \gcd(a_1, a_2, \cdots, a_{n-2}, a_{n-1}-a_{n-2}, a_n-a_{n-1}) \\ \cdots \\ = \gcd(a_1, a_2-a_1, \cdots, a_{n-1}-a_{n-2}, a_n-a_{n-1}) $$$

    Therefore $$$\gcd(a_1 + b_j, a_2 + b_j, \cdots, a_{n-1} + b_j, a_n + b_j)$$$ is equal to $$$\gcd(a_1 + b_j, a_2-a_1, \cdots, a_{n-1}-a_{n-2}, a_n-a_{n-1})$$$.

    Update: We do not need to choose adjacent differences. $$$\gcd(a_1, a_2, \cdots, a_{n-2}, a_{n-1}, a_n)$$$ is also equal to $$$\gcd(a_1, a_2-a_1, \cdots, a_{n-1}-a_1, a_n-a_1)$$$, which can be proved similarly. The important step is to express all but one integers as $$$a_i - a_j$$$ to negate $$$+b_j$$$.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why someone's submissions been skipped and receive no message

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I didn't know the proof for problem B's solution but i solved it.

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

Endagorion Please add implementations to the problems as well it will be really helpful.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem B, when n is odd, k = (n+1)/2.
For n=3, k=2, ans=2*2*3=12.
For n=5, k=3, ans=2*3*4=24.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For n = k + (k-1), if we start with a horizontal step, we can reach :
    k+1 positions horizontally
    k positions vertically
    The total is k(k+1).
    For example, if n = 3 + 2, if we start with a horizontal step, we can reach the positions with a cross :
    x . x . x . x
    x . x . x . x
    x . x . x . x

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Solution sequence for Div2B is also available on OEIS. https://oeis.org/A241496. But I didn't understand the general formula. Can someone explain?

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

.

»
9 months ago, # |
  Vote: I like it +40 Vote: I do not like it

https://youtu.be/1OWGTQpfk5Y — recording of post-contest discussion with Endagorion with analysis of all div2 problems (so up to div1-D)

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can you please provide the code for the above explaination of question D?

»
9 months ago, # |
Rev. 2   Vote: I like it +12 Vote: I do not like it

In problem D (div. 2) isn't the complexity O(n * k * n * A) where A the maximum capacity of a glass? Which in turn is 100^4 (since max n = 100 max k = 100 and max A = 100 )? 100^4 = 100 000 000 dp cells, so the solution should pass yes (with the memory optimization). But your complexity is O(n * k * n * A) I don't get how you got A^2 in there. Please someone explain, thanks.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Good point, thanks. I'll fix it soon.

    • »
      »
      »
      9 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      That fix created some confusion.

      A line above that, $$$A$$$ was used to denote the 'total capacity of the subset'. In the next line, $$$A$$$ is used to denote the 'maximum capacity of the glass'.

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks for pointing it out, I made it more clear now.

»
9 months ago, # |
Rev. 3   Vote: I like it +6 Vote: I do not like it

In Problem-B's explanation,

Last Line:

Shouldn't it be where k=n/2 rounded up, instead of where k=n/2 rounded down?

Endagorion

Someone, do correct me if I am wrong.

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

Endagorion I think that in Problem-E's(div2) explanation

$$$p'$$$ should be equal to $$$v_0 + iv_x + jv_y + kv_z$$$ instead of $$$v_0 + xv_x + yv_y + zv_z$$$

this is part of the paragraph before the last one

Sorry if I am wrong.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You are correct! I'll be fixing all mistakes soon once I finish the editorial for div1F.

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

Why did the rating change again as it was? Endagorion

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No idea honestly. Let's just let CF staff do their thing.

»
9 months ago, # |
  Vote: I like it +25 Vote: I do not like it

Ignoring the short contest time and difficulty gap, I think your rounds are generally of high quality.

Thanks for the round :)

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    Thanks a lot! There's always room to improve for the next time huh.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
9 months ago, # |
Rev. 4   Vote: I like it +8 Vote: I do not like it

Is there a thought process on how to obtain the key observation of 'Latin Square'? It feels very clever and beautiful, but hard to come up with at the same time

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D(Glass half spilled), can anybody tell me , why we are considering taken glasses from n to 1 order.

  • »
    »
    9 months ago, # ^ |
    Rev. 4   Vote: I like it +1 Vote: I do not like it

    Edit : The order of $$$k$$$ doesn't matter too, since we allocate $$$n$$$ 2D dp arrays for each glasses. Sorry!

    We need to calculate $$$dp(i,k,A)$$$ from $$$k=n$$$ to $$$k=1$$$ and from $$$A=sum$$$ to $$$A=0$$$ order because if we do the opposite, 'duplication' will happen in case you use the same $$$dp$$$ table for all glasses. The order of $$$i$$$ doesn't matter, I think you can do either 1 to $$$n$$$ or vice versa.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So, suppose that we are going from 1 to n ans we have taken 3 glasses. Then it may happens that we are taking the same glasses to extract water and then put it in the same glass. Am i getting correct? And can you please explain with an example?

    • »
      »
      »
      9 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Can someone explain this? I also dont understand the need to iterate backwards.

      101822812 Saw this submission, this proceeds in forward direction. So I guess we can proceed both ways.

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        yeah, can anyone please explain why do we need to iterate backwards? Thanks in advance :)

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Would the order of $$$A$$$ matter even if you're using $$$n$$$ 2D Arrays?

      I'm able to get the solution following the correct ordering with only one 2D array, but I thought that the order wouldn't matter if I used a separate 2D array for each i (since there is nothing to duplicate / overwrite).

      Can someone explain why this submission with $$$n$$$ 2D arrays gets a wrong answer? https://codeforces.com/contest/1459/submission/101994708

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Never mind, figured it out by looking at the submission mentioned above.

        The order indeed doesn't matter but I need to make sure that I copy over all the values from the previous array.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can we solve the Row Gcd problem with the given below logic?

(1) sort the array 1

(2) take the array[0] and array[1]

(3) iterate through the array2 and take gcd of array[0]+array[j] and array[1]+array[j]

(4) check divisiblity with all array1[i]+b[j]

(5) if divisible then we got the gcd else dividing the current gcd with prime factor list of gcd and goto step 4 until gcd!=1 or all elements are divisible with gcd.

I had implemented this logic in the contest but I was getting errors in test case 3 on the 29th element. How can I download the test case of the above problem to debug my code? ThankYou

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

my solution can anyone pls tell me how to optimize my code. Thank you.

my logic is:

initially I can move in any four direction north south east west so I made four function calls

then if I move in x-direction(taken care by movex variable) then I have to move in y-direction either positive or negative

if I move in y-direction(taken care by movey variable) then I have to move in x-direction either positive or negative

then if I ran out of moves I insert the coordinates in a set

then I finally print the size of set.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Print for some values and observe the pattern. In your code, even if you apply dp, it will give tle.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ok, thank you I will try and get back to you.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      sorry, I can't come up with any pattern can you help me? thanks

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The first 15 numbers are: 4,4,12,9,24,16,40,25,60,36,84,49,112,64, 144

        1-indexing if n is even ans is p*p where p = n/2+1 Now take odd numbers 4,12,24,40,60,84,112,144 Now you can see that the difference between two numbers is getting increased by 4. You can see my solution for implementation.

        You can also watch errichto(youtube channel) soln for easier soln

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem B, it is given a dp tag .Though there is a nice O(1) solution but can anyone please describe about how to get a dp solution ?

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    You can check my submission for the DP Implementation.. I figure it out by observing the pattern through recursive implementation.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks bro :D . but can you describe that ??

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      seems like it is an iterative solution. Where is your recursive part and you did it in math,I didn't find any dp there.Please can you explain ?

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        For odd numbers, my dp state is calculated as below :

        dp[i] = dp[i-1]*2 + (i+1);
        

        So, I agree that it is a formula only since the previous state of an odd number is an even number only which can be calculated directly through a formula, but it can still be viewed as recursion, although weakly. I could not find a DP flavour more than this amount to this problem

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

Dear Endagorion,

The heading of Problem 1459C (Row GCD) is not translated to English. I could make out that it's the solution of Row GCD based off the description that follows. Kindly fix it!

Thank You!

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How is the graph structured in Flip and Reverse F? The editorial makes it look like something on a straight line, which cant be true

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That's exactly what it looks like though: vertices are balance values in the real line.

»
9 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Can Div2D/Div1B be solved using a top-down approach? Recursion with memoization?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is almost the same as in the tutorial, think it like knapsack: If we fix a total capacity A_s, a total number of glasses that we are going to fill K_s and a current glass i.We have to choices:

    1. Include the glass among the ones we are going to fill: This is possible if we haven't include all the glasses already and we are not exceeding the capacity. In this case we should decrease k_s by 1, because we are including one more glass, and also decrease A_s by the capacity of the current glass. Then just call the recursive function adding the amount of water of the current glass (just like the dp in the tutorial).
    2. Not including it: In this case we ignore the current glass, thus we just call the recursion with a different glass.

    In order to find the solution for a k just iterate over all possible capacities (I did it from 0 to the total capacity of all glasses) and the answer will be the maximum value of min(current_capacity, dp[start_index][current_k][current_capacity] / 2 + total_water_of_all_glasses / 2). Here is my submission 102646662

»
9 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

In problem D, declaring the arrays globally makes the same solution pass which otherwise was failing due to runtime error when I had declared them locally. Could someone elaborate on this point or am I messing up something else?

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain B's editorial with an example? how the editorial is working?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I honestly don't understand the editorial either. but i've observed the pattern through brute force. i also visualized it using R for better understanding about the pattern.

    here's the pdf file

    hope it helps!

»
9 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Finally finished my alternative solution for div1D.

  • Consider the sequence of $$$N+1$$$ prefix differences (number of 1 minus number of 0). The given operation is just reversing a contiguous subsequence between two equal values.
  • Find ranges between equal values for the initial sequence of differences, merge overlapping/touching ranges. We can treat the resulting disjoint ranges independently since a reverse within one of them can't affect the rest.
  • What does an "optimal" result look like? There's no reversible substring starting and ending with 1, so when we throw away leading and trailing 0-s, we must get a string like 1...101...101...1. Proof left to the reader. (Alternatively, we can have no possible operation even at the start.)
  • For each of our substrings corresponding to disjoint ranges, we should be able to achieve this "optimal" situation. Turns out that the final string is now uniquely determined. Let's say that at the end, there are $$$a$$$ leading 0-s, $$$b$$$ trailing 0-s and a string starting and ending with 1 in between.
  • Let's look at the minimum of our sequence of differences. If it's equal to the final difference, then $$$b \gt 0$$$. Proceed recursively without the last 0.
  • Otherwise, the final difference is strictly not the minimum. That means the minimum difference is $$$-a$$$. We know $$$a$$$, time to remove the leading 0-s and proceed recursively again with $$$a=0$$$.
  • Let's look at the maximum difference. That's reached after the last 1. Now $$$b$$$ = maximum difference — final difference.
  • Now $$$a = 0$$$ and $$$b = 0$$$. If the minimum difference is unique, the final string must start with "1(1)", let's remove the leading 1 and again proceed recursively. Otherwise, it must start with "10".
  • All cases are covered and we can find the answer in $$$O(N)$$$.
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please help me understand the proof why we can convert any two Eulerian pathS with the operation of reversing a cycle ?

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem b if r = 51 and b = 61, then blue will win. But when r = 51 and b = 16 then they will end up equal. Am I missing something?

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

does anyone know the proof of this property of gcd? GCD(x,y)=GCD(x−y,y) or any resource for exlanation?

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain me the DP solution of div2-B...Please

  • »
    »
    8 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    105154843

    You can draw the final possible answers for each step in the grid, and then you can summarize the rules.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D why is the total available capacity necessary as a state ?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Maybe elaborate on why you think it shouldn't be.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Okay one reason I found is that since I am aiming to gather max water from a set I have to also know the upper bound of what I can carry. That is why Total sum is needed. Tell me if I am right.

»
7 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

For 1459D - Glass Half Spilled

When I used int for integer variables, I got a runtime error. 107625846

However, when I replaced all int's with int16_t, it gave AC. 107680750

This is the first time I've encountered something like this. Is there a way to avoid runtime error without using int16_t?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what will be recursive solution to div2b

»
5 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Problem C can be solved using following identities

Instead $$$L$$$ write it as $$$R^{-1}$$$ and instead of $$$U$$$ write it as $$$D^{-1}$$$

  • $$$ID = DI$$$
  • $$$CR = RC$$$
  • $$$II$$$ is identity
  • $$$CC$$$ is identity
  • $$$IC = TI$$$ and $$$CI = TC$$$ where $$$T$$$ is the transpose operation
  • $$$IR^{k}I$$$ and $$$CD^{k}C$$$ are same as adding $$$k$$$ to each entry and taking $$$\mod n$$$.

Using these identities, we can reduce the whole expression to an expression where there is atmost one $$$I$$$ or $$$C$$$ and at most one transpose and rest $$$R$$$, $$$D$$$ and add operations which freely commute with each other.