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

Hello Codeforces!

On Jul/12/2020 17:45 (Moscow time) Educational Codeforces Round 91 (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 Roman Roms Glazov, 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: The contest is delayed by 10 minutes.

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 Geothermal 7 341
2 natsugiri 7 362
3 LayCurse 7 387
4 GyojunYoun 7 415
5 tribute_to_Ukraine_2022 7 430

Congratulations to the best hackers:

Rank Competitor Hack Count
1 celestialcoder 15:-2
2 dapingguo8 9
3 kamer 6:-2
4 WiwiHo 3:-1
5 FelixArg 4:-3
48 successful hacks and 88 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A bekzhan29 0:01
B LUV 0:08
C atU 0:09
D duyenn_khong_ngu 0:32
E dorijanlendvaj 0:45
F bekzhan29 0:36
G Geothermal 0:59

UPD: Editorial is out

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

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

Please, arrange a testing round before this round. If not, this contest will also have possibility to become a unrated contest. Please...

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

I wonder how many people are about to wait the LONG queue or to register for tomorrow's contest?

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

    Maybe Mike will postpone the contest if the problem is not solved.

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

to MikeMirzayanov I think we need to make one unrated round and then run the rated round. Because it might turn out unrated like round #655. it is unfortunate that round #655 has become unrated but I believe the next rounds won't turn out unrated and I think many other competitors have the same thought as mine. please announce before tomorrow's contest about this contest will be rated/unrated. thanks for reading

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

"Hope the contest will not waste efforts of coordinators. Although codeforces is the best platform but sometimes gives problem 'queue'. Thanks for such a wonderful platform mike.

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

There should be Testing round tomorrow instead of Educational round.

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

    definitely should have... every time we have to cancel a round we should have a testing round to make sure everything's ok

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

      But fewer people will participate in testing round. Because it will not be rated.

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

It is really sad to know that contest is unrated especially after waiting for a whole week. Let's hope that no such issue occur during educational round.

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

I am just curious to know why in some of the contests, the queue is so long even the participant is nearly equal or less than other contests. The load on the server should be the same! (by the way, it really hearts when you are giving the contest skipping dinner and then contest will be unrated).But I can understand It happens sometimes, we can't do much!

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

    They must have done some upgrading work which turned out to be buggy.

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

    Mike said in announcement, "Sorry, because of the long queue the round is unrated. Probably, the reason is the simultaneous combination of several facts: a lot of participants, 5 pretests in task B, a slight degradation in performance after some recent changes. In any case, I will do an investigation". I think it's more because of the changes they did, as there were too many participants in some other contests too, but there wasn't any long queue at that time.

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

A,B,C solvers never get to use algo knowledge anymore, just a bunch of constructive/pattern/observation C problems everytime. somebody save us.

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

    The aim is to strengthen your logical and constructive thinking before moving on to advanced Algorithms, that way it would be easier to visualize how algorithms work and build strong concepts in those. Anyway, that's just my opinion and you may be right on your part too.

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

      I get your point. I'm just tired of facing the same things. Given a permutation.... maybe I should focus on getting gud so I'd be able to solve interesting problems.

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

        If a problem starts with "Given a permutation", I become very excited and happy :P

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

          Exactly..i also love permutation problems

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

    Lots of problems which have famous algorithms now, were nothing but constructive, pattern, math, and lots of observations based problems 50 years ago

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

Make problem A,B,C somewhat harder otherwise there will be same QueueForces tomorrow.

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

Hope it goes well.

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

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

Was sad because today's contest got unrated, but Wohoo! we have one more contest tomorrow!

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

It looks sad to me that problem setters have to go through problems like what happened in previous round (**Submission pending in queue to be judged**). I am sure that setters want to have people competing in contest the way they usually do. But bcz of queue issue their contest is just destroyed.

It definitely takes a lot to write a contest. I really do hope that none of setters contest go through it.

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

i dont know whether this is correct time to say but despite of long queue problem there is another issue of difference of rating of 3rd and 4th question in recent contests was too large...

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

    That was because many left the contest after Mike's announcement. If queue wouldn't have been in picture then I guess the rating of 4th would be near to 1700

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

Is it possible to tackle queueforces we can judge submissions of unofficial contestant strictly after submissions of official contestant. So it's priority_queue where official contestant are prioritised

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

It would be great if all the educational round problems were Algorithm based, take no offense, just my personal opinion. :)

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

