vovuh's blog

Codeforces Round #653 (Div. 3)
By vovuh, history, 4 years ago, translation, In English

<almost-copy-pasted-part>

Hello! Codeforces Round 653 (Div. 3) will start at Jun/28/2020 17:35 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 (or 8) problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

  • take part in at least two rated rounds (and solve at least one problem in each of them),
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Daria nooinenoojno Stepanova, Mikhail awoo Piklyaev, Maksim Neon Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round. Also thanks to Artem Rox Plotkin and Dmitrii _overrated_ Umnov for the discussion of ideas and testing the round!

Good luck!

</almost-copy-pasted-part>

UPD: Also thanks to ma_da_fa_ka for testing the round and special thanks to Dmitrii _overrated_ Umnov, Artem Rox Plotkin and, of course, Mike MikeMirzayanov Mirzayanov for discussing ideas and great help with round preparaion!

UPD2: Editorial is published!

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

Comments Comments (339)
| Write comment?
»
4 years ago, # |
  Vote: I like it +26 Vote: I do not like it

vovuh orz!

→ Reply
»
4 years ago, # |
  Vote: I like it +40 Vote: I do not like it

This is missing from the announcement after everyone thought our man vovuh retired...

You know I'm back like I never left (I never left)

Another sprint, another step (another step)

Another day, another breath (another breath)

Been chasing dreams, but I never slept (I never slept)

→ Reply
»
4 years ago, # |
  Vote: I like it +185 Vote: I do not like it

This has been happening in the last couple of months :)

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -7 Vote: I do not like it 
At last vovuh come back in div-3 with his interesting problem-set. We missed him 2 continuous div-3 contest.
#650(He was not there) And #644(Just in the tester list).

Edit: Ok. Only vovuh fans missed him And I am one of them.

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

    Would love to know what vovuh feels after reading such cringey comments/memes.

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

      I also want to know, but i think i have not enough ability to get attention of him. Cause he has so many fans like me.

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

div3 by vovuh are best

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +49 Vote: I do not like it

Deleted

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

I am not able to register for the contest. When I click on the CONTESTS options above, I am able to see only ICPC challenge 2020 registration option.

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

    Go to this Link or wait for ending ICPC Challenge 2020 then can easily register from contest option..

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

I don't see any difference between vovuh problems/non-vovuh problems.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

.

→ Reply
»
4 years ago, # |
  Vote: I like it +137 Vote: I do not like it

Vovuh orz!!!!!!!!!! vovuh is back baby!!!! Missed you Vovuh ❤❤

→ Reply
»
4 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Starting RN I'm gonna explain my family members to keep quiet during 8:00 — 10:00 Tomorrow ! Maybe they'll understand this time

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

    Mine will probably start bugging me on purpose if I say that.

    → Reply
»
4 years ago, # |
  Vote: I like it -19 Vote: I do not like it

vovuh : "The man the myth the legend !"

→ Reply
»
4 years ago, # |
  Vote: I like it -20 Vote: I do not like it

Div-3 and vovuh perfect combination.

→ Reply
»
4 years ago, # |
  Vote: I like it -25 Vote: I do not like it

Finally vovuh is back :)

→ Reply
»
4 years ago, # |
  Vote: I like it -27 Vote: I do not like it

→ Reply
»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -28 Vote: I do not like it

This comment has been deleted due to negative feedback!

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

I don't know about this man vovuh but going through these comments makes me feel there's a good contest ahead ! Wishing it's true ... All the best to all participants

→ Reply
»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

meanwhile vovuh counting all the money he made setting div 3 contests!

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

MikeMirzayanov No more Div.4 rounds?

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

I can nearly always solve div2 C but I can't solve div3 D should div3 D be harder than div2 C ?

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

    Stupid comparison

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

      I compare div4B and div1B. It's not stupid.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it -27 Vote: I do not like it

        u r stupid

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

          Mind the color gap

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it -24 Vote: I do not like it

            I will be orange soon!!! and this stupid community will upvote me for my shittiest comment these greys and greens used to cry and downvote instead of solving problems!!

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

      why it's stupid div1 A is div2 C so div3 D shouldn't be harder than div2 C but I guess it is

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

    What's your feeling today can solved not only D also E1 .

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

      I didn't solve div 3 D since like a year this time it's easier maybe

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

Does Div-4 contests are discontinued?

→ Reply
»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Cringe overloaded

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +138 Vote: I do not like it

meme

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

pls can someone tell me what happens in hacks ?

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

    Checkout this blog post

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    Div-3/educational round Hack phase :
suppose think. A test can fail a problem .But that was not in the pretest system case.So that problem showed accepted..Then anyone can hack that problem by that case in the 12 hours hacking phase.And the defender no of solved problem-=1. But hacker did not get any point.
    → Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I know here is not a good place to ask this question but what happened for div4 contests ??

are they removed from codeforces contests or we can see them back soon ??

→ Reply
»
4 years ago, # |
  Vote: I like it +18 Vote: I do not like it

It is high time to introduce filters to comments section on codeforces -_-.

→ Reply
»
4 years ago, # |
  Vote: I like it -15 Vote: I do not like it

Harder than usual div 3 :)

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -26 Vote: I do not like it

    In my opinion no. A-E1 obvious, E2, F — impossible.

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

      Why do you have Wrong Submissions on obvious questions?

      Jokes aside, obviously, if you know a concept or saw some observation, it is easy for you. Don't discourage others.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it -45 Vote: I do not like it

        lol you are grey... there is no problem that obvious for you

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

      why u guys friending my alt acc for div3/div4 rounds?

      → Reply
»
4 years ago, # |
  Vote: I like it +12 Vote: I do not like it

The gap between E1 and E2??

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

