Автор awoo, история, 4 года назад, По-русски

Привет, Codeforces!

В 12.07.2020 17:45 (Московское время) состоится Educational Codeforces Round 91 (рейтинговый для Див. 2).

Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.

Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

Вам будет предложено 6 или 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.

Задачи вместе со мной придумывали и готовили Роман Roms Глазов, Адилбек adedalic Далабаев, Владимир vovuh Петров, Иван BledDest Андросов и Максим Neon Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.

Удачи в раунде! Успешных решений!

UPD: Контест отложен на 10 минут.

Поздравляем победителей:

Место Участник Задач решено Штраф
1 Geothermal 7 341
2 natsugiri 7 362
3 LayCurse 7 387
4 GyojunYoun 7 415
5 tribute_to_Ukraine_2022 7 430

Поздравляем лучших взломщиков:

Место Участник Число взломов
1 celestialcoder 15:-2
2 dapingguo8 9
3 kamer 6:-2
4 FelixArg 4:-3
5 WiwiHo 3:-1
Было сделано 48 успешных и 88 неудачных взломов.

И, наконец, поздравляем людей, отправивших первое полное решение по задаче:

Задача Участник Штраф
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: Разбор опубликован

  • Проголосовать: нравится
  • +515
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

QueueForces

»
4 года назад, # |
  Проголосовать: нравится +191 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 3   Проголосовать: нравится -7 Проголосовать: не нравится

"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.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

There should be Testing round tomorrow instead of Educational round.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

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!

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
4 года назад, # |
  Проголосовать: нравится +53 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +24 Проголосовать: не нравится

    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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 4   Проголосовать: нравится -25 Проголосовать: не нравится

Hope it goes well.

»
4 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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.

»
4 года назад, # |
  Проголосовать: нравится -25 Проголосовать: не нравится

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...

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится -20 Проголосовать: не нравится

Queueforces xD

»
4 года назад, # |
  Проголосовать: нравится -36 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +61 Проголосовать: не нравится

I think this time mike will definitely win <3

»
4 года назад, # |
  Проголосовать: нравится +95 Проголосовать: не нравится

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?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

    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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится

      sounds like leetcode

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится

Another contest, another opportunity to my son to win!

»
4 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Make Codeforces Great Again

»
4 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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.

»
4 года назад, # |
  Проголосовать: нравится +74 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +36 Проголосовать: не нравится
»
4 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Delayed :(

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Codeforces needed to run an unrated round before starting educational round

»
4 года назад, # |
  Проголосовать: нравится -50 Проголосовать: не нравится

Delayforces into action again! Fucking irritating it is :)

»
4 года назад, # |
  Проголосовать: нравится +67 Проголосовать: не нравится
»
4 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

Seems like codeforces is in trouble.

»
4 года назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

I can already see where its going.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +24 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +38 Проголосовать: не нравится

anyone else facing bad gateway?

»
4 года назад, # |
  Проголосовать: нравится +60 Проголосовать: не нравится

502 Bad Gateway is coming

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +35 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Switch to m1.codeforces.com

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

500 Internal Server Error...

»
4 года назад, # |
  Проголосовать: нравится +46 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    yes , another problemset wasted

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 .

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Is it still rated?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What's going on?

»
4 года назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

Codeforces!

»
4 года назад, # |
  Проголосовать: нравится +49 Проголосовать: не нравится

My son is crying...

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Still rated? Cant open anything for 30 mins .

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Did they not realise that everyone was facing bad gateway ?

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Classic Codeforces

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

UnratedForces!

»
4 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

"Unfortunately, the round is unrated."

Ah shit! Here we go again!

»
4 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

That's why we need daily contests XD

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Unrated, right?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Unfortunately, the round is unrated.

*Fortunately

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

UNRATED

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

You should have postponed the contest instead of starting. Sad for the author.

»
4 года назад, # |
  Проголосовать: нравится +114 Проголосовать: не нравится

...

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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...

»
4 года назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

WTF, back to back to unrated contest!

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

I feel bad for awoo and his efforts :(

»
4 года назад, # |
  Проголосовать: нравится +44 Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится -19 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

This even worse than yesterday's round

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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!!

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

A. Yet another wasted problemset

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

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

July 2020: This contest is unusual to be rated.

»
4 года назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

Unrated again!! :(

»
4 года назад, # |
  Проголосовать: нравится +44 Проголосовать: не нравится

»
4 года назад, # |
Rev. 5   Проголосовать: нравится +3 Проголосовать: не нравится
»
4 года назад, # |
Rev. 2   Проголосовать: нравится -42 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +16 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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?
      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

        Facts:

        • Long queue and inability to enter the site are different problems.
»
4 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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.

»
4 года назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

DeadForces :-)

»
4 года назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

DeadForces :-)

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Please, arrange a testing round. We don't want unrated contest any more.

Sorry For My Bad English

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

All we need is Hope

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Ahh, test 7 killed me.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Any hint regarding test 7 in D ?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What's the test 7 for D

»
4 года назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

The problems were good!!!

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve D?

  • »
    »
    4 года назад, # ^ |
    Rev. 12   Проголосовать: нравится +8 Проголосовать: не нравится

    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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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$$$.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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]

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        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.

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Pls explain your idea of D.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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?

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve E?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

        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.

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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)

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

86694208

»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Thanks for the contest anyway, I liked the problems.

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 ?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
4 года назад, # |
  Проголосовать: нравится +44 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

the problems were very nice.Specially problem E.In E i used dsu algorithm.But sad that contest is unrated.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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.

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      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!

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

        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.

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

        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.

»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 3   Проголосовать: нравится +10 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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)?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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