Queueforces xD

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

Let me tell you a trick to reduce the load. Just midway through the contest make an announcement that the contest is unrated. Then when the contest has ended make it rated. Profit

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

    And like this you will become red and others won't ! :P

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

I think this time mike will definitely win <3

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

I don't understand why people feel this upset about the situation of the long queue. Like what makes people feel that they are entitled to a perfect round when the system is running for the community. You are able to give rounds and practice nice problems without paying a cent. Isn't that enough?

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

    Exactly! and the problems which are there in the contest are all new and original with a very basic and tricky idea behind it for atleast A's, B's and C's and even if some round is unrated (which is rare) and people think that their rating would have been increased a lot, they can do it in future contests as well, as they were able to do it now.

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

    Lezendary_sandwich I completely agree with you. After all this is the best platform someone can get which can handle 20k users at a time. But times like yesterday come very often here. So people should keep patience. Hope today's round will be a good one.

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

    Honestly, it'd be pretty cool if we could pay like an annual subscription to CF that gives access to a judge with a smaller queue. Obviously it doesn't work out, since you get a competitive advantage, but still cool.

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

      sounds like leetcode

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

        Does it work well/badly there? I've never competed on leetcode, but it seems like the competition aspect on leetcode not as prominent as CF's is.

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

      I think that could be nice for when upsolving problems or doing virtuals, but I don't usually have problems with the queue at those times. Otherwise yea the pay2win aspect would be pretty lame.

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

    I feel really bad for problem setters and problem testers!! :(

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

Another contest, another opportunity to my son to win!

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

Make Codeforces Great Again

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

Hoping for no long queues in this contest and I feel unlike the last Div2 ,this contest's B and C will be comparatively on tougher side.

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

When everybody is talking about queue but no one is talking about stack

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

Why educational rounds have comparatively very less upvotes than a normal div2 or div1+div2 round.

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

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

Delayed :(

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

Codeforces needed to run an unrated round before starting educational round

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

Delayforces into action again! Fucking irritating it is :)

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

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

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

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

Seems like codeforces is in trouble.

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

I can already see where its going.

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

Each time a contest is delayed by 10 minutes, adrenaline of thousands of participants goes straight to the flush. edit: GG codeforces lol.

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

anyone else facing bad gateway?

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

502 Bad Gateway is coming

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

why am I getting "502 Bad Gateway" error before the contest

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

Please delay the contest. Make the server prepared. Don't screw author's efforts

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

    why didn't they delay it if it's clear there's a problem now the round is probably not rated again

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

Switch to m1.codeforces.com

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

500 Internal Server Error...

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

quite sad to see it happening again , the problemsetters' hardwork is kinda gone to waste again.

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

    yes , another problemset wasted

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

    If all problem statements (except A) were locked/hidden at the start of the contest, then the problemsetters' work wouldn't necessarily have to go to waste. Even if some technical difficulties were to arise during the round, some problems could still be used in the future, since no contestant would've seen them. We could make it so, that each successive problem becomes visible/unlocked, once at least one of the participants has solved the preceding one.

    What do you think of my stupid proposal?

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

      I was able to see first three problems on m2.codeforces . So ,there are definitely more people who did. Btw ,It will be better ,if they publish editorials now .

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

        I wasn't talking about what happened in this specific contest, but rather suggesting a way to change the rules, so that problems only gradually become "unlocked". I was able to see A, B, and C, on m3.codeforces.com too, but there is no way to guarantee, that there wasn't some lucky person who could read all problem statements. Therefore, if a situation like this were to repeat itself in the future, there would be no way of knowing, which problems could still be used in future rounds, unless my proposal was implemented.

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

Is it still rated?

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

What's going on?

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

Codeforces!

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

My son is crying...

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

Did they not realise that everyone was facing bad gateway ?

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

Classic Codeforces

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

UnratedForces!

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

I think contest could have delayed bit more or held tomorrow after fixed bug. All the efforts of setter go in vain.

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

    yes,they should have seen this coming and postponed the round,would have saved everybody's time and effort

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

"Unfortunately, the round is unrated."

Ah shit! Here we go again!

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

That's why we need daily contests XD

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

Unrated, right?

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

Unfortunately, the round is unrated.

*Fortunately

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

UNRATED

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

...

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

It's almost like people predicted the round would have been unrated if not postponed. There was no way these issues could have been fixed overnight...

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

It makes sense to ask "Is is rated?" before contests..

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

WTF, back to back to unrated contest!

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

I feel bad for awoo and his efforts :(

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

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

I think this is done by rival competitive coding sites like leetcode, atcoder, codechef, they are attacking website.... just opinion.

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

This even worse than yesterday's round

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

    I disagree with you :-)

    Atleast we were able to submit today and get the instant result.

    what happened yesterday was worst because u just submitted the code and you dont know weather it is AC or not even after waiting more than 10 min!!

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

Is it the first time there were two back to back unrated contests? If so, we need to reconsider the direction we are heading to.

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

A. Yet another wasted problemset

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

    Not for you, just go and submit now :-)

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

      Of course I will do that but solving problems during rated contest gives more fun and it's a chance to change rating

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

