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

Hello Codeforces!

On Jan/16/2022 17:35 (Moscow time) Educational Codeforces Round 121 (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!

UPD: Unfortunately, the round is unrated. We are sorry for the inconvenience. You can upsolve the problems using the Codeforces archive.

UPD: Editorial is out.

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

Comments Comments (215)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it +24 Vote: I do not like it

First educational round of 2022!

Wish everyone positive delta

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

Wish all people who are going to participate in this round good luck!

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

I hope this will be the best education round in 2022. Wish everyone positive delta

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

We always wait for the Educational Round.

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

When I go to register for the contest, it doesn't say that I'm "out of the competition" like it usually does. Is this an error?

UPD: Apparently this is just how edu rounds are, I guess.

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

The number of problems invented by these guys is more than the number of problems i solved so far. Just wanna say thank you, you guys are genius.

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

Is rating below 2100 belongs to division 2? If so what is rating range for division 3?

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

Hope To Be Pupil This Round

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

Why Codeforces is lagging when i switch to Wifi ??? Is happening with everyone ???

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

first time participating in 2022,and in first educational round of 2022.

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

[deleted]

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

yes, a new contest, can't wait to lose rating again!!!

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

Why haven't they listed the rating of problems ?

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

Hope to become pupil.

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

Does anyone else think Problem C statement is unnecessarily complicated?

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

    yes i do think , especially for newbies and pupils like us

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

      And for me too, after solving problem C for 30 mins I realised that I understood the question wrong lol

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

Is it unrated?

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

Unrated?

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

unrated? (due to the breakdown of the website?)

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

Is it unrated? I hope it is as the site was down for a while.

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

I want my Delta back >:(

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

Is it rated?????

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

I couldn't submit my solution for C in the last 40 minutes, and I believe others are experiencing a similar situation. Please, unrate this round.

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

    Yeah same situation. Make the round unrated, even temporary sites were not working.

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

    same thing happened to me

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

    I waited about 45 minutes to submit my E, and the site didn't reopen until after the contest ended. Does anyone know how long the site has been down?

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

    yeah last 45 minutes site wasn't working

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

    Can't agree more! Can't submit C (It could just drastically improve my RANK)

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

    yeah, I couldn't submit D...

    I haven't solved D so fast in a long time...

    It makes me bad

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

I was not able to submit problem C on time as the website was down.

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

I was about to submit problem C and the website is down...

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

What the hell is the power company near Codeforces doing

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

pls dont get rated plssssssssssssssss

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

Just before I wanted to send a full solution to C, site crashed. If it is rated I am gonna be very very sad.

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

    Same, got B and C, wanted to submit, boom unavailable. 45 min later, website up again

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

Make it unrated or bring new contest. This is bujdili.

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

I submitted problem C with two minutes left, but CodeForces was down. I was not able to submit. Did this happen to others?

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

Any ideas to solve E ???

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

    Brute force

    let 2 ^ a, 2 ^ b, 2 ^ c be the partitions

    just check whether this partition is possible or not

    then the answer:

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

    The solution I wrote and could not submit due to website being down does the following:

    • First dfs from any root and determine for each subtree the number of black nodes in that subtree -> now we can determine the number of black nodes of any subtree using any root.

    • Now we BFS starting from all black nodes going outwards. — If current node u has neighbour v such that v number of black nodes of the subtree v when root is u is bigger than the distance of v to any black tree. Then mark u.

    Sorry for bad formatting :/

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

It should be unrated . Half of the time the server was down...

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

Obviously it will be unrated. Keep calm everyone.

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

Where are Codeforces servers hosted?

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

give us 30 more minutes

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

    Better to make it unrated. Otherwise, those who have read/downloaded all the problems will have an advantage. (Also a problem for those who are not available anymore)

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

Due to electrical problems, the site is temporarily unavailable. We expect him to be back in minutes 5-30 minutes.

This is there for last half an hour of the contest for me. Anyone else faced same issue?

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

Will this contest be unrated since the website crashed in the last hour for a lot of people?

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

guys the contest stopped in between:(

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

Is it rated or not?

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

    same bro :(

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

    LMAO this guy comment was:

    before edit

    but when he saw -13 votes he edit it to:

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

      I don't get what is wrong for me to wish if it was rated.

      As I was going to return to candidate master again and achieve new max rating.

      I think it's normal for me to want more than +100 delta and after all it's just a wish it can't change any thing.

      I don't get why I get down voted a lot.

      and to correct something when I edited the comment it was just -2 not -13

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

        I mean you knew that you are doing something wrong when you edited your comment so why u are asking again? Many people couldn't get +ve delta during the uptime and some of them could have reached +ve delta during the downtime so thats why its not fair for many participants, and btw my delta was 108 +ve but its better for it to be unrated :)

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

Unfortunately for the authors, the round didn't go smoothly but I enjoyed the problems. Thank you.

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

I did good. But it should be unrated (: almost 1 hour server probelm :3 Its huge ..

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

Unrated?

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

please let me submit!

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

Downforces

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

Will this round be Unrated?

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

Please make it rated

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

It will be unrated?

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

CF everyday bomb.

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

People are so impatient. I mean, you need to give them some time to announce that it is unrated. Who knows, probably they cannot still access the site : P

edit: there you go

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

Kindly make this round unrated as the server went down for about 50 minutes. I had written the code for C but was unable to submit it due to the server issues. Many others might have faced similar problems.

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

I thought I would become CM then the atrocity happened. My disappointment is immeasurable and my day is ruined.

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

hope it will be unrated

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

i would become blue，almost

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

Didn't know electrical issues could screw up a contest. Well the round was supposed to be educational after all XD

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

Please keep rated...

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

People should stop down-voting the contest. It's not the fault of the authors, co-ordinators or testers that there was an electrical outage.

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

Unavailableforces

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

Probably going be to heavily downvoted but guys it might still be rated. Everyone got the same amount of time to submit their solutions. So effectively only the contest duration got reduced.

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

    And it became unrated just as I commented. Maybe I jinxed it lol.

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

      You said ... "it might still be rated" ...

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

        I wasn't expecting it to be rated but I wouldn't have been surprised if it would have been because effectively only the contest duration was reduced. And I get a feel, I haven't understood your comment.

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

ig a lot of people want this round unrated because who performed good is a small percentage and that's why they got positive delta

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

I had 10 minutes left but suddenly the web crashed. When the problem was fixed, I intended to get back to submit my code but the contest is over:((

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

Half of the people wants it to be rated other half wants it to be unrated. Good Luck awoo

UPD — Round is unrated.

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

    Maybe processing only +ve deltas is a good idea.

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

Does the contest will be unrated now?

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

i cant submit in the archive, why?

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

    Wait for the system test to end

    → Reply
»
3 years ago, # |
  Vote: I like it +12 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 +23 Vote: I do not like it

finally NON-NEGATIVE delta in Educational Round.

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

In my opinion, it should be rated. The server failure has affected equally everybody, and the site has run enough time to be able to submit several problems. It would be a shame to have lost all the time spent. But it is up to Mike of course...

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

    I quite agree, surely because I did well, for once.

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

    This is not how it works. Think about those who solved a question but could not submit and those who could not solve it at all. If the round is rated then it would be unfair to those who could solve it. You can't say it's a shorter version of the round coz the duration announced before the start was 2 hours and that's the duration everyone expected but could not get. So it's fair to everyone that the round gets unrated.

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

(*￣3￣)╭

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

From where can I access codeforces archives?

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

First unrated contest of the year ! :|

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

It is officially unrated now.

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

First unrated educational round of 2022! :D

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

Peoples reaction when codeforces is unavailable during the contest reaction

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

Why are people downvoting the blog? The authors can do nothing about codeforces's servers

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

since the contest is stuck at System Testing 100%, it is not completely over and we cant upsolve it in the archive :(

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

Wow! no one's lost any points this round.

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

Can we add another Educational round by end of Jan to make up this one ??

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

Why do unrated rounds always happen when I do well :sob:.

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

Unrated! Thanks UnavailableForces!

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

Anyway, I loved this round!

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

Any idea how I can submit solutions for contest problems ? I get 'Contest is over' popup message :/

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

I don't know whether speaking this will affect my contribution to become negative because some people may disagree. But yeah, whatever.

I just wanna "rant". But if the round will be unrated, I will be very upset because after a while, I feel like my performance is quite great in this round. So it feels like making the round unrated is quite unfair (at least for some people did their best for the first 1+ hour (before the electricity went out))

Yes, if I'm at the bottom, probably I will feel different and frustrated.

But when I try to see this objectivically, making the round rated is a fair thing to do. Why? Because in the end, all participants has a fair condition : 1 hour contest (and the electricity go back up after the contest ends anyway)

Yes there's a way of thinking like : "if you're good, you will keep enjoying problem solving — whether the round is rated or not". Yes I do agree with that, but emotionally speaking, it feels like this hits me hard personally (and probably some people might feel the same)

Yeah so that's my point of view. Feel free if you guys want to disagree and downvote for this, but I stand with my thought. And hopefully in the future, there will be some acceptable solution to mitigate this issue

Good luck Codeforces team

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

    This doesn't really make any sense. People choose to participate in the contest with the expectation that the rules/time constraints don't arbitrarily change during the contest. Do you really think someone who can eventually solve 5 problems should be ranked lower than someone who can only solve the first 3 quickly?

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

      In 2 hours contest, I agree with your opinion. And I think this incident is quite an unfortunate event I believe

      But I also believe that speed is also important for solving the first X problem quick. So in a way, I think given the equal circumstances to all participants (i.e. electricity went out until the end of the contest), should it still be a fair game?

      Unless if in the middle of the contest the server went back up, I think it's another story and when that's the case it's reasonable to make the round unrated

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

        Of course speed is important, that's why it's rewarded on the leaderboard. But in the cp community (in particular these educational rounds), there's a reason why the slowest solver of 4 problems is higher ranked than the fastest person who can only solve 3.

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

        I have to disagree with you — while we all got the same time, changing the duration of the contest can affect people's strategy. Consider the classic example of "I can't wrap my head around problem C, I'll try D and then come back". You'd never do something like this near the end of the contest, but people would consider it when there's plenty of time left. So by suddenly truncating the contest you punish people that are trying harder problems when they really shouldn't be.

        It's bad for a round to become unrated, but I think it's the only fair thing to do in this case

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

    I think that extending the contest time is a better way of dealing with server failures. Making a contest unrated is very frustrating and discouraging for those who have performed well. There is a reason why it's called 'competitive' programming. I don't think people here are truly indifferent whether a contest is rated or not :)

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

      Extending contest time is not always feasible. Many people only participate in a contest coz they were able to get free time in that duration. You gotta take care of all time zones.

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

      Hmm I think it's not a best thing because some people might think the contest is unrated and quit before they realize there's an extension :')

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

    1 hour contest is a fair condition, but only if you know the duration beforehand.

    Suppose you have written a solution for a problem and you're not so sure that it's correct. It might be due to different reasons — this can be an unproven greedy, the code can just be complex and there might be some bugs in it, etc. Should you submit right away?

    If there's a minute until the end of the contest, the correct decision is to go full YOLO, submit (maybe even without checking the samples!) and pray to whomever you worship that both your idea and your implementation of it is correct. But what if you have a considerable amount of time until the end of the contest? Then the better course of action is to wait with submitting the code (because you might get penalty) and test the solution, maybe even let the stress run for several minutes. When you know that you have time, being careful is better than just submitting the code outright.

    So, in a situation like today's one (when you assume that it is only the middle of the contest, but in fact it's only a minute), you get punished for doing the correct thing (if you verify your code once again, hoping to submit in 5-10 minutes, you instead can't submit at all). That's why these conditions are unfair, and that's why we chose to make the round unrated.

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

      I see. I think your argument is reasonable. Let's hope this unfortunate incident is minimized in the future :)

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

It was a terrible contest experience I have had before. Does this kind of problem usually happen during contest HERE?

I don't participate Codeforces contest so frequently, so I'm wondering if it is necessary to consider technical issues on platform.

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

    No, it does not usually happen. Normally the contest experience is smooth except for some minutes at the start of the contest.

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

    happens very rarely

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

    Gotcha. So it seems that it was a rare accident. Unfortunate for authors :(

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

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

Why did they make it unrated?

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

    cause it's not fair for many contestants, maybe not you, but still worth going unrated

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

    The contest only lasted an hour and twenty minutes when it should have lasted two hours. Even if I don't really agree with this decision, it is clear that it completely changes the competition, and that it may seem reasonable to cancel.

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

editorial?

→ Reply
»
3 years ago, # |
  Vote: I like it +19 Vote: I do not like it
Happy Meme :)
Sad Meme :')
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    haha that actually happened with me XD

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

Solved 4 problems but unrated.ಥ_ಥ

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

Are there are some thoughts about how to clever implement 1626D - Турнир боевого искусства?

I had for like one hour a more or less clear idea on how it should work (iterate possible group sizes, binary search possible number of partitipants), but was not able to write the code. I tried using lower_bound() for binary search, but did not get it right somehow. What here is the trick to get it right in time?

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

    I bruteforce the size of the small and medium group and check how many people I need to add to form a group with those sizes

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

    After the formation let the Light , Middle and Heavy Section have 2^i , 2^k and 2^j members respectively . Let's form two arrays pref and suff , pref[z] number of persons with weight<=z and suff[z] number of persons with weight>=z So our answer would be 2^i + 2^j + 2^k — n so if we fix i and j to minimize the answer k should be minimized so we should find maximum x such that pref[x-1]<=2^i , minimum y such that suff[y]<= 2^j. We can brute force over all pairs (i,j) and get the result . 2^k >= (n-pref[x-1]-suff[y]) thus to minimize k , pref[x-1]+suff[y] should be maximized

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

      Well, it is super obvious how error prone that is. And what you discribe by "get the result" is an additional binary search on the prefix array(s).

      The question is, how to make it more clear. Actually I am not able to simply write it down, it is to complecated. I need some kind of abstraction layer or whatever.

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

        I just said what I wrote in my already accepted code . The last statement in my comment is the reason behind why I chose for every i and j max x such that pref[x-1] <= 2^i and minimum y such that suff[y] <= 2^j

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

    Related blog

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

Was problem C easier than usual? Anyway, good problems.

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

for problem D, I have a O((log(A))^2 * log(n) + n) solution, is it wrong? submission

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

problem E was super nice. After a long time, an Edu problem E actually required some thinking. A shame that this was unrated...

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

I uploaded a screencast solving all problems here: https://youtu.be/XBqrXvMy3Is

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

I had a pretty clean solution to 1626E - Черно-белое дерево without any casework, so I'll outline it here.

  1. if you have an edge $$$(u, v)$$$, and there are 2+ black nodes on the side of $$$u$$$, then we say that $$$u$$$ is "easily reachable" from $$$v$$$.
  2. if you can "easily reach" a black node or an immediate neighbor of a black node, then you win.

Hence, we construct the reverse graph of "easily reachable" and multi-source BFS from the black nodes & their neighbors, and we're done!

(The intuition behind "easily reachable" is that we can take a step along this edge regardless of other moves, since we have 2+ black nodes to choose from.)

Full code (including IO/templates) is at 143016277, but the key part is below.

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

    Thank you, this is a brilliant solution, and very well explained!

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

    Hmm what do you mean by "reverse graph of easily reachable" ?

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

      Reverse in the sense that in step 1, we would consider the "easily reachable" edge to go from $$$v$$$ to $$$u$$$, but during the BFS we consider it as $$$u$$$ to $$$v$$$ since we are starting from the black nodes.

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

Can someone explains the dp solution for C. I used ghreedy

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

Any approach for C ?

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

For problem C, does a spell stop once it hits a monster, or does it keep going? Edit: nvm, my question was stupid.

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

Really like the problems in this contest, the problem description is short.

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

Can someone please help me find the error in my code for problem C. I used a greedy approach of traversing the list in reverse order. Here is my submission

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

I am sorry for your loss. This Round is, absolutely, good(at least for me).

Looking forward to your future contests!

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

I figured the idea for the solution of problem F quite quickly after opening it.

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

Problem C what should be the output

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

    45

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it 
      But i think it is possible to get the lower answer
because
we can cast spell

at 2 3 (cost 1+2=3)
and 
at 3 4 5 6 7 8 9 10 ( cost 1+2+3+4+5+6+7+8=36)

total =39<45
please tell me why it is wrong
      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        you are casting 2 spells at 3, which is not allowed. Hence you are forced to cast spells (x + 1) at every second from 2 to 10

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

is there gonna be an editorial?

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

Will the tutorial be available or not?

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

Can anyone tell what is wrong in my solution 143108028 for problem D where a is size of lightweight, b is size of middleweight and c is size of heavyweight

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

    The only wrong part I could think of is in your code for a you're finding the smallest length bigger than 1<<j while you should be finding the biggest length smaller than 1<<j.

    Think of it as such.

    In problem it is given that the final partition would be of form $$$2^i$$$ so it would be more sensible to take the maximum number of elements in that partition from the array. So we can say that we take some $$$2^i-k$$$ from array. So we should minimize k right ?
    But what you did was, you considered that the number of elements from the array in final partition will be of form $$$2^i+k$$$ and you minimized k. See in that case you would have to add $$$2^i-k$$$ elements to the array. Now minimizing k will actually maximize the answer for a particular i.

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

I am not able to find where am I getting wrong in problem C. Anybody pls help. My submission 143125218 https://codeforces.net/contest/1626/submission/143125218

→ Reply
»
3 years ago, # |
  Vote: I like it +9 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 +7 Vote: I do not like it

It's so sad that this round got unrated and i didn't become purple. But i love these carefully-prepared problems :)

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

It's a shame the round didn't go well, yet I'm glad to have participated.

The problems were all creative and unique, I enjoyed every one of them and loved the round.

→ Reply