Help me with D after the contest...

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

    D problem was giving TLE when i used unordered_map and when i changed it to map it got accepted. You just have to calculate the minimum number which we have to add to the numbers of the array after which they are divisible by k.

    This can be calculated by taking mod.

    for example the numbers are 5,1,3,4 and value of k = 3

    so for the first element we need to add 1 to get the divisible number

    this number can be calculated by taking mod of a[i]-k & k.

    -> (k + (a[i]-k)%k)%k;

    now similarly for other numbers also we'll calculate in the same way so -> 1,2,0,2 is the required array.

    Now Notice that at a time we can select only one element from the above calculated array. It means that when we see 2 or more elements of same type we can't give the same x to them.

    It means we have to calculate the next greater number which must be added so that the given number is divisible by k.

    the next number can be calculated by multiplying k with the number of times this number has previously occurred, which means we have to maintain the hash table for it.

    Your code here...
        long long int n,k;cin>>n>>k;
        long long int a[n],maxm=-1;
        for(int i=0;i<n;i=i+1) scanf("%lld",&a[i]);
        
        map<long long int,long long int>mp;
        vector<long long int>rem;
        
        for(int i=0;i<n;i=i+1)
        {
           long long int val = mod(k-a[i],k);  // taking mod and storing it.
            if(val)rem.push_back(val);
        }
        for(int i=0;i<rem.size();i=i+1)
        {

            long long int val = k*mp[rem[i]] + rem[i];
            mp[rem[i]]++;
            maxm = max(val,maxm);
            
        }
        maxm++;
        printf("%lld\n",maxm);
    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it 
      D problem was giving TLE when i used unordered_map and when i changed it to map it 
got accepted.

      Wow, just tried this and confirm the TLE with unordered_map. Does anyone know why this happens?

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

        unordered_map worst case is linear, so you can assume that your algorithm time complexity is O(n * n) in some cases

        don't use unordered_map when it's not needed and you can solve the problem with map :)

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

        same happened with me in problem D

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

    My approach:

    for all the array elements calculate the value required to make it a number divisible by k and store it in map and keep incrementing its value if it repeats.Then, find the max "value" in the key-value pair and ans= key+(value-1)*k+1. If two keys have the max value, take the max key.

    eg: second example, 5 repeats 3 times. so ans= 5+(3-1)*6+1=18.

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

      Can you explain why this works ?

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

        To make a such that a%k==0 you have to increase a by k-(a%k). Now if there is another element with the value of a , minimum increment to make a%k==0 is k-(a%k). But according to statement we can not choose multiple indices to increment by same x. So the next minimum value is k-(a%k)+k. If there is another element with the value of a then we have to increment it by k-(a%k)+k+k. So generally,

        required minimum increment for a value 'a' = k-(a%k) + (frequency of a - 1)*k

        Maximum of these value for each distinct element is the optimal answer. (As values of other element are less than the answer we can increment them accordingly on the way to the answer )

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

          I think your this approach might not work.

          Consider the case 2 6 3 9 for 3 the minimum required increment = 3 for 9 the minimum required increment = 3

          And max of (3, 3) will give 3.

          But the answer here would be 9

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

            Yes. I'm sorry i forgot to mention a really important thing. when calculating the frequency of each element we must take the mod of them. Because as in your case the increment needed for both 3 and 9 is 3. As we are focusing mainly on the x (increment) 3 and 9 is same for us. (3%6 = 9%6 = 3).

            Then the answer would be,

            6 - 3 + (2 - 1) * 6 = 9

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

    https://codeforces.net/contest/1374/submission/85372487

    Isn't this linear ... why it's giving TLE?

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

      Use map instead and then try your luck

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

        Can you please tell me the logic behind this?

        My code gave TLE when I used unordered_map but got accepted when I used map.

        → Reply
»
4 years ago, # |
  Vote: I like it +106 Vote: I do not like it

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

Now I see why vovuh rounds are so amazing. Thoroughly enjoyed the round!

→ Reply
»
4 years ago, # |
  Vote: I like it +76 Vote: I do not like it

Easy solution to E2: Copy a solution to this problem https://codeforces.net/contest/799/problem/E which is the exact same except you don't have to reconstruct the indices. Then add boring code to reconstruct the indices

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

    nice, 2500 problem for div3 contestants

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

    I tried that but I was failing at test 12. Well if this worked for you then I definitely made some really stupid mistake.

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

https://ideone.com/oNqhoj

My code is obviously wrong (fails sample test case 2 lol).. But I spent more then an hour can't find where my logic is wrong :/.. I'm almost convinced my 24 IS the correct answer haha..