Before July 2020: This contest is unusual to have an unusual starting time.

July 2020: This contest is unusual to be rated.

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

Unrated again!! :(

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

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

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

No excuse this time, MikeMirzayanov. You knew since yesterday this could've happened and you chose to do nothing about it.

UPD: I did a poor choice of words with this comment, I know it's not true that Mike did nothing about the issues on the platform. I do believe there were a lot of alternatives which could've prevented the round from being ruined, and none of them was taken. I stand by that. But I didn't want to offend Mike, or diminish the efforts he constantly does for the community.

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

    What makes you think he wasn't trying to fix this the whole time? Never assume, and be grateful of their hard work.

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

      Facts:

      • The platform failed yesterday.
      • This round could've been postponed.
      • A testing round could've been held to avoid this.
      • Setters and testers' weeks of hard work were ruined.
      • Something very similar happened in Round 639. One would expect the CF team learned something about it, but here it is again.

      I've always been grateful to CF, I've even donated so they could keep up and improve, which apparently you haven't done. And I didn't say Mike didn't try to fix this. But he couldn't fix it, and I think there's no excuse this time, considering all the options he had.

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

        I didn't say Mike didn't try to fix this

        You literally said "you chose to do nothing about it".

        All your "facts" only make sense with the assumption that yesterday's issue reoccurred and precisely that issue was the cause for today's outage. You also have to assume that it was the same issue as in round 639, then, for some reason it went away, and then reappeared yesterday.

        How does this even make any sense? Have you really thought this through before commenting?

        What makes you think it was the same issue? You realize that there are multiple things that can go wrong on the website, right? It doesn't even make sense as the first guess:

        • the failures were different — yesterday there were queues, today the website didn't load itself
        • you've been on this website since at least 2017 — do you really not have any trust in CF's team that they did their best to prevent yesterday's the issue? After 2+ years on the platform, the first thing that comes to your mind is "chose to do nothing about it"? Really? Is this consistent with your experience so far?
        → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 3   Vote: I like it +8 Vote: I do not like it

        Facts:

        • Long queue and inability to enter the site are different problems.
        → Reply
»
4 years ago, # |
  Vote: I like it +18 Vote: I do not like it

we can somehow make the entire codeforce infrastructure as open source and ask more participant to contribute, optimize, improve its overall quality and performance.

While enjoying the high quality contest, it is also important to maintain the infrastructure itself together.

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

DeadForces :-)

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

All we need is Hope

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

