ch_egor's blog

Codeforces Round #657 Editorial
By ch_egor, 4 years ago, translation, In English

Thanks for the participation!

1379A - Acacius and String was authored by ch_egor, meshanya and prepared by ch_egor, vintage_Vlad_Makeev

1379B - Dubious Cyrpto was authored by jury and prepared by DebNatkh

1379C - Choosing flowers was authored and prepared by grphil

1379D - New Passenger Trams was authored by Helen Andreeva and prepared by KiKoS

1379E - Inverse Genealogy was authored and prepared by voidmax and I_love_myself

1379F2 - Chess Strikes Back (hard version) was authored by 300iq and prepared by isaf27

Tutorial is loading...
vintage_Vlad_Makeev code
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +107
  • Vote: I do not like it

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

Thank you for the fast editorial.

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

pretest 2 was a nightmare. but anyway thanks for the fast editorial

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

I used binary search for B.

Here's my submission: 87322797

I basically fixed my lower bound and upper bound to M+(R-L) and M+(L-R). Let them be up and lo respectively. Now, we need some values of A.N such that the inequality lo <= A.N <= up is satisfied. As we know that a lies in the range L-R and that some value of N for some value of A always exists, for every value of A I used binary search to find for every A if some value of N exists.

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

    Explain pls!

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

      Here's my submission: 87322797

      I basically fixed my lower bound and upper bound to M+(R-L) and M+(L-R). Let them be up and lo respectively.
      Now, we need some values of A.N such that the inequality lo <= A.N <= up is satisfied. As we know that a lies in the range L-R and that some value of N for some value of A always exists, for every value of A I used binary search to find for every A if some value of N exists.

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

Can someone point out the flaw in my code? 87334189

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

My video Solution For Problem A And Problem B. Hope you like it

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

Difficulties are not seems like it is div2. Thanks for the fast editorial

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

If you are still getting WA in A, this is an edge case you probably missed.

1
13
abacab?bacaba

Output: No

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

This contest was a Nightmare for me.

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

My approach in C was almost the same as the editorial's approach.
If anyone wants to check the implementation, check out my submission 87337116. :)

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

Questions are quite interesting after many contest.

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

Please make others submission visible.

UPD they are visible now.

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

Were these problems supposed to be solved by 5-8 grade students?

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

"Wrong answer on pretest 2" The contest summarized in 5 words

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

Was it Div 1???

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

Fastest editorial, system testing and least submissions.. records been broken here.

Thanks to iynaur87 for the key update! :-)

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

Very similar problem to F has appeared on the 2019 Canadian Mathematical Olympiad before, you can check it out here.

Edit: you can check the solution to that problem here.

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

    Funny coincidence! I haven't seen this problem. I was inspired by the problem "Grid Guardian" from the GP of America, where you had to count the generalized version of grids from my problem.

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

Plz,tell my mistake for A Code: 87298100

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

    Consider this case

    1

    15

    abac?bacabac?ba

    Your output has two occurrences of "abacaba"

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

my approach to C:

find the maximum element among a[] and b[], if one of the maximum is a[i] then decrease n by 1, add a[i] to the answer, and change a[i] to b[i].

if not, then iterate over all sort and find out the maximum a[i]+(n-1)*b[i].

however this approach is getting WA on pretest 4, can anyone tell me why?

thanks in advance qwq

Update: found hack test case.

1
2 3
100 1
100 1
1 101
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We need to check each b[], and for each b[i], choose all better a[j], and only the remaining number of that b[i].

    So it is more brute force than greedy.

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

      Yeah I understand the correct solution.

      yet I racked my brain and can't figure out why mine is incorrect, so I want to get some sort of countercase or how to construct one

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

Extra fast tutorial

Extra level question(Difficulty similar to div1)

Extra ranks(3K rank after doing just 1 question)

Hope extra rating :)

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

For D, it is also very helpful, that an optimal starting time can always be selected, so that either the trains departure or arrival, coincides with some existing freight train.

Therefore, we can just check all those 2n possibilities, and obtain quite an easy solution, as then we just have to get the number of freight trains in 2 ranges.

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

Many of them solved C using Convex Hull Trick. Is it a standard problem?

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

It could be more balanced, if removed D, shift ABC to BCD and paste easy A.

By the way, problems are insanely amazing!!

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