Any help is appreciated. (Would be awesome if you don't spoil the problem but hint me where I went wrong)

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    Try this test case

    1
5 38
15 29 7 15 7

    Edit: answer should be 70. Your code gives 108.

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

      Ty! I finally was able to get rid of WA but then I was struck by TLE :(

      https://codeforces.net/contest/1374/submission/85394497

      Could you identify my bottleneck ? I think the solution is nlog(n) and should pass ..?

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

        Your code has worst case complexity of O(n^2), having worst case when all elements are same.

        See this part in your code 

                for(int i = 0; i < n; i++) {
            if(arr[i] == 0)
                continue;
            while(myset.find(arr[i]) != myset.end())
                arr[i] += k;
            myset.insert(arr[i]);
        }

        For each iteration of inner loop, it will search multiset the number of times value of arr[i] has appeared before in the array. if n same elements have appeared before, then inner loop runs n times, giving complexity of O(n) for inner loop. The outer loop runs n times, giving total complexity of O(n^2).

        → Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Hints for F?

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

    Just simulate. If it does not end in correct ordering, then do one triple swap including two same elements from a[]. The simulate again. If still not correct ordering it is impossible.

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

      Thanks for the solution! I thought of this solution, but I am still figuring how to prove that it will be impossible, in case both simulations fail.

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

        Seems that it does not work good :/

        Here is the submission of #1 85347474 He does count invariants, and if odd parity, does one swap in two same elements.

        Then sorts with triple swaps, but including the indices in comparison, which does not change the order of elements, but makes the parity even.

        → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 3   Vote: I like it +10 Vote: I do not like it

        The idea behind proving whether it is possible/impossible is based on the following idea:

        Define f(P) for some permutation P to be the number of pairs of indices (i, j) such that i and j are the 'wrong way round' — that is, i < j but in the permutation p, j is to the left of i.

        For example if n = 4 and P = {1, 2, 3, 4} then f(P) = 0. f({2, 1, 3, 4}) = 1 and f({4, 3, 2, 1}) = 6 (everything is the wrong way round).

        We claim that each cyclic shift is invariant mod 2 for f(P) — that is, f(P) will change by -2, 0 or 2 with each shift. This is because if [a, b, c] --> [c, a, b] then the pairs (a, c) and (b, c) have reversed (now a, b are to the right of c when before they were to the left). So since there are two changes, then f(P) goes up by 2, stays constant or down by 2.

        This also explains why we need to do two simulations — if two elements in the original array are the same, then we label them (x, x') in one simulation and (x', x) in the other simulation. Then for the starting configuration, f(P) will be odd for one of them and even for the other, and at least one of them should work.

        From this we can conclude that it's impossible if both below conditions are met:

        • there are no duplicate elements (otherwise by the above, at least one of the x, x' or x', x should work)
        • the original permutation has f(P) odd (then it can never reach 0 since it's always odd)
        → Reply
»
4 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Really enjoyed this round. hail vovuh

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +15 Vote: I do not like it

What's the limit for compilation time? I submitted my code for E2 nearly the end of contest and got this verdict. "Can't compile file: Compilation process timed out." I guessed the reason is that my code is too long, but I don't think I can make it significantly shorter. Do you know how to make it compile?

85381670

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

    I don't think your code is too long xD https://codeforces.net/contest/1373/submission/85026680

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

    We don't specify the exact time limit for compilation, but your solution can't be compiled on my laptop in 30 seconds or even in 1 minute. Probably, it is a bug of GCC or how your solution is written. Try to fix it and submit again.

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

      I manage to make it compile now. Thanks for reply! The reason is I wrote this in my segment tree code. 

      node sg[nax << 2] = {};

      erase "= {}" part fix the issue. I write this since I think it can prevent UB sometimes, probably it causes me UB this time...

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

Can someone tell me where my code is wrong for E1? https://codeforces.net/contest/1374/submission/85384974

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

    what if they only read from both books. what would be your answer, you will print INT_MAX which is wrong

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

      so add this to your code 

      if ( k < both.size() ) ans = both[k] ;
      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you give an example test case? I'm not sure I understand what you are saying because the loop would take care of the case where they read from both books (when i = k)

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

          check out this case, you code will produce negative value. because $$$k - i$$$ is negative and you index the vector with negative indices.

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

    what if both is empty?

    → Reply
»
4 years ago, # |
  Vote: I like it -14 Vote: I do not like it

Please a fast editorial , i need to upsolve

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

What is the test 4 of problem E like ?

I tried to use priority_queue a(only a like), b(only b like), c(both a and b like)

Then with ca(number of chosen a), cb(number of chose b)

  • If (ca < k), I will take min if exist (a.top() and c.top())

  • If (cb < k), I will take min if exist (b.top() and c.top())

  • If (c.top()) is selected I will increase both (ca) and (cb) else I only increase 1 (a.top() -> ca and b.top() -> cb)

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

E2 would have been better easier if it didn't have to traceback indexes.

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

    If you really think so, then try this

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

      Hi! Thank you so much for sharing the problem! It feels good to know my approach for E2 was correct!

      Though had to add a few extra steps because of coordinate compression.

      Here's my submission for 799-E -- 85410030 (solved using two BITs , same as E2)

      Although my thought still remains, tracing back through BIT would have sucked :p

      Thanks!

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

What a huge implemention on E1.

Three pointers and so many if-else, I am about to not to solve it. Luckily, before the end of the contest I finally solved it by huge implemention :), hope not to be FST.

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

    I think instead of using 3 pointers, you can just iterate over how many books are you taking which Alice and Bob both like. Then it is obvious that you have to take k — (both likes) books from 1 0 and 0 1. Just precalculate the prefix sums.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      I have done the same but it gives WA on test case 5. can you please check it 85387758
      upd : missed case (0,0)

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

        Instead of else b.push_back(t), you have to use else if(B==1) b.push_back(t)

        Because you are also pushing 0 0 values into b, where no one likes the book. Instead, you should push 0 1 values into b, where Bob likes the book.

        I slightly changed your code according to the above logic. Check 85389515.

        → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 4   Vote: I like it +10 Vote: I do not like it

      Yup, there are many ways to solve E1 with easy implementation. You can even just take the minimum number of commonly liked books initially, then keep replacing the two longest individually liked selections with the shortest one commonly liked one remaining if it makes the answer better.

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

    You could have implemented it directly using priority queue, one for each of the possible cases.

    Then greedily go through the input :)

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

    Hi! I think the approach for E1 was fairly straighforward. (maybe)

    I stored time for (0,1) , (1,0) and (1,1) in different arrays and sorted them by non decreasing order of time.
    Also we don't need to store (0,0) (why?)

    Say we can take x amount of (1,1) then we know we have to take k-x from (0,1) and (1,0).

    Let's iterate over all possible case of x and the minimum possible time is answer.

    Here's my submission : 85342055

    Thanks!

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

      Thanks. Best solution for me at least.

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

      Tried doing something different but on the same lines

      Took Three separate vectors for (0,1) , (1,0) and (1,1) , and sorted them

      Then took a variable which would store the answer , Now

      Iterate over three vectors at the same time , keeping variable i for 1,1 and j for 0,1 and 1,0

      if time amount of (1,1) at i is greater than time amount of ((0,1) + (1,0)) at j then add (0,1) + (1,0) at j and j++ else add (1,1) and i++

      But getting WA on test 8

      Here's my code 85373064

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

        My implemention is:
        1. Can (1,1) replace (0,1)+(1,0)?
        (1) (1,1) <=(0,1)+(1,0)
        (2) One of them run out of their "own like" set which means the book only he likes, but he still needs to read book, so just put (1,1) dont need to check anything.
        2. Can (1,1) replace (0,1) or (1,0)
        In this situation, one of them has got k books to read but the other is not. Just check (1,1)<=(0,1) or(1,1)<=(1,0), then just choose (1,1)
        3. Otherwise we just choose the book in their "own like" set
        PS: we also have to check whether the set (1,1) has run out, if so we just go to 3, and get the number of books we need, because we have checked the exist of answer before, which is put all the referenced books in the shared set and check whether both of them have k books to read.

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

          Thanks for the answer , but I dont think you saw my submission

          There was only one typo in a loop (wrote i instead of i1) and Nothing wrong with the logic , got AC

          Iam not completely sure if I understand your 2nd point though

          Thanks for the effort of commenting though

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

      I have also done similar thing. Here's my video Editorial for E1 Video Link

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

    You overkilled it.

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

    https://codeforces.net/contest/1374/submission/85352661

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

How to Solve F ?

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

Why am I getting TLE on test case 8? 85389867

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

    may be your while(1) loop run for long time(>2000ms)

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

      Even now I'm getting TLE. I've tried using very large random test cases. It works for them, but I can't figure out what's causing TLE here

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

        try with map instead of unordered_map

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

        Try using map instead of unordered_map. unordered_map takes O(n) time to search in the worst case but map takes O(log n)

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

D: Could someone please tell why this is giving TLE?

http://codeforces.net/contest/1374/submission/85383846

inline bool c(ll a, ll b) { return (a >= b); }

int main() { ll t; scanf("%lld", &t); while(t--) { ll n, k; scanf("%lld %lld", &n, &k);

ll p = 0;
unordered_map<ll, ll> mxx;
for(ll i = 0; i < n; i++)
{
  ll x;
  scanf("%lld", &x);

  x = x % k;
  if(x == 0)
    continue;

  x = k - x;
  mxx[x]++;
}

for(auto i: mxx)
{
  ll v = i.first + k * (i.second - 1) + 1;
  p = max(p, v);
}

printf("%lld\n", p);

} }

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

    Try using map instead of unordered_map. Because unordered map has a worst case complexity of O(n), your code has a worst case complexity of O(n^2).

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

      Wohhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh, sorry to spam, it blew my mind, Thanks a lot sir, could you please tell when to use map or unordered_map?

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

      Didn't realise this stupidity of mine. Worked around it by using reserve() upto 1e4. I guess it will be hacked.

      I am so stupid I thought unordered_map is obviously faster than map always :|

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

I see C easier than A ;) :v

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