Ahh, test 7 killed me.

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

Any hint regarding test 7 in D ?

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

    Same, can't find anything wrong for 1 hour.

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

    It is sometimes optimal for you to take one Fireball, and all others Berserk

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

      I took care of that, can you give any test-case ?

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

        No I don't have any test case but I have 3 cases which needed you need to solve:

        If left or right element from subarray is greater than maximum in subarray:

        1. Take all Berserk

        If length of subbaray is greater or equal than k:

        1. Take as much Fireball as you can

        2. Take one Fireball, and all others Berserk

        Take minimum of those 3, if those 3 cannot be achieved, than it's -1

        Code: https://www.ideone.com/B1cMcc

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

          Silliset mistake I have made, didn't took care of the garbage values.

          → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it 
    13 3
4 3 1
2 9 3 5 8 10 7 4 1 6 10 11 12
2 6 12

    Maybe check this TC, ans = 11, to my knowledge

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

What's the test 7 for D

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

The problems were good!!!

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

How to solve D?

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

    In order to reduce array A to B, B first needs do be a subsequence of A. Then, when this condition is checked there is always a solution, and here is how to achieve it with minimal cost. For every consecutive B[i] and B[i+1], we need to delete elements from A in the range [pos[i]+1 , pos[i+1]-1] where pos[i] represents the position of element B[i] in the array A.

    It is clear that if pos[i]+1 = pos[i+1] then the cost for this part is 0 otherwise let m be max value of array A over the range [pos[i]+1 , pos[i+1]-1] and nb = pos[i+1]-pos[i]-1 (number of elements in the range).

    If nb<k which clearly means we can't use Fireball operation, we have only two options:

    - use nb Bersek and spend y*nb only if m<max(B[i],B[i+1]) 
- otherwise there is no solution and output -1

    else there are two cases:

    1. if it is more optimal to use one Fireball than to use k Bersek operations: clearly we need to reduce nb elements to the biggest multiple of k using Berseks and destroy the rest using Fireballs

2. otherwise we have two more cases:
    - if m>max(B[i],B[i+1]) then we can not use only Bersek we need to use one Fireball at the end so the cost will be (nb-k)*y+x
    - else we can use only Bersek and the cost is nb*y

    In order to deal with elements before pos[1] and after pos[m], I've added 0 at the beginning and the end of both array A and B. Here is my submission 86697447.

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

      For the case nb>=k 

      clearly we need to reduce nb elements to the biggest multiple of k and destroy the rest using Fireballs

      Can you please explain it in detail , I couldnt thought of how to optimally pick elements as there could be lot of ways. Thanks

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

        yeah, ofc. Well we know that it is more optimal to use one Fireball then to use k Bersek which means k*y < x holds. However, we can't only use Fireballs because nb is not guaranteed to be a multiple of k and we will have some elements left in the end. So instead of directly using Fireballs we will reduce nb to biggest multiple of k smaller than nb using Berseks and then we will employ Fireballs. More formally, the cost will be $$$(nb\mod k)*y + \lfloor{\frac{nb}{k}}\rfloor*x$$$.

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

      Isn't it possible that when you reduce nb to the biggest multiple of k, that you could not use Bersek to destroy the remaining warriors? Namely, you end up with m greater than B[i] and B[i + 1]

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

        when reducing nb to the biggest multiple of k we are only using Berseks to achieve that. Keep in mind that we can always do it by picking an element in the range which has a smaller element adjacent to it. Then, we will use $$$\lfloor{\frac{nb}{k}}\rfloor$$$ fireballs to destroy the remaining warriors.

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

