MikeMirzayanov's blog

Codeforces Round #547 (Div. 3) Editorials
By MikeMirzayanov, 5 weeks ago, In English,

Thanks for taking part in the round. I hope you enjoyed the round. It happens that the statements were really easy to understand (thanks to testers). We've got only 38 questions during a round!

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

Comments Comments (63)
»
5 weeks ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

MikeMirzayanov, in code of 1141B - Maximal Continuous Rest should be if (a[i % n] == 1) but there is if (a[i % 2] == 1).

→ Reply
»
5 weeks ago, # |
← Rev. 2   Vote: I like it -13 Vote: I do not like it

The G's STD code is not complete.

→ Reply
»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Thank you so much MikeMirzayanov for this round... I enjoy the problems a lot...

→ Reply
»
5 weeks ago, # |
← Rev. 3   Vote: I like it +10 Vote: I do not like it

E can be solved using binary search also .

→ Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Yes, see this

    → Reply
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      can you please explain , how are you applying binary search, I couldn't solve it in contest because I couldn't find sum to be monotonically increasing or decreasing

      → Reply
      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        The answer exists only when H becomes zero in the first round, or $$$\sum_{i=1}^{\ n} d_i <0 $$$ .
        If $$$\sum_{i=1}^{\ n} d_i >= 0 $$$ , print "-1".

        So, after each round H decreases by some amount, now binary search for the first round in which H becomes negative.

        → Reply
        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
          ← Rev. 3   Vote: I like it 0 Vote: I do not like it

          I also thought to use binary search but could not come up with any idea so i did greedy. Also your code uses the similar idea so binary search can be avoided. Anyway nice to see a binary search solution.

          → Reply
        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Can you tell how are doing the calculations for upper bound of binary search? high = 1e12; high/=(max(1ll,abs(sm)-1)); high+=N;

          → Reply
          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            simply set high =h / sum

            → Reply
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      +1 for username.

      → Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes but its complexity would be high

    → Reply
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      no

      → Reply
      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You are doing a binary search and in each search, you are iterating the whole array to find the answer.

        → Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you for this good editorial.

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

    take the case of array -8 -5 -10 +22 the entire array sums up to -1 so instead of taking whole array stipulated times we find the max prefix sum we can get so as we can cut down on the number of operations.

    → Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In 1141E — Superhero Battle problem, to find x why do we need to add partial prefix sum to H?

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please this, why I'm having Memory Limit Exceeded, on the implementation I did, while editorial says the same.

51582194

Thanks, in advance.

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How should I approach Problem D in Java? I m not able to get the structure of code for this problem in java.

→ Reply
  • »
    »
    5 weeks ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Not sure if you're still looking for a response, but my approach was as follows: Use ArrayDeques for each letter or '?' to store the indices. Then, when matching letters I just polled left and right until either went empty and then matched rest with '?' if I had any '?' remaining. In the meantime, you can track how many pairs you have created and use StringBuilder's insert method to put that at the front of the output. Code: https://codeforces.com/contest/1141/submission/51599198

    → Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone please explain in detail how we get the value of x in Problem C

→ Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Basically, p'[i] + x is the minimum value in the series. So, then it must be equal to 1, as the series can have values from [1,n]. So, x + p'[i] = 1 => x = 1 — p'[i]

    → Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem "Same Sum Blocks (Hard)" for finding all the possible sum if I do the loop like this 

map<ll,vector <pair<ll,ll>> > mymap;
    for(int i=0;i<n;i++){
		 ll tsum=0;
		for(int j=i;j<n;j++){
			tsum+=vec[j];
			mymap[tsum].push_back({i,j});
		}
    }

then I'm trying to find the maximum number of disjoint set but it doesn't give me the optimal answer as you can see here 51596165 can anyone explain why it isn't working?

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there an intended slower solution that was meant to pass F1 but not F2 ?

→ Reply
  • »
    »
    5 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Sure. I did the following. The idea is much more standard but might be trickier to implement if you lack experience at dp. Find all different sums of the segments. Now for each one you can do $$$dp[i]$$$ — the maximal number of disjoint segments of this sum up to position $$$i$$$. Updates can be done straightforwardly by iterating over all $$$j < i$$$ and checking if the sum between $$$j$$$ and $$$i$$$ is the current one or not. That's $$$O(n^4)$$$ at best ($$$O(n^5)$$$ if no prefix sums). 51606155

    Btw you can also AC f2 if you do updates in $$$O(1)$$$ instead of $$$O(n)$$$ lol. That would be $$$O(n^3)$$$. 51606140

    → Reply
    • »
      »
      »
      5 weeks ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Why your $$$O(n^3)$$$ solution passes. :xD. Isn't $$$n=1500$$$ too much for $$$n^3$$$.

      → Reply
      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Welp, I just believed that there are not that many distinct sums such that each of them appear at least twice) Apparently, the number is less than expected $$$O(n^2)$$$. I'd be glad to hear the countertest)

        → Reply
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hi Mike,

      Thanks for your reply. I appreciate you taking the time to explain your solutions. :)

      → Reply
»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

1141A - Game 23 can be also solved using dfs.

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem C . can someone explain me why P[1] = the smallest negative number that I can reach from sum+=q[i] ?

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What is u,p and f in dfs function in Problem G's code given?

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved E with the logic of Arithmetic series like nth number of arithmetic series [ a+(n-1)d ].

→ Reply
»
5 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In 1141D- Coloured boots, i am getting WA in test case #22. Can someone tell me what am i missing??

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem G I thought of first painting the k vertices which have maximum number of neighbors i.e. to paint the k maximum neighbor vertices with color 1 and then paint rest of the vertices. The number of colors required would be then the maximum number of neighbors of remaining n-k vertices. I don't know how to implement this also whether this approach is correct or not.Has someone else followed this strategy.

→ Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    hello .......

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

      you can find the (k+1)th largest degree let's say 'd' and this is the maximum number of color needed to color the graph. Now, you can use DFS to color the edges by initiating some variable let's say 'c' with some integer in between 0 to d-1(assuming 0 indexed color) and each time when you move to unvisited vertex make c = (c + 1)%d.

      → Reply
»
5 weeks ago, # |
← Rev. 6   Vote: I like it 0 Vote: I do not like it

I found something interesting when submitting codes on 1141D - Colored Boots. It's so slow to erase the vector elements using erase() funtion comparing to pop_back(). I got AC after replacing all erase() with pop_back(). TLE submission, AC submission

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E, why are we subtracting minimum prefix partial sum from H? I solved it with binary-search but cannot understand this logic of subtracting minimal prefix partial sum from H.

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem c for calculating value of x why we have taken min_val to be summation of all q[i] instead of finding minimum value from q[i]

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone else having problem with problem G test 24 ?

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Any easier explanation for 1141C

→ Reply
»
4 weeks ago, # |
← Rev. 7   Vote: I like it 0 Vote: I do not like it

1141C

Why we take minimum?

Input

7

-2 6 -3 2 -1 -3

Output

3 1 7 4 6 5 2

If possible can someone explain with the help of above test case?

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In code of 1141G — Privatization of Roads in Treeland why was it necessary to set f=-1 after color and f became equal?

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't understand the working of the code of Problem D.

→ Reply