https://codeforces.net/contest/1374/submission/85372487

I think this solution is linear. Anyone explain the reason for TLE?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it 
For D ,Even O(n*t) solution is resulting in TLE , Is there still any scope left for improvement in my code .
Code
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    using map instead of unordered_map, got it Accepted, But could anyone pls explain why did it happen?

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

      Don't use unordered_map or unordered_set they blow up for certain inputs , if you want a detailed explanation read this blog

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

What's wrong with this code. (Problem D) It gives MLE at test case 5. Thanks in advance.

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

    because you create many map keys. For Example fre = {{1, 4}, {100000, 3}}, k = 1000000 You are created keys 2, 3, 4 .... 1000000. if(fre[num] > 0) created this keys

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

      Thanks got it.

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

        You must refer to the next element. By the way, such a solution will not work even in time. use binary search to find the element closest to the current element x. After it has reached the required value. So the asymptotic will become nlog (n), not kn

        → Reply
»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

How to solve D if the first operation can be performed any number of times on each $$$i$$$.

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

    You mean [k = 3, a = {2, 2, 2, 2}]?

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

      I mean let's say $$$k$$$ = 4 and $$$a$$$ = $$$[1,4,8]$$$. In original problem answer would be 4 because we can perform operation $$$a_i = a_i + x$$$ on a particular $$$i$$$ at most once. How to solve it if we can perform it any number of times. Like in this case answer would be 3 as we can perform $$$a_1 = a_1 + 1$$$ and $$$a_1 = a_1 + 2$$$.

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

    If x is answer to the current question, then an O(x).k solution can be easily found for the modified question. We maintain a frequency array of size k, to store the remainders and another frequency array of size k to store currently available remainders . While processing x, we can check if it can make a remainder which is needed, and we can modify accordingly.

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

    I initially didn't read that line and was getting hopeless. I mean there won't be any fast algorithm, I have a felling that there won't be any polynomial time algorithm

    → Reply
»
4 years ago, # |
  Vote: I like it -14 Vote: I do not like it