This contest is too damn hard for Div.2. Aren't you Shaco?

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

Can F1 be solved with maximum bipartite matching and binary search?

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

    I thought of it too, but couldn't reach up to a solution.

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

Here's my approach for B:

We know that we need an $$$a$$$ such that $$$(m+x)/a=n$$$ where $$$n$$$ is any positive number and $$$x$$$ is just any number in between $$$r-l$$$ and $$$-(r-l)$$$. Now fix $$$a$$$ by looping from $$$l$$$ to $$$r$$$. Then $$$x$$$ will have 2 possibilities computed by using the modulo operator as follow:

$$$md1 = m \mod a$$$
$$$md2 = a-md1$$$

Where $md1$ is the number that must be subtracted from $$$m$$$ for the module to be zero and $$$md2$$$ is the number that must be added to $$$m$$$ for the modulo to be zero.

Now $$$b = l+md1$$$ and $$$c = l$$$ if and only if $$$md1 \leq r-l$$$ and $$$m-md1 \neq 0$$$

Or, $$$b = l$$$ and $$$c = l+md2$$$ if and only if $$$md2 \leq r-l$$$

Else, continue iterating on $$$a$$$

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

    can you explain, why two possibilities of x ? md1 and md2 ? can u elaborate this part ?

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

      As I said in the post, $$$m \mod a$$$ is essentially just the number you need to subtract from $$$m$$$ in order for $$$m$$$ to be divisible by $$$a$$$ so if that value is less then $$$r-l$$$ you can always choose $$$b$$$ and $$$c$$$ such that $$$b-c$$$ is your $$$md1$$$.

      But sometimes you need to add to $$$m$$$ rather then subtract from $$$m$$$ and thus the number to try here would be $$$a-md1$$$ and do the same as above.

      I hope it's more clear :)

      E: Submission with idea: https://mirror.codeforces.com/contest/1379/submission/87346264

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

It would have been better if the contest was of 2:30 hrs.

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

Problems were very nice! B was easier than A and A was definitely very tricky unlike usual A. Took me more than 30 minutes! I wonder if the partication was less due to unusual timing or difficult problems. C finally looked like as a usual C from the past (hard).

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

I had a bit different solutions for B and D.

For B, I tried all possible values of a, and then let $$$d = b - c$$$ , $$$z = m \ mod \ a$$$

Then $$$na + d = m \Leftrightarrow \ n = \frac{m - d}{a} \Leftrightarrow d = ka + z$$$

I checked only $$$k = 0$$$ and $$$k = -1$$$ to make shure that $$$n > 0$$$

Code

For D, lets solve problem for $$$ m \leq 10^5$$$. For fixed $$$t$$$ all segments where no freight trains are allowed to depart and should be canceled are in segments $$$[t - k + 1 + i\frac{m}{2}; t - 1 + i\frac{m}{2} ]$$$ for some $$$i$$$. Lets create array $$$a$$$ and add 1 to time when some freight train departs. Then answer is $$$t$$$ whith minimum sum of segment $$$[t - k + 1 ; t - 1]$$$. Let $$$d_i$$$ — time when i-s train departs. Now, lets check not all t from $$$0$$$ to $$$\frac{m}{2}$$$, but only $$$d_i + 1, d_i-1, d_i+k, d_i-k$$$ for all $$$i$$$. Instead of counting sum we can count number of trains in segment with upper_bound.

