Educational Codeforces Round 112 [Rated for Div. 2]
By awoo, history, 3 years ago, translation, In English

Hello Codeforces!

On Jul/30/2021 17:35 (Moscow time) Educational Codeforces Round 112 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

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

The problems were invented and prepared by Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

Codeforces and Harbour.Space

Hello once again, Codeforces!

It’s been a week since we completed our Harbour.Space Scholarship Contest. It’s was an intense journey, but we are excited to share the results of the contest and take this time to give a word of appreciation to every participant.

One more big shout out to the authors and round coordinator who made this contest happen in a short period of time:

Thank you again for all your hard work.

Congratulations to all the winners and runner-ups who got the opportunity to go through the admissions process and who are eligible for a full scholarship.

1st-3rd Places: Ali.Kh, Yousef_Salama, early-morning-dreams

4th-10th Places: sunyx, amanbol, IMRED, Meijer, loan, kpw29, Huah2

11th-15th Places: dhruvsomani, adamant, Kaitokid, RetiredPlayer, c8kbf

We are pleased to announce that we have reviewed all the winners and will make a final decision about additional scholarships soon. Stay tuned and keep an eye on your inbox!

Remember, to claim the scholarship you need to respond to the email sent 3-4 days ago. And just to make sure email addresses weren’t misspelt, we want to take this opportunity and ask Yousef_Salama, Huah2, adamant, c8kbf, Naseem17 to contact us via email ([email protected]) or directly on Codeforces platform (Harbour.Space)

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 SSRS_ 6 92
2 tourist 6 120
3 WZYYN 6 127
4 Sugar_fan 6 131
5 Tlatoani 6 140

57 successful hacks and 612 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A Geothermal 0:01
B tourist 0:03
C kaiboy 0:04
D dario2994 0:07
E tourist 0:11
F rainboy 0:30

UPD: Editorial is out

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

Comments Comments (201)
| Write comment?
»
3 years ago, # |
  Vote: I like it -105 Vote: I do not like it

i hope i can get top 10 in this contest

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

I hope that this contest will be as good as CF Round #735. And maybe even better

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

Hope this educational round actually have balanced problems unlike the last edu round

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

Please don't start hopeforces again

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

28/07 -> July Cook-Off 2021

29/07 -> Codeforces Round #735

30/07 -> Educational Codeforces Round 112

31/07 -> July Lunchtime 2021

31/07 -> AtCoder Beginner Contest 212

01/08 -> Leetcode Weekly Contest 252

01/08 -> Codeforces Round 736

Raining Contests

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

I hope I can break my unconditional love with FSTs in this round.