Problems were really good, infact the difficulty of question B was greater than C until u get the trick. Also D was little tricky if u don't consider all the cases carefully. Lets hope we see a rated round soon.

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

    Pls explain your idea of D.

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

      First check if B is a subsequence of A, if not then we can't produce an answer.

      For converting A to B we need(provided B is a subsequence of A) to delete some of the segments/fragments in A which are not there in B, for that you can see the my below comments:

      -> https://codeforces.com/blog/entry/79986?#comment-660940

      ->https://codeforces.com/blog/entry/79986?#comment-660968

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

        Didn't read your explanation(I want to first try on my own) but I got stuck on the test case:

        what if array_a = [1,3,4,2], array_b = [1,2], k = 3? I'm stuck there. We can't delete [3,4](since k is 3) and if we delete 3 using 4 then it becomes [1,4,2]. Am I missing something?

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

          For the above test case we won't be able to convert A to B because:

          -> size of segment to delete < k so we can't use x mana i.e first type of operation.

          -> We can use second operation for completely deleting the fragment only when either of adjacent element > maximum element in fragment, but in ur case max(3,4) > 1 and 2 so we can't completely delete all the elements in the fragment using second operation.

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

How to solve E?

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

    There must be some way to implement the simulation efficient. Note that the ans foreach move is the number of segments of consecutive rings.

    Then, whenever two towers get merged, some of the consecutive segments get merged to one segment, ans is decreased by one for each such merge.

    But my solution TLEed.

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

      We can do this by keeping track of the current number of differences between consecutive elements. Every time we merge, some differences will get eliminated. We just need to keep track of how many get eliminated per merge. To do this, keep track for each tower, at what indexes it occurs in the array. For instance in the sample, the array is

      1 2 3 3 1 4 3.

      Then the sets would be:

      Tower 1: 0, 4
Tower 2: 1
Tower 3: 2, 3, 6
Tower 4: 5

      Now when you merge two towers, this is equivalent to merging the two sets corresponding to those indices. This can be done in O(log n) amortized by using the small to large merging method. For example, after we merge towers 1 and 3, the sets will become:

      Tower 1:
Tower 2: 1
Tower 3: 0, 2, 3, 4, 6
Tower 4: 5

      You also need to know how many changes between consecutive elements in the original array are eliminated. This can be computed by iterating through the smaller set, and adding 1 for each element in the larger set that is 1 away from this element in the smaller set. In this case the 4 from Tower 1 and the 3 from Tower 3 are the only ones next to each other. This means we must subtract 1 from the current count of differences.

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

        In my first submit I tried to use vectors, and made a new vector out of a and b every time. Then I tried to use sets, but it seems I did buildin some bugs, all TLE.

        However, of the solutions I studied so far I like most the one from icecuber, 86686544 which does what you explain above in nice code.

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

My video editorial for B . I have tried to explain my thought process and why the algorithm worked hope you like it .

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

What is wrong with this approach for D?