My A, B, C, D, E1 solution`s
A: 85388328
B: 85388390
C: 85388427
D: 85388457
E1:85388485
If you have questions regarding the logic of the solution or the principle of the code — write here

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

    Why am I getting TLE in this submission for Question D?My Submission

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

      Because worst case time complexity of unordered map in order of n . Solve it by using map

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

      I didnt fully understand the reason, but its in unordered_map. Use the common map and it will work. I will now try to understand why you cannot use unordered_map.
      P.S. I understood the reason. In some cases, unordered_map works for a long time

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

    In E1, is it always necessary to take A and B in pair?

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

      Yes. Since we write the values ​​in set, this will be the most profitable solution.

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

Tutorial of problem C: First, solve this, then assume your output is $$$ans$$$. Now, back to C, and print $$$(n-ans)/2$$$ for each testcase. I wish I've made a clear solution and stay tuned for my YouTube channel :'D

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

Can someone help me in finding bug in my E2(Hard Version) solution?
Here is my solution 85387601
It is failing in 12th test case. Thanks in advance.

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

    Our solution seems to have the same idea. Even my solution is failing on test 12, with the same answer. If someone could help it would be great, thanks

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -65 Vote: I do not like it

Can anyone please tell me what's wrong with my solution in E2??

giving RE on test case 5.

https://codeforces.net/submissions/Lord_Saga

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

    Next time use spoiler or link to share code.

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

    I like this comment //FIRST THINK THEN CODE.

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

    So big comment,hard to read for every-one. Edit it using spoiler & block option or give the code link..

    → Reply
»
4 years ago, # |
  Vote: I like it -62 Vote: I do not like it 
Question D should be rejudged , as it has extreme time limits , there are people who used map , passed their tasks , while i got TLE using unordered_map , which is faster .

In O(n*t) time limit , even the time complexity to take input is O(n*t) , there is no way my solution should fail . Definitely , There is a big scandal behind all this . We want Enquiry.

Hope , Mike sir will look into this matter .
→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it +16 Vote: I do not like it

    Unordered map can run in O(n) per query in the worst case if there are enough collisions. It is trivial to generate cases that cause such behavior for unordered map without custom hashes and would make the solution run in O(t * n ^ 2).

    CF blog that discusses this.

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

    "Definitely , There is a big scandal behind all this"

    Maybe in your mind.

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

    unordered maps are not always faster than maps, as ordered maps can take anywhere between o(1) to o(n) for indexing while maps always take o(logn).

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

    So, How come don' I see any attempt at this contest in your account?

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

what a bad day for me, my rating continously decreasing from past 4-5 contest and my current rating is just 1615 and this contest is unrated for me in which my rank would be in top 10. hope this would never happened to anyone

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

is vovuh from BTS?

→ Reply
»
4 years ago, # |
  Vote: I like it +21 Vote: I do not like it

I'm going to assume that my solution for problem E2 using treap is not the intended one, because that would be very weird for a div3 contest. But I usually try to kill a mosquito with a bazooka during contests, so I'm sure that there is a simpler and nicer way to solve the problem :P

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

    Can you please explain your treap solution?

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

      Fix the amount of books of type 1-1 that you will take. You can calculate how many books of type 1-0 and 0-1 you will need to force that both people have at least k books. Obviously, you will take the ones that have lower cost for each group of books. This works for E1.

      Now for E2, you should keep the same strategy, but maybe you have to use a few more books to complete the M books you need to take. But both people already have at least K books, so you can take any other book you want (even if it is a 0-0 book). Obviously, you will take the smallest amount of books you need (let's say X). Here is where treap comes up to help us: you can use it to calculate the sum of the first X smallest values in the remaining books that you didn't take before.

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

        but why didn't u implement it??????

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

          You can see my submission during contest here :)

          If you are looking for a clean implementation, don't even waste time with my code. I was on a hurry because the contest was reaching its end, so I had to code everything quickly :P

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

        But how do you save the indices of solution set of books? I could calculate the minimum answer using set, but couldn't figure how to find the indices of final answer.

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

          You can keep track of the number of 1-1 books in the optimal solution, sort the unchosen books, and take the smallest m-k books, print them along with the chosen books

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

Can someone explain how to solve E2? I saw some people using treap to solve the problem.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 4   Vote: I like it +7 Vote: I do not like it

    I think the main part of this problem is how to find k-smallest elements sum. Usually you can do this by binary search tree, so treap can do the job. The easiest way to implement for me is to use segment tree that each node store pair of (number of element, sub of element) in subtree. To get sum of k-smallest elements. Check if left node size greater than k or not. If yes, try searching on left subtree, otherwise subtract sum of left subtree and search on right subtree. Fenwick tree can also do the job if you keep two fenwick trees that one store sum and one store number of elements and use binary lifting or binary search to find sum of k-smallest elements.

    I saw many people solve using priority_queue or multiset, but I don't know how it works though.

    Edit: I think I get it now. It’s similar to finding median by priority_queue or multiset. Notice that k is always increasing. So you can simply do the same thing. When you encounter query, just transfer elements between 2 multiset respected to value of k. The total number of operations will still be $$$O(n)$$$

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

Thanks for this contest! Through this contest, I realized that my implementation skill is very very weaker than others In F, I observed the main idea very quickly, but that is all.. I failed to write accurate code...

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

    can you tell your idea for solving F?

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

      For(int e=1;e<=n-2;e++), we find the Farthest minimum value that located in [e~n]. And located in e After that, if the array is sorted, finished. but if not, last two number is not sorted. so in this case, we find two same value in [1~(n-2)] and maximum in last two number is going to that ( we can go either of two same value ) then we only go fowrad one move -> then maximum value can go to last of array

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

        thanks, I was thinking about the same idea

        → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -23 Vote: I do not like it

    Your code for E2 is a mess!

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

    I also face the same issue, for questions rated above 1500-1600. Can anyone provide some tips?

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

      practice question of difficulty :1600 or above.

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

      look at the code of more experienced people. They usually know how to make it in a simple way.

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

https://codeforces.net/contest/1374/submission/85392451 its showing TLE for using map also. pls someone find the fault.

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

    K can be up to $$$10^{9}$$$

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

    Hey, You are running a for loop from 1 to k (1 <= k <= 10^9) This is the reason for TLE. Instead of going through all the numbers from 1 to k just check for those which are present in the map.

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

Can anyone tell me why I am getting this runtime error in TC 5 for E1 ?
Link for submission — https://codeforces.net/contest/1374/submission/85375093
I am pretty sure this has to do something with my comparator function for sort but I cannot figure it out.

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

Can someone help me with D? I am not able to understand what's wrong with my code. Main logic below

lli == long long int

        lli mx = 0, mxval = 0;
        map<lli,lli> mp;
        while(n--)
        {
            lli x;
            cin>>x;
            if(x % k == 0) continue;
            lli diff = (k - x%k)%k;
            mp[diff]++;
            if(mp[diff] >= mx)
            {
                mx = mp[diff];
                if(diff >= mxval)
                    mxval = diff;
            }
        }
        if(mx == 0 and mxval == 0) cout<<0<<endl;
        else cout<<(mx-1)*k + mxval+1<<endl;
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You should skip elements with diff = 0.

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

      diff=0 when (k - x%k). I don't think it will ever be 0

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

        Consider the case $$$x \bmod k = 0$$$.

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

          That won't be because the code will not go to that line then. I have checked it in the line above.

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

    Seems that the mistake is in:

    if(mp[diff] >= mx){
    mx = mp[diff];
    if(diff >= mxval)
        mxval = diff;
}

    You can do this instead:

    if(mp[diff] > mx || (mp[diff] == x && diff > mxval) ) {
    mx = mp[diff];
    mxval = diff;
}

    The reason is that if mp[diff] > mx and diff < mxval you are not updating the mxval but you must do it.

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

      Can you explain why I should update mxval when mp[diff] > mx and diff < mxval. Cause mxval should also be 'max' right? so should be update when mp[diff] >= mx and diff >= mxval

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

        You need to take the maximum mp[diff] no matter what. Then, over all the diff which have the maximum value mp[diff] you should take also the maximum.

        Consider this case:

        3 3
1 2 2

        Correct output: 5.

        That is because the correct results are mx = 2 and mxval = 1, but in your code it gives mx = 2 and mxval = 2 which is incorrect. If you still don't get it just do the simulation by hand.

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

Here is my screencast of this contest, do check out it :)

Link: https://youtu.be/afn_V7YkX3U

On my channel I do educational content, so if you want to improve, make sure to subscribe to the channel!

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

Can Anybody explain me C please

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

    Keep a counter, initialised to zero. Traverse through the string now, whenever you encounter ( counter++, otherwise counter--

    Now if the counter becomes negative at any moment l, it means that you have a extra closing bracket, in this situation move it to the end of the string. This approach will ensure that every opening bracket is matched to some closing bracket. And also set the counter to 0.

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    Suppose you have variable $$$bal$$$ which stands for balance. We go through string from left to right, if we have $$$"("$$$ now then do $$$bal+=1$$$ and $$$bal-=1$$$ if we have $$$")"$$$. The answer is the global minimum value of $$$bal$$$. For example $$$s=)))((((())$$$, then balance will be $$$-1, -2, -3, -2, -1, 0, 1, 2, 1, 0$$$. The most minimal value of $$$bal$$$ was -3, thus the answer is 3. So you can fix the sequence by 3 moves. You can take 3 rightmost opening brackets and move them to the front of the string. So string $$$)))((((())$$$ will become $$$((()))(())$$$.

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

      Hey so will the deformation always occurs in the form of )))(((, can ) or ( appear in between balanced sequences. Cause I'm unable to concretely prove it. Thanks!

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

        not always, you can get string like $$$)())())())(((($$$ answer is 4, and you take last 4 opening brackets and move them to the beginning, you will get $$$(((()())())())$$$

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

How to solve problem D ?

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

Kindly explain the statement of problem E1.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

using min_heap (priority_queue) for D seemed more intuitive to me.

Submission

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -14 Vote: I do not like it

can anyone plz try to hack my first E1 submission i think it is wrong!!
upd-: never mind that solution is correct

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

My Video solution for the contest

A,B,C The video is time stamped for your convenience (check the description).

D
E

→ Reply
»
4 years ago, # |
  Vote: I like it +35 Vote: I do not like it

As usual, video solutions to all problems are available at the end of my screencast of the round.

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

    Thank you for the content. Simple explanations.

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

Can anyone give a proof for the solution to F?

What i used -> sort the first n — 2 part and then if the remaining 2 elements are not sorted then sort them using some element which has a duplicate. Im unable to prove why it works.

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

have the people got the rating for this round anyone please help me

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

    Ratings won't be updated until after the open hacking period is over.

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

In E2, I made 4 arrays, 1st is "common books", second is "books interesting Alice only", third is "books interesting Bob only" and fourth is "books both are not interested in". Then I sorted them and took corresponding books from second and third array and added them to form pairs of books that interest either one of them. After both have read 'k' books of their interest, I am checking if a total of 'm' books have been read.

Let 'num' be the books read till now.

My code is failing on test 12, and with furthur debugging, I found that this case is where num<=m. So now I am taking all the remaining books(common,interest for alice only,interest for bob only and books none of them are interested in) and sorting them by time. after this I am taking the first (m-num) books to get the final ans.

Link to the code

Please can someone help me in debugging. Thanks

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

    That approach isn't necessarily correct. You might want to remove a book interesting to both people and replace it with two books, one interesting to each person.

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

      at each step, I am checking if the common book has a lower time or the combined time of 2 books each interesting to one person. This approach worked for me in E1.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it +9 Vote: I do not like it

        Imagine this testcase for E2:

        4 2 1

        3 1 0

        4 0 1

        5 0 0

        6 1 1

        Your approach probably will print 9 (1, 4) as 6 < 3 + 4 but the answer is 7 (1,2).

        → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -28 Vote: I do not like it

Why map can ac

unordered_map time out problem D:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 5;
int main() {
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    ll a, b, c;
    while(t--) {
        cin >> a >> b;
	// time out
        // unordered_map<ll, ll> mp;
        // ac
        map<ll, ll> mp;
        ll tmpa = 0, tmpb;
        for(ll i = 1; i <= a; i++) {
            cin >> c;
            ll tmp = b &mdash; c % b;
            if(tmp == b) {
                tmp = 0;
                continue;
            }
            mp[tmp]++;
            if(mp[tmp] > tmpa) {
                tmpa = mp[tmp];
                tmpb = tmp;
            } else if(mp[tmp] == tmpa && tmp > tmpb) {
                tmpb = tmp;
            }
        }
        if(mp.size() ==0) cout << 0 << endl;
        else cout << (tmpa &mdash; 1) * b + tmpb + 1 << endl;
    }
 
 
    return 0;
}
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Please consider using spoiler when you want to include code.

    → Reply
»
4 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Hello, I am stuck at this solution as to why it is giving MLE on TC 5. I am just storing the remainders in a map. Please can anyone help?


ll == long long;
loop == for

    int n,k,p=0;cin>>n>>k;
    
    map<int, int> mp;
    bool y=false;
    loop(i,0,n){
        int h;cin>>h;
        h %= k;
        if(h!=0){p++;y=true;}
        mp[(k-h)%k]++;
    }
    ll ans=0,x=0, cnt=0;
    if(!y){
        cout<<0<<endl;return;
    }
    y=false;
    while(cnt<p){
        ll j = x%k;
        if(mp[j]>0){
            mp[j]--;
            if(j!=0)cnt++;
        }
        ans++;
        if(cnt>=p)break;
        x++;
        
    }
    cout<<ans<<endl;

I can see that it should give TLE but why MLE?? Submission[submission:85385727]

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

    I didn't look carefully, but if you write mp[j] and j is not a key in the map, then j will be added to the map as a key with value 0. If you don't want to add a key you can write if(mp.count(j)) instead of if(mp[j] > 0).

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

.

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

For E1, why am I getting WA on Test case 5? 85405609

My approach was that I iterated on the number of books which they should read, such that both of them liked that book. For the rest of the books, I chose greedily.

UPD: Got it fixed :)

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

I have been hacked on problem A. Here is the submission. https://codeforces.net/contest/1374/submission/85298617

This is the first time I have been hacked. It says I got TLE. But my program is O(1). So I am certain that it is right. Can someone please tell me 1) If my program is wrong. 2) If the hack was judged successful incorrectly.

Please help me. This was my best performance. I will drop 3000 ranks due to this incorrect (in my opinion) hack.

Edit: My solution is definitely right. I had to switch from input() to sys.stdin.readline() for it to not be on the brim of TLE.

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

    Note that your solution is fairly slow, the test shows Time: 982 ms

    So I assume the hack also used 50000 testcases, but with bigger input numbers. Which is enough to put it over 1000ms.

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

    Your solution is logically correct but not fast enough. Python is a slower language and your solution only just passed the pretests taking 982 out of 1000 ms.

    There are things you can do to speed it up without switching from python:

    -150ms by removing the unused imports at the top.

    -200ms by buffering the output instead of printing every line (eg 85407621 takes 592ms).

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

      By the way, do you know any way to disable flush on a new line inside print/stdout in python? Couldn't find any From what I see the line on a terminal is always flushed when there is "\n".

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

        To clarify. In Python, printing does not flush stdout. It is the call to input that flushes stdout. The implementation of input is that it first flushes and then calls sys.stdin.readline. So to not flush, simply use something like input = sys.stdin.readline. (tested on CPython3, PyPy2 and PyPy3) .

        Here is a code if you want to play around with what flushes stdout.

        Detect flushing

        Btw, just so you know, the built in IO especially in PyPy is pretty slow. During the competition I used sys.stdin.readline and it ran in 654 ms85296367. Most of the time is spent on IO. Doing IO smarter makes it go down to 140 ms 85416929.

        A while back I made a drop in FastIO for PyPy2 and PyPy3 that fixes these issues of slow built in IO (found https://github.com/cheran-senthil/PyRival). With it, my code runs in 155 ms 85417276. anoubhav's code runs in 202 ms 85417590.

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

          Thanks I tried to determine the flush by observing how characters appear on a terminal and they always appear after "\n", but I guess I misunderstood the concept of flushing.

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

After giving 15 contests I can say that Yes, Ashish Gupta's round has fastest editorial . Who else agree with me?

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

    The editorials of Div 3 rounds are given after the hacking phase.

    15 contest and yet you don't know where are you stand.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      Can you tell ne where I said about the Div 3 editorial, and it's the fact that Ashish Gupta's round have fastest editorial in comparison to other Div 2 contest.

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

        You literally commented under a Div 3 announcement.

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

      I think hacking phase is over now and there aren't any editorial till now

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

Is there any other way to do E1 instead of priority_queues and a lot of if-elses?

→ Reply
»
4 years ago, # |
  Vote: I like it -11 Vote: I do not like it

Video Editorial for E1 Video Link

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

In question D, I used unordered_map, why it is giving TLE and Now I just changed unordered_map to map and my solution is accepted. Can anybody clarify this?

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);
	int T;	cin >> T;
	while(T--) {
		ll n, k;	cin >> n >> k;
		bool allbyk = true;
		ll ans = 1;
		unordered_map<ll, ll> r;
		for (int i = 0; i < n; ++i) {
			ll a;	cin >> a;
			ll rem = a % k;				
			if (rem) {
				allbyk = false;
				r[k - rem]++;
				ans = max(ans, (r[k-rem]*k - rem));
			}
		}
		if (allbyk)
			cout << 0 << '\n';
		else
			cout << ans+1 << '\n';
	}
	return 0;
}

This is my code for reference.

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

    Sometimes, the complexity in unordered map goes to O(n). However, you can define a good custom hash so that you do not blow up because of unordered map. Check the following link for reference:Link by author neal

    → Reply
»
4 years ago, # |
  Vote: I like it -15 Vote: I do not like it

Check out the editorials guys:

Problem E1

Problem D

Problem C

Problem A and B

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it

    tooo many if else in E1....not required... not a good solution

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

where is the editorial??

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

    In Div-3 and educational round it always publish late.. I don't know the reason. But it's annoying.

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

      Because there are open hacking phases in both.

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

        What wrong happens if they publish editorial before the hacking phase done ???

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

          There will be an unfair advantage to the people trying to hack. This is what someone said on this question.

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

            If people take advantage by editorial that's not unfair i think.. Cause hack is a positive things..it's only fail the wrong solution But Not The correct solution.

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

              Sometimes, hacks are given points. In that case it is unfair as you have taken help from the editorial to hack.

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

                In Div-3 & edu no points given..point given just in div2-/div-1/global and but those have not any extra hacking phase.

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

                  You can take down people from the top of the table, with/without solving the problem yourself. You can not receive points directly, but going up on ranking gives you positive delta.

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

When will the ratings be updated?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    I have some months of CF experience , and I observed that whenever we got "Pretest Passed" during contest , in that contest our ratings updated within few hours , but when it's "Accepted" , it takes a lot of time (nearly 14hrs ,I guess) . Can anyone please tell why this all happens ?

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

      deleted

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

        means in div2 contests , there is no open hacking?

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

          deleted

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

          In Div-2 you can only hack by the contest time by lock your on problem.But div-3 & edu round has extra 12hours hacking phase.

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

Hello This is my first contest on codeforces. Please tell me how to find editorial of the contest?

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

Can anyone care to explain who is vovuh?

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

    A competitive programmer From Russia .

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

      Why is he mentioned in comments so much?

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

        Cause People love his creating problem mostly in div-3.

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

Why hasn't the editorial been provided yet? It has been a while since system testing has been completed.

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

Can anyone help me with this, in E1 my solution with long long fails with runtime error, but the exact same code gets accepted with int.

Submission with int — 85434593

Submission with long long — 85434729

Diagnostics says overflow with long long. How is that possible though?

In the image 

Red: Runtime error
Green: Accepted

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

Is my solution for B entirely correct. Submission

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

    It is okay, but a better way of thinking is: prime factorize $$$n$$$, if $$$n$$$ has a prime factor other than $$$2$$$ and $$$3$$$, answer is $$$-1$$$, otherwise, let $$$n = 2^a * 3^b$$$. If $$$a \leq b$$$, then just multiply $$$2$$$, $$$(b - a)$$$ times, then divide by $$$6, b$$$ times. So, answer is $$$2*b - a$$$.

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

there is a message is sent to me about someone else's code is matching with mine, but I can't understand this. And what to do now? I Don't understand how to do now

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

    Just stop doing cheating !

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

      if i'd cheat my rating wouldn’t be just mid 1100, what you think?

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

        How rating related with cheating .Even High rated people do cheating. **Are your share your code with others or submit with two of your accounts ?

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

          my friend and I were doing contest together and he asked for my code. Is this the reason?

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it 
            Yes.That's the reason. Don't share your code and even logic with others during contest ..It's totally violation the rule of contest.
            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              they'll block me now for this?

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

                No for 1st time but yes for 2nd time .

                → Reply
»
4 years ago, # |
  Vote: I like it +12 Vote: I do not like it

how can in div3 a person get rating even though he was expert (his rating was >= 1600) before the contest?
look at rating of user: beethoven97
MikeMirzayanov please look at this

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

    He became expert in the last educational div 2 round.

    He might have registered in div 3 contest before his rating changed in the last educational round.

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

    I think he register for this div-3 when his rating less than 1600.He became expert again from last edu round.

    → Reply
»
4 years ago, # |
  Vote: I like it -13 Vote: I do not like it

Python WINS at something at last! It has a superior default hash function (the address of the object in the behind-the-scenes C implementation, which is pretty much random).

ENJOY all your TLEs for once CPP users, MUHAHAHA (•̀ᴗ•́ )

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

Still waiting for official Editorials. Problem setters should make editorials along with problems.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

Why was my rating changed after round? I've thought that bug with registration when you cyan was fixed...

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

    Watch out if the participate status is Contestant but not Out of competition

    Rounds will be rated for you if you are a Contestant, except for Educational Rounds or Unrated contests.

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

Where I can get the tutorial for E2 and F

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

Why is E1 missing the tag 'three pointers'. my submission:85436260

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

    There are many ideas but tags correspond to the most popular ones

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

Something strange happened with me in this contest... For problem E1, my submission got runtime error on case 35. while it worked fine on my compiler and on ideone.com as well. i tried submitting in C++ 14,11 as well, but result was still same.

when i submitted in C++ 17 64 bit , it got accepted without any changes in code. It would be great if someone could explain this.

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

Can anyone help me with this? The submission 85319608 doesn't get a TLE while 85452045 does. They look exactly the same. I tried hacking the first one using what is now test 3 but was unsuccessful while the same test worked against many other codes with the same asymptotic running time.

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

i did E2 but my implementation is quite messy i have seen solutions of many red coders but i donno why their solution is even messier, can anyone plz explain the logic of solution using BIT or seg tree!!

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

Codeforces Round #653 (Div. 3) D. Zero Remainder Array

In this Problem , if we consider a input — 1 2 5 4 4

then as per the solution provided,the output is 7 but if we conside like —

1 .when x = 1 , we will server one of the 4 (4+1=5 and 5%5=0) then x will become 2 2. when x = 2 , we will add it to the remaining 4 and it will become 6 and x will become 3 3. At this step , x is incremented and becomes 4 4. Now if we add 4 to the 6 , it will become 10 and 10%5==0 and then x becomes 5

So the answer should be 5 . .
Is it ? ? ?

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

    You added $$$2$$$ to the remaining $$$4$$$, which makes it $$$6$$$, and then added $$$4$$$ to it, which is not allowed. You can choose any index at most once. Also, the $$$1$$$ remains in your array.

    → Reply