:(

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

Please get me out of this losing streak. I'm doubling in rating loss each time.

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

y would anyone waste their time going to some trash unaccredited university, beyond me tbh

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

Good luck, guys!

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

I hope, I won't become turquoise again ^^

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

Good luck to everyone!

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

My first Contest as Expert , will try my best today to move up more !!

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

Hopefully this contest won't make you worry about your setters' safety.

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

It's time to move up.
Good luck for everyone

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

Hope that there won't be any Bitwise-operators tonight.

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

I hope I will solve B in this contest

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

MikeMirzayanov I think something is wrong with my registration. It shows me as a official participant. Can you please fix it? I don't want to lose master.

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

Maybe there's sth wrong with Problem D.

How can a string which length is 1 can be changed to an "beautiful" string ?

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

    Because it is given that we have to consider only "palindrome of length greater than or equal to two".

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

just realized why A is the hardest problem ..

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

The announcement which came for C, should have come early. I was solving a different C, where Alice is looking for the maximum and then Bob goes with the minimum afterward.

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

    No, you should have read the statement more carefully.

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

      Yeah, you are correct. But the announcement itself proves that the statement was unclear.

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

        No,it proves there were more people like you who didn't read the statement properly and were bugging authors with queries.

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

Solved D at 01:50, so happy! ^__^

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

After giving yesterday's contest. This one feels so much better. Regained some confidence again. :)

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

When you solve A,C, and D but not B. Sigh...

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

B had more cases than law courts!

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

    upsolve it, there are at max 6 cases.

    1. for -1

    2. for 0

    other 4 for each direction R,L,U,D

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

    Three cases: -1, can fit horizontally, can fit vertically.

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

      Yeah i guess i complicated it a bit. I checked for both sides and found the minimum.

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

In my opinion, C was much easier than A and B. Thanks.

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

I think A,B is way more harder than C,D and E lol

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

I took 47 minutes to solve problem B (+ penalty), but 9 minutes to solve problem C and 15 minutes to solve problem D....

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

    Solved B in when last 4 minutes were left . Solved C and D long ago. :((

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

I'm so disappointed of myself Idk why my B solution is wrong :( :( I solved C easily I could have read D but I kept saying I will solve this B

Submission

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

    I might have missed it in your code but did you check x1 and y1 to the walls or the walls to x2 and y2?

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

      nah I just realized my mistake I thought we place the second rectangle from (0,0) what a stupid understanding I did

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

Mathforces. 4 wrong submissions for A :(

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

score distribution is same for all problems? i have solve only C and D today but ranking is same who slove only A and B.

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

    Its educational round, that's why !

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

      How educational rounds are different from normal round?lazywitt

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

        They are by definition different, as in there is no semantic meaning in this difference. It's not that "oh this is educational so let's teach them how to treat all problems equally" or anything. It's just by definition. Educational and Div3 rounds follow ICPC style contest rules, where Div1, Div2 and most others follow point based score distribution rule where difficult problems are assigned higher points.

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

Nice contest, E is a very interesting problem.

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

    how did you solve e? I tried doing a nested binary search on the minimum values to take and maximum values but it TLE'd.

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

      I did that too initially, but binary search is actually not needed. Just use two-pointer, extend right bound until the whole interval is covered and then update the answer.

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

      How are using binary search here? After fixing the minimum value, we can do a binary search on max values that's fine. But how can you do a binary search on minimum value ... Then you will have to iterate linearly for minimum value?

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

        Depending on whether or not there are any valid max values(using a certain min value) I will choose to either lower or increase my min value. It sounds pretty dumb and it didn't pass either but if you are really curious you can read my code.

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

    Is downvoting comments complimenting contests becoming a trend?

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

Why was A and B (didn't read rest) so "heavily" math based compared to other general As and Bs? I'm surprised so many people got A, toughest A and B I've ever seen, also first time seeing both the starting two problems are math.. which is surprising considering most of the people can only do A and B (I'd expect something which has to more with programming than complete maths). IMO

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

    Well, you can't have every A be "you have an array and you need to permutate through it and do and do x". Sometimes there has to be math involved, and let's be honest, it wasn't a lot.

    And "toughest A and B I've seen" seems comical when yesterday there was a B rated 1700.

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

    If this is your "toughest A and B", then 1. You haven't done many contests in CF. 2. You don't really know what is a tough problem and what is not.

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

Unfair constraints for python in problem D

same code for c++ https://codeforces.me/contest/1555/submission/124343239 got accepted but

python code got tle https://codeforces.me/contest/1555/submission/124338639

Headquarters MikeMirzayanov, Round Coordinator BledDest, one of the authors Errichto

please look into this.

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

    1) We are not creators of Python. Go complain to them. I think that CF staff only cares about easy problems being solvable in slow languages.
    2) I have nothing to do with this problem. I was mentioned in the blog as an author of the previous round -_-

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

    even though I am a newbie here in code forces or should I say in this whole cp genre .but i know that [1] you must not tag Authors and other GM unnecessarily in (unless you'r LGM YOURSELF). [2] you must wait for editorials to come out before asking too much question [3] be respectful. Nobody here's the homeroom teacher

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

      It's a valid concern. Python may have timed just around the given time limit. So asked organizers to see if time could have been higher for python based submissions. Codechef does it and so do many problems in codeforces have elevated time for problems like the one (https://codeforces.me/contest/1553/problem/B)

      PS: It's not unnecessary tagging. Also even with editorial there are times that solution writer didn't go with simple solution. Tagging is just one thing. If you don't think you are right person to answer, just leave it.

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

        I agree with the first part of your reply regarding elevated time for problems. however, there's a place to ask such questions you don't ask them in comments here and tag people.a better way is to go into to contests "**Ask a question** section..this isn't insta or fb.

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

          Didn't knew there was such a thing. I will check that out

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

    Wow. So many downvotes for no reason. I raised a valid concern for god's sake.

    The problem https://codeforces.me/contest/1553/problem/B. works in 500*3 (about 10**8) complexity , but my solution in today's contest has time complexity of (12*10^5 + 2*10^5) in worst case and i still got TLE.

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

      It's not a new issue. Many times python and java solutions get TLE due to strict time limit(Ask secondThread lol). Nothing can be done after contest.

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

      """Each participant has the right to choose the language that he likes. Together with all its pros and cons. Yes, Java runs a little slower on average, but it has better static analysis in the IDE. It is quite typical for IT tasks that the tool is chosen for the task. And yes, I'm sure it's not a bad thing that sometimes you encounter purely programming difficulties. Understanding that not all ways to read or write data are the same is helpful. In particular, it is important to understand the basics of buffering. Specifically, in your case, knowing the standard library of the language in which you write is also useful. You are using Arrays.sort, but not reading the documentation. Read it finally.""""
      - MikeMirzayanov, March 2021

      Spoiler
      Spoiler
      TL DR
      At last
      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Use pypy with some fast io (fast io is an issue even in c++ so it's kind of fair).

    Your code ACs in 732ms: https://codeforces.me/contest/1555/submission/124358306

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

      ok.I could have simply taken pypy3 instead of python to save my points. But may be in next contest

      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    1. You have a choice of languages, Python is known to be slow, and Codeforces make it very clear that the time limits are the same for all languages. I normally choose to use Python, for ease of writing, in spite of this, but I know that its performance, even using PyPy, can be a problem.
    2. When you select the standard Python interpreter (cPython) as your submission language Codeforces tell that PyPy is normally faster
    3. I am not sure why your code is slow, but my Python code for this problem runs well within the time constraints using either Python or PyPy3. See my contest submission using PyPy3 and the same code run with Python 3
    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

a lot of case works in B :/

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

What the heck is wrong with guy who set up problem B. Like you really want the people to stop logical coding using their thinking skills and just spend 15 minutes considering all the cases like a donkey, and spend another 30 debugging when they get a penalty on the same code. Is this the way the best coding platform wants to evaluate its participants? If yes, then good luck/bye caseforces!

PS : i think the problem setters just wanted to minimize the nuumber of people who could attempt the good questions afterwards by just sticking them to this **** problem!

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

    Nevertheless, I did not like problem B either. It was just implementation, no thinking.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it
      More Cleaner ig

      Basically, you can just try moving it along only x-axis or only y-axis. There is no need to move it in both axes.

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

Problem F:

I used HLD to solve it. Can somebody please tell does there exists any approach without HLD?

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

    Did you use HLD to find usable edges? I'm not sure but I think the problem boils down to single usage of an edge in the tree formed from all the queries and if that's the case, we can split the tree about an edge that can't be used anymore, and re-root the smaller component with another parent? Just like small to large merging. PS : We can keep splitting a tree into forests by this process.

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

      Initially, I made a tree by using only edges which are first time connecting any two different components, then observed that any cycle can span atmost one edge of the tree. After that, used HLD for max path queries. So after that anytime got validation for adding any edge just set all values of all edges to infinite (basically deleted). To check validation, just did a max path query.

      Can you please tell in your approach after splitting into forest how are you checking for any query.

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

        Yes I was thinking of the exact same thing. But just to confirm, please tell me if this is right. First off anytime a tree edge arrives we can add it. Otherwise I found a sum for each node in the tree that denotes the xor of the path from the root to that node. If 2 nodes are in the same tree in the current forest of trees and have xor of Node sums = (edge ^ 1), then they can be connected. Otherwise they cannot be connected. Now if they can be connected, we can disconnect each edge on the path between them using the process i described before and recalculating the sums and root Node for each Node in the smaller component.

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

        dnshgyl21 I think your implementation does not consider the fact that it will be a HLD forest, you always start from root 0.

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

    Model solution is without HLD. We'll describe it in editorial, but shortly, we first find the MST of the graph (using the time when the edges are added as weights, to find the edges that are definitely present in the answer), then create a logarithmic data structure like Fenwick or Segment Tree to mark the edges belonging to a cycle and/or verifying that the cycle we're adding doesn't intersect with some previously created ones.

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

      Can you please describe how can we mark edges on any path in a tree using Segment or Fenwick tree?

      Upd : Thanks,i got it now.

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

        There is a way to range addition on the path from $$$v$$$ to $$$root$$$ and range sum on path from $$$v$$$ to $$$root$$$ using two Segment Trees, but it's not needed here.

        Since each edge will be marked at most once, you can mark edges one by one while asking a sum on path: all using Fenwick tree on Euler tour.

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

could someone tell me whether i am wrong with these i have tried my own these problem link

void solve(vector<int>v[],int src,vector<int>&euler,unordered_map<int,int>&mp,int &counter) {
    euler.pb(src);
    if(mp.find(src) == mp.end()) mp[src] = counter;
    for(auto i:v[src]) {
        counter++;

        solve(v,i,euler,mp,counter);
        counter++;
        euler.push_back(src);
    }
}

void storeminimum(vector<int>&euler,int sq,vector<int>&sqrtd) {
    for(int i=0;i<euler.size();i++) {
        sqrtd[i/sq] = min(sqrtd[i/sq],euler[i]);
    }
}

void Main() {
    int t;
    cin>>t;
    for(int kk=1;kk<=t;kk++) {
        int n;
        cin>>n;
        vector<int>v[n+1];
        for(int i=1;i<=n;i++) {
            int m;
            cin>>m;

            for(int j=0;j<m;j++) {
                int a;
                cin>>a;
                v[i].pb(a);
            }
        }
        // first occurance 
        unordered_map<int,int>foc;


        // store euler path 
        vector<int>euler;
        int count = 0;

        solve(v,1,euler,foc,count);
        int sq = ceil(sqrt(euler.size()));
        vector<int>sqrtd(sq,INT_MAX);
        storeminimum(euler,sq,sqrtd);
        int q;
        cin>>q;
        cout<<"Case "<<kk<<":"<<endl;
        while(q--) {
            int a,b;
            cin>>a>>b;
            int ans = INT_MAX;
            int l=foc[a],r=foc[b];
            while(l<=r) {
                if(l%sq ==0 and l+sq-1<=r) {
                    ans=min(ans,sqrtd[l/sq]);
                    l+=sq;
                } else {
                    ans = min(ans,euler[l]);
                    l++;
                }
            }
            cout<<ans<<endl;
        }
    }
    
}
→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +7 Vote: I do not like it

    Remember to use spoiler next time :) and you are not even talking about a problem from the contest.

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

Are you kidding me? I used old version of problem F statement where cycle was simple if there weren't any repeated edges. And this is the only reason why I didn't get accepted during the contest. I've got accepted in 2 minutes after the round ended, so sad(

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

    We are sorry, we actually noticed the bug in Russian version only, like, 10-15 minutes before the end of the contest :(

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

Can somebody please explain the solution of problem A?

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

    What I did was, write down N as N = 6a + 8b + 10c. Now this can be written as N = 2 * ( 3a + 4b + 5c ). Now let's take ( a + b + c = S ) , so we equation becomes N = 2 * ( 3 * S + b + c ), and b + c = S — a. So this becomes N = 2 * ( 4 * S — a ). Now just find a and S( and one thing if N is odd take N as N + 1, don't know the reason for this but it just worked for odd numbers because they are not divisble by 2 ).

    Now the total time required is TIME = 15a + 20b + 25c. TIME = 5*( 4 * S — a ). This is the answer.

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

      3*S+b+2*c

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

      The question asks to find x, y, z, when 6x+8y+10z is greater than or equal to n, find the minimum value of 15x+20y+25z

      Note that 15/6=20/8=25/10=2.5

      Let us make an equivalent transformation for the condition 6x+8y+10z >= n.

      3x+4y+5z >= (n+1)/2.

      Note that gcd(3,5) = 1 , so all numbers greater than 7=3*5-3-5 can be formed by adding several 3 and 5.

      For the part less than 7, it can be solved directly by violence.

      Code : https://codeforces.me/contest/1555/submission/124347937

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

    if(n<=6) we need only 1 small pizza giving ans as 15 mins Consider x small , y medium and z large pizzas : so number of slices will be n = 6x + 8y + 10z corresponding to it , time spent = 15x + 20y + 25z = 5*n/2 ( in terms of 1st equation) for odd number of slices , u can find that ans modifies to 5*(n+1)/2

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

    I listed out the first 20 values of n:

    1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21
15,15,15,15,15,15,20,20,25,25,30,30,35,35,40,40,45,45,50,50,55

    and noticed that increases by 5 every 2

    out.println(Math.max(15, ((n + 1) / 2) * 5));
    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    If $$$n<=6$$$, print $$$15$$$

    For $$$n>6$$$, if $$$n$$$ is even, print $$$n*2.5$$$

    else print $$$(n+1)*2.5$$$

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

Expected to become an expert today, will probably end up as a pupil...
Spent both the hours on Problem A and got 7 WAs, lol.

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

    Almost did the same, then decided, 'hey, why not check other problems'.

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

      Can't argue with that, though I spent around an hour trying to figure out why exactly was even a brute-force solution giving me WA (Brute Force on n % 120, 120 being the LCM)...
      And I still don't know what exactly is wrong with my code...
      Edit:
      I finally realized that considering n / 120 and n % 120 separately doesn't always give the optimal answer.
      Eg: 121: My output would be 315, while the optimal answer is clearly 305.
      My program would waste 5 slices of pizza, while the optimal answer would only waste one.

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

        I had a similar approach like this but my code also gave WA, did you try for all i in the range 1 to 16. My code was giving wrong answer in this range and correcting for this got me Accepted

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

    If you saw the sample cases, you would've noticed the answer always being ((n+1) * 5) / 2 for n >= 6. Something to do with the fact that 15/6 = 20/8 = 25/10 = 5/2.

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

      Yeah, I guess the McNugget theorem can be applied to this problem as well.
      The McNugget Theorem
      6 = 2 * 3, and 8 = 2 * 4.
      3 and 4 are relatively prime, so the greatest number which cannot be formed by them is 3*4 — 3 — 4 = 5 (10, because of *2; 10 exists as the third term here, so it too is covered).
      Because we only need to consider even numbers (odd numbers can be converted to even), and we are working with *2 here, all the even terms above 6 will be covered.
      Numbers below and equal to 6 can be processed as a special case.

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

Solved 4 but still feeling worthless because of A and B xD

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

I spent 40 minutes on A and didn't have enough time to solve E ：(

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

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

    I lost B to precision today.. just changing double to integer made it pass. Significant digits turned out to be so significant today :( The pain though!

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

B ruined my entire contest. Couldn't even read E though it was pretty doable. :((

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

124312667 this is my submission for problem B during the contest where i took the values float instead of long long and it gave WA. It gave a difference of 2 in one of the TC. 124345470 this is that same approach(everything same just changed float to long long) but got accepted....can any one pls explain why this happened. edit: by mistake initially i gave the link to wrong problem.

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

    precision error

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

      and why will float be less precise than int/long long

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

        Sometimes with floats, it will do things like $$$1.0000001 = 1$$$. This is why, when comparing floating point numbers, I like to do something like this:

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

          yes you are absolutely correct but my point is that if i am just having floats of type f.000000 and there is no multiplication just subtraction and addition then why would it give some difference.

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

            it shouldn't

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

              actualy 3 != 2^k

              so even with addition you should get precision error

              edit: Am I right here?

              Like 3.000000 != 3 right?

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

          or just multiply 10000000 and compare normally

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

        google "precision error"

        it's not something someone can easily explain to you here

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

Can we do C using dfs ? I think it is the same as Cherry pickup II of leetcode ? please help.

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

But its a question afterall with a valid difficulty range for qstn. B. Also,its my fault that i assumed it to be something else. It actually didn't have much case work. Apologies..

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

Was thinking I'll regain Expert! But problem B exists lol, ate up huge amount of time :(

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

    Problem D is wonderful.

    Considering that a three-letter palindrome can only be

    abcabcabc... acbacbacb... bacbacbac... bcabcabca... cabcabcab... cbacbacba...

    Each position is symmetrical in rotation. So a simple prefix sum can be done for it. Code : https://codeforces.me/contest/1555/submission/124347304

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

      Of course it is! I came up with exact logic to compare with 3! strings and make prefix array (precompute) and answer queries in O(1) time. But sadly , time ran out and I couldn't implement it fully.

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

A clean(ish) solution for B.

Spoiler

We need to check for the number of free cells possible in both X and Y directions. (Free cells are the cells not occupied by the first table). If the number of free cells in ANY direction (X or Y) is greater than the number of cells needed for second table, then we can fit the second table in. The first table only needs to move horizontally or vertically to acommodate the second table, it will never have to move diagonally.

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

Is the rating predictor broken?

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

In reference to problem B 3 actions can be taken: 1. Rename the website to caseforces 2. Ban the guy who set it up from setting up future contests 3. The guy should have some self respect and delete his account

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

    What do you mean? There were only 3 cases: -1, horizontal fit, and vertical fit.

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

Should we be sad or happy in this case? :(

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

One of the best contests I have participated at in my life. Beautiful, Balanced and the Best

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

Actually problem B should be C and C should be B!

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

hard contest only the first problem was easy

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

    Everything is relative.. I thought A was hard, B and C were easy

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

4 Div2 (with 2 Div1) Round, 2 Div3 Round, 2 Educational Round, 2 Div(1+2) Round, and 1 Global Round, Total of 11 Rounds held in this Month. So we can say July is the perfect month for all the contestants who like and enjoy every round of Codeforces. Thanks to Mike Mirzayanov and all the problem setters of this month <3

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

wonder how many guys copy-pasted their segment_tree for E from the Internet

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

    From which part of the Internet? Do you mean that general purpose segment tree libraries are available? Or a complete solution for exactly this problem is available?

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

    Can you please explain the approach of problem E? Where do we need segment tree?

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

      You can use two pointers with segment trees to maintain the minimum value

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

A solution video for the first four questions of div 2

https://www.youtube.com/watch?v=NMSQ-uu59mQ

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

why to even use double in problem B as shown in sample output.

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

    it's a trick to fool people, and also it accepts solutions that somehow use doubles

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

    That was just to confuse us so that we start thinking the box both horizontally and vertically as shown in the example diagram.

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

    I wasted 5 minutes thinking that when can the answer be in double.

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

I misread problem D and thought that input string can contain any 26 letters of Latin alphabet and it is allowed to change any character of the string to one of the first 3 letters and couldn't solve that problem. Can this problem be solved?

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

    I think that it is possible if you spend $$$O(r - l)$$$ on each query or do precalc and spend $$$O(n^2)$$$

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

→ Reply
»
3 years ago, # |
← Rev. 5   Vote: I like it +5 Vote: I do not like it
The solution to Problem A with Proof:
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    For the claim, you can give a one line proof by induction. It's true for $$$6 \leq N \leq 10$$$ and assuming it is true for all even numbers less than $$$N$$$ with $$$N - 6 \geq 6$$$ we can write $$$N$$$ as $$$N - 6 + 6$$$ and we're done by induction.

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

Nice round with not easy nor really hard tasks E is especially good!

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

Is anybody know which testcase is in task b test 2 case 554? My solve fails on it and idk why... Here is link on it https://codeforces.me/contest/1555/submission/124358523 [](https://codeforces.me/contest/1555/submission/124358523) plz say what is wrong...

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

Where's the editorial?

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

Questions about Karry5307_AK_NOI2024 again:

  1. How could he solve B in 29 seconds at 00:09:43 after he solved C at 00:09:19?
  2. How could he solve F in only 3 minutes after he solved E at 00:51? You see, SSRS_ solved it in 21 minutes, tourist solved it in 42 minutes, and WZYYN solved it in 25 minutes. These three are all LGM but they solved F in at least 20 minutes. How could this guy solved it for only 3 minutes?

I think there must be something strange.

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

    I think it is possible that he submitted B and C at the same time because of the bad Internet connection. But a more likely guess is that some people shared this account and solved these problems together.

    I am sure that this account's owner is not real Karry5307 because in China nearly nobody will register an ID of "I all killed a contest".

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

    Although he(they) might cheat,he(they) can't beat me because I am much stronger than h0up1ngze!

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

      You are much stronger than tourist :)

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

      You are much stronger than tourist :)DXqwq

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

      Yes,she is too naive.

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

      You are much strong than tourist :-)

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

      Yeah, you solved F in less time than tourist, then you'll soon become a LIGM(Legendary International Grandmaster) soon :)

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

      You are much stronger than tourist :)

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

    If you check his submissions you can notice that after he submitted D, he coded F for 31 minute, but then got WA, after one more submission for F, he coded E in something like 2-3 minutes (the only code he actually wrote is in main, so I believe 3 minutes were enough), and after that he returned to F. In total he spent ~34 minutes for the last problem, which is quite legit.

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

      Oh, I finally got it. Sorry for my misunderstanding :(

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

    he/she is LGM now.

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

Can we do C using dfs ? I think it is the same as Cherry pickup II of leetcode ? please help.

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

Can anyone help me with problem B solution?? What I am doing wrong here? It is failing 2nd test. Here is the verdict: wrong answer 530th numbers differ - expected: '0.0000000', found: '1.0000000', error = '1.0000000'

here is code:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{

    int tc;
    cin >> tc;
    while (tc--)
    {
        ll W, H, x1, y1, x2, y2, w, h;
        cin >> W >> H;
        cin >> x1 >> y1 >> x2 >> y2;
        cin >> w >> h;
        ll ans = 0;

        if ((h + (y2 - y1)) > H && (w + (x2 - x1)) > W)
            cout << -1 << "\n";
        else if ((w + (x2 - x1)) > W)
        {
            //work vertically
            //cout<<"h="<<h<<" (H-y2)="<<H-y2<<" (H-y1)="<<H-y1<<" ";
            if ((H - y2) < h && y1 < h)
            {
                ans = h - y1;
                ans = min(ans, y2 - (H - h));
            }
            cout << ans << "\n";
        }
        else
        {
            //work horizonatally
            if (x1 < w && (W - w) < x2)
            {
                ans = w - x1;
                ans = min(ans, x2 - (W - w));
            }
            cout << ans << "\n";
        }
    }
}
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    please help me what I am doing wrong here

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

      i think the problem is that you are not considering the case where u can fit it both vertically and horizontally.

      so i would suggest to look in both direction. Like here after going in elseif. it is not going to go in else to check if u can get a smaller ans

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

Have the solutions been rejudged yet? When will the ratings change?

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

Interesting Round, thanks!

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

Can we just appreciate that there is no pretest for D where m < n, so I got RTE. Nice.

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

what's the binary search solution for E? I am more interested in how to write the predicate function in o(logn) or so ?

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

MikeMirzayanov My submissions of this round skipped getting an unexpected warning that my submission to the problem C 124303153 coincides with the submission 124301236 by NZB. This is totally unexpected. The solution to problem C is super simple. I request you to manually check the submissions and the solution to problem C. I'm totally disappointed with this kind of wrong warnings from such a reputed platform like codeforces. Because this is the second time I have been convicted without doing any kind of violations. I wrote a detailed blog on this after getting my first warning but nothing changed. Please read the blog Unexpected warnings from CodeForces. Hope you will look into the matter. Thanks.

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

    MikeMirzayanov same thing happened with me for Question C. The problem was a very simple one.Please look into this

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

    The idea and code of problem C are really quite simple. So, the chances of having similarities in codes are high. Even, my submission's main function has a lot of similarities with you: 124324875. It's quite unfortunate and saddening to see such false-positive cases. I hope, MikeMirzayanov will look into this matter and sort out this thing.

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

    MikeMirzayanov This same thing happened to me too... I received an unexpected message from System saying that my submission was similar to some 10+ other submissions for this problem? This was purely coincidental at least on my end, since the problem's solution was so short.

    Here is mine: 124296686.

    Also my submission ID was earlier than every other submission mine was considered similar to, so there's no way I could've copied/cheated from any of these people.

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

Someone, please explain the first test case of question 5

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

Did anyone who solved F use lca,dsu & merge small into large?

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

When I tried solving problem B using long double for output, I was getting WA on Test 3. But when I used long long instead of long double in the same solution, it got accepted. Why? Can someone please explain?

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

    I think it's because of your output format. You used cout for printing double value. But you didn't set any precision or width. A good way to print double/floating value using cout is: cout<<fixed<<setprecision(10)<<res<<endl;. Your failed solution was printing in this format: 6.55587e+006. Which might have led to the precision error.

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

One constructive feedback : It would be really nice if educational rounds had atleast one problem with a high upsolve value for Div2 contestants, i.e. problem that is slightly out of reach for majority of Blue/Purple contestants.

In this contest, E is a very standard lazy segtree problem and F is (seems ?) too hard.

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

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

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

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

→ Reply