I first checked if B was a subsequence of A. After this, I fragmented A into parts (each fragment was between two such positions, such that the corresponding numbers were the same for A and B, that is to say, where A and B matched. After this, I greedily calculated mana required for each fragment.

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

    To greedily calculate mana required there will be two case:

    -> If the maximum element there in the fragment to be deleted is larger than the adjacent elements to that fragment then we must use x mana to delete the k elements in the fragment containing that maximum element also, for the remaining element in the fragment you can than greedily compute the cost. Note: In this case if size of fragment < k then there won't be any possible answer.

    -> If the maximum element there in the fragment is smaller than either of the adjacent element then you can greedily compute the cost to delete all the elements in fragment(there won't be restriction like we had above)

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

I don't understand why my solution for D gives TLE on test 6.

86694208

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

    Never mind, I got AC. It was a stupid variable placement.

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

Thanks for the contest anyway, I liked the problems.

Now, what about the tutorial? I see no reason to hold it back any longer.

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

The problemset was really good! kuddos to the problemsetters !!

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

How to solve Problem E?

I even don't understand the sample: [[5,1],[2],[7,4,3],[6]] ---> [[2],[7,5,4,3,1],[6]]

[[5,1],[2],[7,4,3],[6]] ---> [[5],[2],[7,4,3,1],[6]] ---> [[5,4,3,1],[2],[7],[6]] ---> [[],[2],[7,5,4,3,1],[6]] 3 steps is ok! why the answer is 5 ?

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

    Whenever two consecutive rings lay onto each other they never get separated again. And in the end, it must be one consecutive segment.

    So ans is always the number of consecutive segments of rings, minus one.

    When towers get merged, some of those segments get merged, too, ans decreases by that number of merges.

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

It was hard for me to understand that you can reorder the chests in G.

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

the problems were very nice specially E.In E we can use dsu.But sad that contest is unrated

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

My video editorial for problem C . I have tried to explain my thought process and the algorithm . Hope you like it .

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

I have doubt of max and min function. Here is my code for A 86697535. I used one while loop with max function and it gives TLE. As I understand testcases loop is 10**2 while loop is of 10**3 and max function takes 10**3. And 10**8 is valid for 1sec, then why I got TLE. please help, Thank you

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

    You see that such a triple is available at every local maxima, it is in your code.

             c = g[i-1]
         d = g[i]
         e = g[i+1]

    So just iterate the array once checking every position it if is such a triple. If yes print it and break/return.

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

      Hey spooky, I read your submission after getting WA on D still could not figure out where I am making a mistake. 1. I check if v2 is a subsequence of v1, if not then answer is not possible. 2. I am destroying all segments between the elements. If there is a segment where we have an element which is greater than the starting and ending point of that segment, at least once we should use Power X, else we can use cheaper of Power X or Y. If we are unable to use Power X (segment length is less than K) then answer is not possible. 3. I am destroying all segments from starting to first element in v2, and from ending to last element in v2. Here is a link to my submission: https://codeforces.com/contest/1380/submission/86702514 Any help is much appreciated as always!

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

        Again, as soon as I made this comment I found out my mistake like the last time. Anyway, your solutions are very helpful! Thank you.

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

        Note that p1 is out of bound here, but that seems not to be the reason for WA.

        		while(p1<v1.size()&&v1[p1]!=v2[p2]){
			p1++;
		}
		if(v1[p1]!=v2[p2]) return false;

        The other code is... well, complecated. Try to simplify. There are so much if and things, one cannot debug this.

        Edit: Wrote this parallel to your comment, nevermind.

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

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

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

On problem G, for the second sample case, can someone explain what configuration of mimic chests gives 7/8 as the expected value for having 6 mimics? I must be misunderstanding some part of the problem but I've read this several times now and I can't see how you can achieve a better EV than 8/8 for 6 chests (by making the chest 3 and either chest 5 or 8 real, and the rest mimic, giving us 1/8*(3+5)). I have a feeling that I could be misunderstanding, and perhaps the optimal strategy is to make chests 2 and 3 real, but from what I understand, this would give an EV of 1/8*((4+3)+3)=10/8.

I don't want to read the editorial or other people's code since I actually want to try solving the problem, but I've been bashing my head about this for quite a while.

EDIT: Oh, I now understand cookiedoth's comment above about reordering the chests. The order that they are given in the problem is NOT the order they have to appear in the circle. That's pretty confusing. I think what makes it particularly confusing is that you refer to rooms using i and then in the next sentence still refer to the chests using i, almost implying that they correspond to the same thing.

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

    You can reorder chests. I also was having problems with understanding the sample tests. But after 20 minutes I finally understood it.

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

I am not being able to optimize my O(n^2) idea in E. Help?
My idea. For each query, the answer is the number of change of towers from 1 to n. In every query, we can just merge the two sets by iterating the set elements and find out answer by looking through the array.

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

Is D based on magic the gathering?

If so what inspired what berserk and fireball do as in the problem statement (they both do something quite different in mtg)?

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

    No, initially there were Lightning Bolt (killing exactly one target) and Berserk (I don't know why Roms chose those spells, probably based on HoMM III). But that problem was considered to be too easy, so we changed the Lightning Bolt to kill several targets at the same moment and chose a random AoE spell to name it

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

      Oh, that's cool.

      I have an idea for a problem now that also uses a fireball and berserk spell, but that do something different xD

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

I am unable to find mistake in my code of div 2 problem D ( code )

→ Reply