Why is it correct? I thought, if we can find better answer for another t, we can move this segment to the left or to the right and answer won`t change until we hit some train. So, this solution is also $$$O(n \log n)$$$

Code

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

Can somebody please explain B ?? Not able to understand what to do after fixing some arbitrary value of a.

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

I am unable to understand the solution for Problem c. Can anyone explain it?

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

    Hi!

    Let's consider both arrays sorted in non-increasing order(greatest element first).

    The main idea is that we can take only one-type of an element of type-b at max ( why? because if you can take the current element of b why go for an element-b that has a lower value). (think).

    Now, let's iterate over all b's from start and see what is the max value we can take with them!

    How to do that? Let's say the current b[i] is bi , (note that array b and is sorted)

    It's understandable that we should take all the a's that are greater than this bi ( think). So we first calculate all the a's that are greater than bi. let's say the count is x and the total sum they provide is val

    Now, if ai (the type-a for our current bi) is not in that x, we'd have no choice but to take it if we want to use current bi.

    Hence we have two cases:

    • If ai >= bi (means ai is in those x) : ans = (n - x)*bi + val , because it's better to take x elements that have value greater than bi.
    • If ai < bi (means ai is not in x) : ans = (n-x-1)*bi + val + ai , because we'd have to take our ai if we want to use bi.

    Also, note that if we have x >= n it's just dumb to take any bi (think).

    So, all we need to do is iterate over all b and take max amount we can take.

    Here's my submission : 87331654

    Thanks!

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

      Wow Sir, Very elegant approach.

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

      @Dsxv @Sol1 Can you help me with a test case which can point out what is wrong in my approach?

      My approach: Take the max b[i] (lets call it maxB), add all a[j] >= maxB to the val. Then go through all a[i] and if a[i] is already included, then update ans = max(ans, val+(n-x)*b[i]) else ans = max(ans, (n-x-1)b[i]+a[i]+val).

      Difference is that I think maxB will always give optimal result (which is wrong). Can anyone please give a hack test for this?

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

      Better explanation than the official tutorial. Thanks!

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

      @Dsxv, bro I tried to code what you explained in your post but I am getting a WA at TC5. I have been trying to debug it since last night but was unsuccessful to get my code AC. Please, go through my code and let me know where am I going wrong.

      link to my solution: https://mirror.codeforces.com/contest/1379/submission/87395143

      Your help and time would be much appreciated.

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

        Hi! Sorry for the delayed reply

        It's happening when, m-n-1 has value < 0.

        Here's your AC submission: 87406888

        Thanks!

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

          Thank You for the help, bro. I was not expecting any reply since as a sports programmer everyone of us has lot of problems of ourselves that needs to be debugged, but you talking out time to actually debug someone else's code was very generous.

          Keep on doing this great job, wish you high rating!!

          P.S: We all know how irritating it is to not get an AC even after brainstorming the logic.

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

      Hi.I am having a confusion if ai<bi(the largest b). Eg:- 7 4 1 5 If n=4, first element is seven.Now considering remaining three elements. According to you we will select 1 5 5 (sum is 11).But, if we take 4 4 4 (sum is 12).So, in this case we should not take the largest b. Am I doing something wrong? Please explain. Thanks!

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

        Not really! I will check my answer for every bi. Hence when I'll reach bi = 4 I'd have already visited my ai = 7 and that is the only value greater than me! so my answer would be bi*(n-1) + pref, where pref = 7. If I misinterpreted your doubt, feel free to ask again! Thanks!

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

          I did this for just largest value of b and calculated the max sort sum for remaining values.This is failing on Test Case 2. I got your approach which is the correct one but how this one is failing?

          include<bits/stdc++.h>

          using namespace std; vector<pair<long long ,long long> > v; vector v1; bool comp1(long long a,long long b) { if(a>b) return true; return false; }

          bool comp(pair<long long,long long> p1,pair<long long,long long> p2) { if(p1.first>p2.first and p1.first>p2.second) return true;

          if(p1.second>p2.first and p1.second>p2.second)
    return true;
return false;

          } int main() { int t; long long a,b,n,m;

          cin>>t;

while(t--)
{
    cin>>n>>m;
    v.clear();
    for(int i=1;i<=m;i++)
    {
       cin>>a>>b;
       v.push_back(make_pair(a,b));
    }
    sort(v.begin(),v.end(),comp);


    long long c=0;
    for(int i=0;i<v.size();i++)
       c=max(c,v[i].second);

    long long sum=0;
    int pos=0;

    for(int i=0;i<v.size();i++)
    {
       if(v[i].first>=c)
       {
          sum+=v[i].first;
           pos=i;
       }     
    }   
    n=n-(pos+1);

    v1.clear();
    for(int i=0;i<v.size();i++)
    {
       if(i<=pos)
         v1.push_back(n*v[i].second);
       else v1.push_back(v[i].first+(n-1)*v[i].second);  
    }
    sort(v1.begin(),v1.end(),comp1);

    sum+=v1[0];
    cout<<sum<<endl;
}

return 0;

          } Thanks!

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

            I'm sorry but I am not here to debug codes! If there's anything wrong with logic feel free to ask.

            Also, use some links while sharing code :p

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

      hey, i dont think ur logic will hold...... in case 2 where ai<bi,what if n=x+1,would u still go for ai,or would u choose any b[i],from already chosen a[i]'s

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

        I'd leave this case upon your imagination! (note that you can choose to take no bi)

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

Approach to problem D: squeeze all m_i to a circle of length m/2. For all points with coordinate p in the circle, (p, p + k) represent locus of points where t cannot be 'inside' it. Then, the problem is equivalent to removing minimum number of points on that circle such that there'll exist two consecutive points of distance at least k. To find it, we can keep track of # (say ins[] )points inside (p,p+k) for all p using pointers (87364059). Then, we can take the point p with minimum ins and delete all point inside (p,p+k). However, I couldn't pass it. Can you find mistakes in this approach?

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

Can someone help me understand where my code is giving wrong answer.Thanks in advance https://mirror.codeforces.com/contest/1379/submission/87357034

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

Problem A and B has same difficulty rating but problem B has far more points than A. Even(for me) B seems easier than A...Is it fair? Would get more (+) if started with B... :(

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

Can someone share in what topic/concept question C belong? I want to practice more such problems, but I am unable to get where exactly does this belong.

P.S: Contest time should have been 2:30 mins.

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

Can anyone tell me what's wrong with this submission? Implements the same idea as the editorial but gets WA on test 5;(

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

Did anyone else waste time trying to solve problem A in O(n)? :|

In case the count of 'abacaba' was 0 (>=2 or 1 are easy cases) I did the following:

Created a list of starting indexes of occurrences of possible 'abacaba'.

Then I iterated over the list, realizing the that a problem can occur only in the following: If the next possible starting index is +4 or +6, and after the current occurrence there is 'caba' or 'bacaba' respectively.

For example, 'abac???caba' is a problem, and 'abacab?bacaba' is a problem. These are the only types of problems, if this doesn't happen, you've found your starting index.

In the meantime the solution was to just plug the substring and count the number of occurrences :<

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

There are a lot of grammatical errors in the tutorial.

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

Can anyone check this code for me , I get WA on test case 179 in pre test 2 :< ( Problem A )

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

    If you get num == 1 after the first iteration answer will be "YES". It should not depend on "codinh"

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

Why was the time limit for problem F so tight? My $$$\log^2$$$ solution wasn't able to fit in the 2s time limit (but should pass given 3s).

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

    Our bad, none of us wrote a solution with 2d tree. All our AC solutions use 1d tree which work $$$\leq$$$ 0.4 s

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

We can also solve D by dynamic segtrees .. its very much intutive (just like brute force) that way.

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

    dynamic segtrees can always be used in problems where sweepline works.

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

I made a greedy strategy for Problem C but it's giving the wrong answer but I can't figure out where it's going wrong.

I find the pair with max Bi (if there are multiple Bi's with max value) than I select the one with highest Ai. Now we have 1 Ai and n — 1 Bi. Next for every Ai greater than my chosen Bi, I replace that one Bi with Ai. This should be optimal, apparently, it's not. Can anyone help me out here? I know this explanation is messed up and hence I am sharing the link to my unsuccessful submission, hope you'll get an idea.

https://mirror.codeforces.com/contest/1379/submission/87394947

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

    Max Bi isn't always optimal:

    1
2 2
1 10
7 8
    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

One of the most difficult division 2 contest I ever participated. even the first problem was of 1500 rating.

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

A seriously awesome contest after a long time. This one Makes you learn the importance of time where a single question require high implementation and multiple concepts.

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

I am getting wrong answer in test case 5 in problem C. Can Someone please tell me where i am wrong? Submission

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

    You do not handle the case where n is smaller than m. With such input the binary search can return an index bigger than n, and then your formulars are not correct because they calculate with some negative flower count.

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

I had a different solution 87485483 in 1379A - Acacius and String. Since the length of n and the length of "abacaba" is small. I bruteforced all possible variations of "abacaba" with '?'. Then I try all possible places those variations can occur and check if it create another "abacaba".

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

It is better to write "In the form of $$$2^n-1$$$" than "almost a power of two".

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

I have tried to make editorial for questions A-D . please have a look. Language :- Hindi

programming Language :- C++ https://www.youtube.com/watch?v=Omy25cs6JY8&list=PLrT256hfFv5UiRIzkAk6iSHwpwJrJKGMz

→ Reply