I_love_myself's blog

Codeforces Round #637 — Thanks, Ivan Belonogov!
By I_love_myself, 5 years ago, translation, In English

Hello, Codeforces!

I'm glad to invite you to Codeforces Round 637 (Div. 1) - Thanks, Ivan Belonogov! and Codeforces Round 637 (Div. 2) - Thanks, Ivan Belonogov!, which will be held on Apr/23/2020 17:45 (Moscow time). The round will be rated for both divisions (I hope).

All problems were written and prepared by Aleksey Aleks5d Upirvitskiy, Alexey alexX512 Perevyshin and by me, Denis I_love_myself Sapozhnikov. Thanks to 300iq, voidmax, ashmelev, Akulyat, okwedook, Minnakhmetov, divanik, Zakoden, Jostic11, Nakinamo, 4qqqq и allisyonok for testing problems and good advice, isaf27 for round coordination and help with preparation and MikeMirzayanov for great systems Codeforces and Polygon.

You will be given 6 problems in both divisions and 2.5 hours to solve them. Please, read all the problems. Good luck, have fun and I wish everyone high ratings!

The scoring distribution will be announced closer to the beginning of the round.

Did you notice unusual in the title of the round? Here is the message from MikeMirzayanov:

With this round we want to convey fiery greetings and once again say thanks for the support to Ivan Belonogov Belonogov. And it’s not only about his significant gift on the 10th anniversary of the platform. Starting to participate in 2011, Ivan has come a long way from a participant in Div. 2 rounds to the international grandmaster, became the ICPC world champion as part of ITMO team. Such a striking motivational example of a success story! Thank you, Ivan!

UPD1: The scoring distribution will be:
Div1: 500-750-1250-1750-2250-3000
Div2: 500-1000-1500-1750-2250-2750

UPD2: Due to technical problems, the round is delayed by 10 minutes. Sorry!

UPD3: Editorial is published!

UPD4: This was our first round and we made mistakes wherever possible. Sorry for this. We decided to make Div1 round unrated, Div2 round is still rated. You can read more details in this post. We hope that you enjoyed solving interesting problems and did not pay attention to our mistakes.

Tags 637
  • Vote: I like it
  • +125
  • Vote: I do not like it

Comments Comments (387)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it -329 Vote: I do not like it

Just go away! Don't read this....

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

    Let's take the initiative to never Comment.Lol!

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

      Yeah! This happens every time when I comment!

      • @kaushal_26 what happened to your comment! LOL
      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 5   Vote: I like it -198 Vote: I do not like it

        And just do it one more time!

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

        "This happens every time"

        maybe because your comments are no help or use for the community.

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

Good luck and have fun, everyone! :D

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

Some division rounds are of 2 hours while some of 2.5 hours. I am curious as they both have same number of questions(on average). What is the reason then? Is it that the 2.5 hour rounds are slightly tougher/ implementation heavy?

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

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

    Aha.. figured it! They contain questions similar to 2hr round contests but in a difficult language!

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

      Well, I took Virtual participation last night and spent 0.5h understanding the meaning of Problem B.

      The statement is too difficult for people who do not use English as mother tongue to understand quickly.

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

As one of the testers of this round, I can say that tasks are too interesting. Hope that the authors ' efforts will not be in vain :_)

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

I hope it'll be easy.

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

How many problems will there be?

5 or 6 or 7

or

6 or 7 or 8?

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

I wish this blog was posted at codeforces top page so I don't have to find this blog.

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

https://codeforces.net/blog/entry/68665

i have some questions...

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

Hope the problem statements will be short.

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

My first Div. 1 contest! Hoping I can still participate in Div. 1 after this.

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

what is ivan's codeforces handel?

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

It has been mentioned that $$$Please,\,read\,\, all\,\, the\,\, problems.$$$ Does this mean that problems might not be in increasing order of difficulty?

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

.

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

The only question about the contest

Will the No. 1 spot in the rating change ?

tourist or jqdai0815 or Anyone else

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

Deleted

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

"I love myself" is such a good user name :D

Hope this round will have strong pretests.

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

Wish everyone high rating and I hope that most of you go to the next rank in this contest.

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

hopefully the problem statements would be short..

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

Much more frequent contests

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

I_love_myself will there be any sub-part problems?

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

Good！

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

Thanks, Ivan Belonogov.

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

Good luck, guys!

We will be live upsolving the round when it ends:

https://youtu.be/0kr6YSroclg

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

    hey!! I watched your videos. Nice explanation. Good job done :) I have a doubt in problem E. You figured out that cyclic dp will create a problem as the recursion will catch itself in loop. So, we should use dijikstra, to find minimum distance from source(0) to destination(n), by considering dp states. So, the solution Time complexity will be : m*(g+r)*log(m*(g+r)), which will cause TLE. So, how to optimise it?

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

Thank you, Ivan!

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

Interesting nickname

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

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

Thank you mister Ivan Belonogov Belonogov

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

Hope this round has strong pretests...

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

What will be the score distribution?

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

Good luck and have fun

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

Can we please have the scoring distribution now I_love_myself ?

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

    I'm curious to know why people want to know the scoring distribution? Does scoring distribution impact how you are going to attempt the questions? Or is there anything else? (For me it is sufficient to know that the later questions have more marks then the previous ones)

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

    Done!

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

Good luck everyone!

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

[Deleted]

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

Programmers are so bored in quarantine, they are giving downvote to maximum comments O_o

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

Thanks Ivan for his support ! Hope that one day I could be like him <3

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

Why has it been extended by 15 mins?

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

why it is delayed?

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

I was checking my phone for a few minutes, then saw the contest page again and thought I had slept and woke up for the next contest. /s

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

When it is delayed ...

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

delay 10m :((

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

 

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

Yet another long round, 2 hours 30 minutes (+10 minutes delay?)

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

no electricity in my place...So its good..hope electricity comes back in 10 minutes

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

    codeforces knew it , they did it for you

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

      Electricity came just after writing the comment...

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

10 minutes delay after a long time.

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

Round hasn't even started, but codeforces already start to lag :/

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

when I went to have my dinner, I had 12 minutes left.. When I came back I still had 12 left

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

IT took me one minute to realize my network is still working well and the time on my clock is still right...

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

Antipleasant tasks, I wish authors to end third grade faster

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

    Can't agree more. I just give up this round.

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

Extreme long statements, to reach the actual question its taking time.

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

I did register for the Div. 1, the website even did notice me about the contest started and I clicked Enter button

But then after I finished the 1st problem, the website says I never register!!!!!

Do I really need to register for both Div. 1 and Div. 2 to join the contest??

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

The problem statements are too complicated!

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

IMO problem C is so cool!

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

Recently, the div2 rounds are not being scheduled on weekends like it used to happen earlier. Been missing a lot of recent rounds because of this. Looking forward to more weekend contests :)

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

Div2 D weak pretests :C

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

$$$My\,\,Dad:-\,$$$ Don't run behind the girls. They are too complicated. you can be ruined.

$$$Me\,to\,\,my\, \,Dad$$$ (after this round) $$$:-$$$ They can complicate a problem statement too if they appear.

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

I haven't seen a cancer like this before.

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

I would say div2 C is too complicated

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

Tasks description was so long, I had to print it on paper because text didn't fit my screen resoltion.

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

I mean, task should not test our reading skills. It took me way too long to understand and at the end I ended up not understanding the problem anyway.

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

UGH !!!!

StatementForces !

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

Denis(in the statement) is such a poor guy.

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

I hate those div1 coders who make fake profiles just to take part in div2, pls stop doing this! Are you guys afraid to take part in div1, afraid to lose your rating? If that's the case i feel sorry for you. I might have a lot less rating than you guys but i take part in contests to learn new things, not just to improve my rating!

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

statements are too long to be read...

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

VeryLongProblemStatementForces

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

I don't know about E and F, but the rest of the problems from Div2 were absolute trash: no creative thinking, pure implementation. And the length of problem statements is another story.

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

The problems are shreiking and saying comprehension skills are better to be developed than coding skills. Hope codeforces will not make such lengthy problem statements in future which further decomposes just to a for loop only . Those who read fast are fast scorers in this contest.

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

Haha.. Loved the story line!

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

Very much complicated problem statements. And 2-3 lines of these complex story is necessary to solve the problems. Rest of them only confused me.

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

How to solve Div-2 D. Will greedy work here ?

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

    Actually soln is greedy but take care of valid string after using exactly k.

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

      I thought of doing dp. But, tge implementation was very difficult for me to do.

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

    You can look at English Commentary of Problem D here I hope it helps!

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

      Thanks, understood the mistake I was making.

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

How to solve Div.1 C?

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

    My solution which takes O(m*g*log(m*g)) passed the pretests. I just use dijkstra with vertices are (index of safe point, time left to move before red light)

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

      I didn't think that would pass though :/

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

      You can just use 0-1 bfs instead of dijkstra to remove log.

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

        how does the 0-1 bfs work?

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

          It's same as regular bfs, but instead of queue use deque and if cost of edge is 0 push to the front of deque else to the back.

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

            sorry, I meant to ask how you use it to solve problem C because my dijkstra had wasn't on a graph with 0/1 edge weights

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

              If we change distance to number of (r + g) time segments costs will be 0\1.

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

                ah that's nice. thanks!

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

    I just did Dijkstra and passed the pretests. However, it passed too tight.

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

Pretest 5 of Div2D?

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

What is the test case 5 for DIV.2 D?

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

How to solve div1C/2E ?

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

I have no issues with stories in problem statements if they fit in well, but the story of Div2B seems like its just been created for the sake of having a story and has practically no relation to the actual problem. In my opnion the entire 4th and 5th paragraphs are utterly useless and just serve to confuse people.

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

WORST STATEMENTS EVER!!! English was so broken and not understandable at some times that I can't even. And to top it all off, inital version of Div1E was some freaking misunderstanding, a very bad joke. It contained a lot of very weird words, like "power" instead of "degree", firstly "pick" instead of vertex, then "peak" instead of vertex and then some very weird sentence for making a move with some random "top" in the middle of it. Of course the statement was corrected, but SILENTLY AGAIN. Less than two weeks ago, I requested that whenever any changes are made then please make an appropriate announcements https://codeforces.net/blog/entry/75806?#comment-601901 and no improvement here. Quality of statements and that poor misunderstanding called initial statement of Div1E and no broadcast after its change made me rage quit the contest first time in many years.

EDIT: Sad part is that problems alone seemed really nice. But even though I was pretty pumped up with energy and good hopes before the contest, all I could find in today's contest was confusion and anger.

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

    Yet we still get an annoying announcement for "the checkpoints in C may not be given in sorted order".

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

      Yes, like what the frick was that? It made me angry as well. First embarassing thing was to allow an input format without such natural condition. When searching for bugs in my code I reread the statement like two times in the search of condition that they are sorted, because I could not believe my eyes it is not present. And then, I don't care whether you get 1000 questions about whether this sequence is sorted or not, you went for such poorly or evilly prepared contest, so let's take responsibility for your actions and do not make it unfair for people that spend their time and nerves on this. We do not get an announcement "hey, statement of E was complete shit, you should reload it", but we get "hey, you get WA because you didn't notice that some sequence doesnt have to be sorted"...

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

        Not including non-sorted case in pretests(or even examples) was just stupid.

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

    Yeah, the statements were shit.

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

    If somebody is interested in the original statement of D1E:

    Surely you all read the book "Alice in Wonderland". In this task, Nastya got to the country of Three strange Bees. The bees are strange because their honeycombs are pentagonal. Nastya got there illegally, so she wants you not to catch her. Help the bees punish the intruder!

    This is an interactive problem.

    A beehive is a connected undirected graph along the edges of which bees and Nastya can move. A graph satisfies two properties:

    The power of any of its vertex is no more than 3. For each edge, there exists a cycle of length not greater than 5 passing through this edge. There are three bees and Nastya. You play for bees. Firstly, you choose the picks where you put the bees. Then Nastya chooses another peak in which she will initially appear. One move is first moving the bees, then Nastya, in turn: For each of your bees, you can either move each one along some edge of the graph, coming out from the top where this bee is or leave it in place. Then Nastya will necessarily move along some edge of the graph, coming out of the vertex in which she is now located. You win if at least one of the bees and Nastya are in the same peak at any time of the game.

    If this situation does not occur after n moves, then you lose.

    Several bees can be in the same vertex.

    Input

    The first line contains two integers n (4≤n≤5000) and m (n≤m≤3n) — the number of vertices and edges in the graph.

    Each of the next m lines contains two integers v and u (1≤v,u≤n), which mean that there is an edge between the vertices v and u. It is guaranteed that the graph is connected, does not contain loops that the degree of any vertex does not exceed 3 and a cycle of length no more than 5 passes through each edge. Note that the graph may contain multiple edges.

    Interaction

    At each turn, you must output exactly three vertices a,b,c (1≤a,b,c≤n). For the first time, 3 vertices displayed will indicate which vertices you originally placed bees on. In response, you will receive the top where the jury placed Nastya. Each next 3 vertices will indicate where the 3 bees are after your turn. Each of the bees can, regardless of other bees, both remain at the current peak and move along the edge. After the next output of 3 vertices, in response, you get the number of the new vertex to which Nastya went.

    As soon as one of the bees is at the same peak with Nastya or you have reached the limit on the number of moves, your program should complete the work. That is if you made a move, and one of the bees ended up at the same peak with Nastya, your program must complete the work, or if Nastya made a move and ended up at the same peak with one of the bees, you should not make your move and the program should complete the work.

    If the number of spells exceeds limit (n, where n is the number of vertices), you will get the Wrong Answer verdict.

    Your solution may receive the verdict Idleness Limit Exceeded if you don't output anything or forget to flush the output buffer.

    To flush the output buffer, you need to do the following immediately after printing the query and the line end:

    fflush(stdout) or cout.flush() in C++; System.out.flush() in Java; flush(output) in Pascal; stdout.flush() in Python; for other languages see documentation. In this problem interactor is adaptive. This means that depending on all your previous moves, Nastya's behavior may change.

    Hacks are not available for this problem.

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

What is Test 3 in 1C ?

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

It was hard to comprehend the problem statements.

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

I took more time to understand C than to code the solution

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

For Div.2 C I am sharing my strategy to solve it which has passed the pretests.

Take an example of n = 7 and 1-indexed array arr and position allotment p:

Step 1: i = 1 arr = [1,1,1,1,1,1,1] Now generator can select any index from 1 to 7. Suppose it selects index-4. Now we can't select position-4 further. p = [?,?,?,1,?,?,?]

Step 2: i = 2 arr = [1,1,1,?,2,1,1] Now generator will have to select will have to select position-5 as it is the
maximum position. p = [?,?,?,1,2,?,?]

Step 3: i = 3 arr = [1,1,1,?,?,3,1] Now position 6. p = [?,?,?,1,2,3,?]

Step 4: i = 4 arr = [1,1,1,?,?,?,4] Now position 7. p = [?,?,?,1,2,3,4]

Step 5: i = 5 arr = [1,1,1,?,?,?,?] Now again generator can select any index from 1 to 3. Suppose it selects index-3. p = [?,?,5,1,2,3,4]

Step 6: i = 6 arr = [1,1,?,?,?,?,?] Now again generator can select any index from 1 to 2. Suppose it selects index-1. p = [6,?,5,1,2,3,4]

Step 7: i = 7 arr = [?,1,?,?,?,?,?] p = [6,7,5,1,2,3,4]

KEY OBSERVATIONS:

1: If the position j is selected for number i, Then the remaining positions with a greater index should be placed with i+1 and so on i.e. position j+1 with i+1,j+2 with i+2... 2: Positions less than j will again depend on selection by the generator as all the values will be 1. The assignment of the remaining positions could be considered
again as the new problem with the unassigned minimum number which is 5 in the above example.

Any permutation follows these observations results "Yes" else "No".

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

I Read problem C for 40 minutes then only got what it is saying. In B also sometimes setter says that peaks have to be answered and sometimes says parts of doors another dielemma NO comments for A(Which is a first ever Div2 A seen by me!)

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

How to solve E? dijkstra's gave TLE.

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

Maybe my English is so poor that I can't even understand the meaning of the problem.I am so sad.

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

    No, it was the English of round's authors.

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

i feel so smart writing a 100 line function to check the current number in D, only to notice that the strings were given in the problem statement :), and unable to submit it in time because of that.

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

I dunno why the time limit for div.2 D was so tight. It cost me like 14 submissions to pass the pretests.

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

Was fun typing all the digits on Div1B before realizing that it's listed...

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

    Good to know I'm not the only person who actually wrote them all out (though I'm probably the only one who wrote one incorrectly and got a WA).

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

    I realized it now, after reading your comment. XD

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

    Since you have to copy manually anyway, how about:

    const bitset<7> dig[10] = {
    bitset<7>("1110111"),
    bitset<7>("0010010"),
    bitset<7>("1011101"),
    bitset<7>("1011011"),
    bitset<7>("0111010"),
    bitset<7>("1101011"),
    bitset<7>("1101111"),
    bitset<7>("1010010"),
    bitset<7>("1111111"),
    bitset<7>("1111011"),
};
    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +91 Vote: I do not like it

      you can also do

      vector<int> bits {
  0b1110111,
  0b0010010,
  0b1011101,
  0b1011011,
  0b0111010,
  0b1101011,
  0b1101111,
  0b1010010,
  0b1111111,
  0b1111011,
};
      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I Copied the line from the problem statement and put it in a string vector .

        void diginit()
{
    vector<string> arr = {"1110111", "0010010", "1011101", "1011011", "0111010", "1101011", "1101111", "1010010", "1111111", "1111011"};
    foru( i, 0, arr.size())
    {
        string s = arr[i];
        vi temp;
        for (auto it : s)
        {
            temp.pb(it - '0');
        }
        digit.pb(temp);
    }
}
        → Reply
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

A: So easy. B: So easy. C: I need some time to find the construction method. Oh I make it! D: It's slightly difficult, but I can solve it with more time. E: ??? ...OK, Good night.

That's all.

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

I think the constraints on problem E (Nastya and Unexpected Guest) were too tight for Java. After my first try the program failed due to time on the third pretest and after implementing some stupid optimizations (not changing the O complexity) I got the program to reach the pretest 8. Here's my program if anyone's wondering: https://pastebin.com/Z3Xjg1rk. I'm fairly positive my program would work if the time limit was 2 seconds instead of 1.

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

    If you had used 0-1 BFS, which is probably the intended idea, even a Java solution would have passed.

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

      Can you explain how to use 0-1 BFS in the problem? How do you interpret the problem as one with 0-1 edges?

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

        Make the graph where vertices are pairs of numbers

        $$$(t, p) \in \{0, \dots, g\} \times \{1, \dots, m\}$$$

        representing being at the $$$p$$$th line at time $$$t$$$. There's an edge between $$$(g, p)$$$ and $$$(0, p)$$$ of weight $$$1$$$, which corresponds to waiting at that spot during the red light. Also put edges between $$$(g, p)$$$ and $$$(g+dist(p, p+1), p+1)$$$ and $$$(g+dist(p, p-1), p-1)$$$ (as long as those numbers are in the right ranges) which correspond to moving forward or backward. These edges have weight $$$0$$$, since there's no red light you have to wait for.

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

The video tutorial of Div-2D.

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

Just imagine sposoring this round xDDDD

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

I don't want to blame any of the authors, the tasks (at least A,B,C,D) were good in my opinion. However, the staments for B and C are long and hard to read for no reason at all.

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

Was it just me or were some of the problem statements rather long and complex? I decided to start with Div2 C and feel like I made a big mistake. I spent forever trying to understand what the problem was asking for. Decided not to submit anything as I had lost too much time. Which is unfortunate as some of the other problems were very interesting..

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

Video Tutorial for today's div2D/div1B

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

Is there not a maxtest in the pretests of Div2D/1B? My solution takes 70 * n ^ 2 instead of 10 * n * k but still passes pretests in around 200ms even though it should take upto 3e8 operations. Fast simple operations or weak pretests? 77820531

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

My idea for D, unfortunately I spent a lot of time solving slightly different versions of this problem and understood the statement correctly too late:

  • It's a modification of DFS — the following describes processing some subtree.
  • The key is that if we move down to this vertex from its parent at times $$$t \rightarrow t+1$$$, we want to move back also at times $$$t \rightarrow t+1$$$.
  • Clearly, we want to rewind at some point. We'll process subtrees of some $$$s_1$$$ sons, returning from them at times $$$t+2, t+3, \ldots, t+s_1+1$$$, then rewind to a time $$$t-s_2$$$ and process the subtrees of the $$$s_2$$$ remaining sons, returning from them at times $$$t-s_2+1, t-s_2+2, \ldots, t-s_2+s_2=t$$$. Finally, we move back.
  • This is optimal because we either have $$$s \le t$$$ sons and choose $$$s_1=0, s_2=s$$$, which means $$$t+1$$$ is the maximum used time and we don't make the max. time worse by what we're doing in this vertex, or we have $$$s \gt t$$$ sons, choose $$$s_1 = s-t, s_2=t$$$ and the worst-case time is just $$$s+1$$$, which is the obvious lower bound — we need to visit each vertex at least as many times as its degree (+1 for the initial visit of the root).

This is the comment I wanted to post 3 HOURS AGO

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

Trust me the test cases are weaker than my eyesight!

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

Can someone please explain 2 C ?

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

    incase the input was

    7 8 9 4 5 6 1 2 3 then the output will be Yes. 7 8 9 4 5 6 10 1 2 3 then the output will be No. hope this gives you a fair idea.

    what i did was : added the first contiguous increasing subarray at the end of the deque, and pushing the 2nd contiguous increasing subarray using push_front in deque.

    If I end up with with a sorted deque then the ouput will be yes, else no. refer my code : https://codeforces.net/contest/1341/submission/77810951

    I believe the question statement were a little confusing atleast for me !

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

Did anybody solve F using algebra? Without signs it would be doable with matrices/permutations for example, but it became harder with the signs.

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

    Can you please share your approach ?

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

      Do you mean a normal solution to F, or the approach with matrices/permutations to the problem without signs?

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

        I meant the approach with matrices/permutations to the problem without signs.

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

          With permutations, for each type of bracket choose some permutation which consists only of cycles of length at most $$$2$$$, possibly different permutations for different types. Now, the composition of permutations of the brackets from the left to the right will be the identity if the string is a correct bracket sequence and won't be and identity with high probability otherwise (if you chose long enough permutations and selected them randomly for example). Build a segment tree ofc.

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

    Wasted most of the contest on this approach. :(

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

      A function on finite sets can't really satisfy fg = 1 and gf != 1, it doesn't seem too fruitful

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

        Yes, I realized this during contest but thought that if we checked all balances independently after that, that would fix it. But it doesnt work on "([)(])".

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

          Yea, I've even rushed for implementing checking all balances independently. I saw this case somewhere else after the contest, it looks hard.

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

          Do you know how to do it faster than $$$O(n \cdot \sqrt{n\cdot \log(n)})$$$ btw? (Assuming $$$q=n$$$).

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

Decent contest!

Solution notes for A-D (Div 2): A) The range of sum of x is [(a-b)*n,(a+b)*n] and it works iff it intersects with [c-d,c+d]

B) Use two pointers/sliding window type approach, where you add or subtract depending on the point you remove and add each step. Becomes O(n) instead of naive O(n^2)

C) Basically if you put something at a point such that all other points to the right of it are filled, then we don't need to do anything. Otherwise, if we put l at point x, we put l+1 at point x+1, l+2 at point x+2..and so on until we hit a point at the right that we put previously, so we need to check if their position in the permutation is consistent with this.

D) Basically dp[n][k] from n-1 to 0, where dp[i][j] stores the leading digit of the best result you can get with strings [i,n) and exactly j moves available.

How do you do E? I think E was some sort of dp/dijkstra shortest paths, but couldn't figure out how to find if two points where reachable from each other in exactly g steps quickly... there could be a lot of alternating involved so there were lots of states.

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

Was it only me or the statement of DIV2 B was kind of misleading as initially it said the segment end should not be peaks but to pass the pretests they were considering segments ending at peaks also. Waisted a lot of time figuring this. Such an easy problem took 1 hr to get passed because of poor statements. Kindly make statements good as they really affect the rating.

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

Nice problem statements. First time seeing problem statements of different problems have continuing/same story.

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

In addition to the bad and unnecessarily long statements, I was rather surprised by the constraints / time limit on Div1 C — either make it so Dijkstra (with log) fails for all, or make it so Dijkstra passes for the most common programming language. In this case some C++ solution passed and some failed without seemingly any difference. I challenged several people successfully and some unsuccessfully (some passing for 0.966s). Was it that hard to make the constraints on M <= 20,000 or 5,000 (instead of 10,000)?

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

    Agreed--constant factor played way too much of a role here. I'm not sure how they managed to miss such a glaring issue with a dozen or so testers--the Dijkstra solution obviously exists, so they should have made a clearer decision about whether to fail it or not. Relying on hacks to catch a wrong solution is an extremely bad idea because it means that people who are hacked have a chance to fix their solutions and resubmit, while people who aren't just FST.

    I thought 1D was a very nice problem, but at this point I'm not sure it makes up for the extremely weak pretests and long statements of the rest of the set.

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

    If Dijkstra isn't the intended solution, you should fail it in the pretests...

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

I am one of those not able to understand what 1341C - Nastya and Strange Generator asks for, tried for an hour. Luckyly was able to solve D afterwards, but that was no fun.

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

Imagine the level of frustration when you have to throw a door at MoUnTaIn PeAkS to break them.

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

    It was the most frustrating problem statement ever! The whole thing was so misleading!

    Even in div2 d he is talking about broken sticks! when something is broken how are you supposed to turn it on?

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

The array in Div1 C isn't sorted and there is no test for that in pretests...

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

Can someone help me ? What states of dp should i use for Div2 Problem D?

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

    Two states are required. index of the board and current value of k.

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

I did Div2 D with greedy approach Nlogn(Hacked)

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

We've got a wrong answer on test 1 on system tests 77835164!

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

    Yeah, it took me some years of practice to achieve such outcome with deterministic solution :)

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

Was checker for problem D wrong during the contest? Even when my solution output two equal pairs in the sample, it got WA 3, not WA 1.

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

    Yes, there was a tiny issue with the checker, it was fixed, but some solutions failed (8 solutions).

    We have written to all, whose solution failed.

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

I can understand that the problem statements were a little longer but I seriously think that the story deserves appreciation. Natsaya getting confused seeing a heart and breaking the door of heart on the mountains into pieces, Denis getting distracted about her love for a random permutation generator, Denis not able to stand still while he is after a girl and so even moving in the opposite directions. Man! That's really good writing.

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

    Which door stretches over mountain peaks man? I mean seriously??

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

      I know. It doesn't make sense. But I find it extremely hilarious.

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

Weak pretest in Div2A. :(

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

Hacked by Ashish

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

    I too did it without using DP

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

      Hacked you as well :)

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

        It stopped my hearbeat for a second

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

        Wait how can you hack after the contest?

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

          That's uphacking, you won't loose points for that and hence your rank won't be affected, you can read more about it here

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

            If I would be loosing points I would have to wait more to become Blue

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

            Hi, can you try hack my solution? 77797225

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

              5 0100111 1001111 1100111 1010110 0110010 Here is test case he is using

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

              Done :)

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

        are the system tests for d1B are ridiculously weak?

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

          Saw some greedy solutions passing sys tests :-/

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

            ........................sad

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

            Note that in the greedy solution one can use prefix sums of min needed sticks and max usable sticks.

            Using these we can check from left to right in every position the maximum number of usable sticks, and with that simply build the biggest possible digit.

            Given that the limited number of digits and 7-segments the complexity is something like O(n*10*10) and hence runs fairly fast.

            Example 77847086

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

              I wouldn't call your solution a greedy. It's more of a backtracking with a lot of early breaking, which is like the dp solution without memoization.

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

    Hacked :)

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

Shitty pretests for Div2 D.

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

This contest was the worst way to thank someone...

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

I'm a bit worried that Russian speaking participants were a bit privileged (guess why). Statements really seem to be taken from google translate, is it true?

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

    Don't underestimate Google Translate!

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

      "This road is not always can be crossed in one green light."

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

        that sounds worse than google translate. Actually, translating to russian and back again gives: This road cannot always be crossed in one green light.

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

      "From any square, you can get to any other in exactly the same way using these roads and not visiting the same square twice."

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

        I mean even google translate works better.

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

    Funny thing: while reading the Russian statements, I thought the original language is English, and translation is sub-par at times.

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

    Its like bad and worse. :(

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

So is this round unrated, since ratings are not updated? Kinda sad to have cleared the problems only to find out it. :(

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

    Wait for some time it will get updated

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

Damn, the first test where points in Div1 C are not sorted in the input is test 70...

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

I've solved div1E, but I'm pretty sure the following is a counter example.

My idea is to move your 3 bees to minimize the sum of the distances to the (up to) 3 neighbors of N (where you must match bees to neighbors). I've also seen other AC submissions with the same idea. (But instead of sum of distances they minimize the largest distance, then the 2nd largest distance, then the smallest distance).

For a counterexample, consider the 'ladder graph' made into a cycle: two cycles A and B of length n next to each other, where A_i is connected with B_i. Note that each vertex has degree 3, and that each edges is included in a cycle of length 4 (i.e. less than 5).

After picking initial bee positions close to A_0 and B_0, N can start at e.g. A_{n/4}. Now all my bees will move along the circle 1 step, and then N can just move one step up to A_{n/4+1}. This can continue forever I think.

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

    Yeah, I also got AC with incorrect solution. I think this problem has a lot of incorrect solutions for which is very hard to create counterexamples without knowing an idea of solution. But this cycled ladder graph is counterexample to lots of solutions, and it is very strange that it wasn't in tests.

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

      Sure it's difficult to make good test cases here, but I think the only way to make a cycle of length > 5 without chords is to make it so that the entire graph is one 'double' cycle. I think it's not possible to have 2 'independent' chordless cycles of length > 5.

      So given that this is the only special graph, you'd think that this needs extra testing.

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

        I and VladProg (who also got AC with wrong solution) also discussed solution that tries to move bees to different adjacent vertexes to Nastya's vertex without going through another adjacent vertexes to Nastya's vertex. This solution will pass cycled ladder test (because if you remove all adjacent vertexes to Nastya's vertex there will be no long cycle) but there exists another counterexample, like cycled pentagons.

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

          Ah, that's a neat idea, but yeah won't work for even bulkier cycles.

          Another idea is to choose the initial positions roughly at 0, 1/3rd, and 2/3rd along the cycle. E.g. by fixing 0 and then choosing u, v such that d[0][u] + d[u][v] + d[v][0] is maximal.

          Also found a construction to turn any graph G into a graph H suitable for this problem such that G is a minor of H, so you can definitely get more complicated inputs than just cycles.

          Anyway I'd love to see a proof that this approach works even in graphs without long cycles. The 'every edge in cycle of length <= 5' condition is useful because now some of the bees will always 'take the long route' to block off potential exits, but I can't yet prove that the max distance or sum of distances goes down by at least 1 or 3 respectively each turn.

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

            So it's actually quite easy to embed K_5:

            https://imgur.com/a/LC60kW9

            If you make all 'edges' 100+ steps long I think it should be possible to escape.

            Maybe in practice the condition is/should have been that such long cycles do not exist at all anyway? So formally you can reduce the graph to a point by repeatedly contracting cycles of length <=5 to a point.

            Also, congrats on being red now ;)

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

              Thanks ;)

              Yeah, in random graph you can replace edges with these "ladders" and you will get graph that satisfies problem statement. (also you can split each vertex with degree > 3 into few vertexes with degree = 3 with length of ladder between them equal to zero). But obviously there exists a graph that has minimum number of bees larger than three. I suppose it's impossible (or possible, but using very big number of queries) to catch Nastya on these graphs.

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

Missed out on 1D because I left out a ++pt; in one of my loops. How fun.

Cool problem, though.

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

In Div1 B I thought k would always be less than or equal to number of sticks which are off.As said in the problem statement, what is the maximum number that can burn on the board if you turn on exactly k sticks (which are off now) Reading the line(specially the sentence in the bracket), it seemed to me that at least k lights are off.Which led to wa in system test.

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

When you realize tourist solved Div1B in 00:04, while you can't even read the statement in that time

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

I guess the extra 30 minutes from ingeneral round was for reading the long paragraph in each question...

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

In div2D/div1B, case where solution can consist of leading zeroes isn't present in the systests. Thought I'd fst, but didn't. code case

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

I solve A(div1) so l check if we have anybody what a[i] + 1 < a[i+1] answer No else Yes.

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

hmm, I had the exact same code on all 3 submissions...

Are the data structures on newer versions of C++ faster? 77856421 77857168 77857210

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

    Off the tangent, but what made you try this check?

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

      I opened up the status page and looked at the C++ solutions that passed, and most were in C++ 17 or C++ 17 (64). I switched to C++ from Java pretty recently, so I don't know too much about which version of C++ is best for certain situations. I guess this is one of those situations?

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

        Due to the c++17 (64) being 64 bit, the compiler may emit optimizations that the non (64) variants may not. This will optimize it for the computers that the tests are running on, rather than intentionally handicapping it to keep the performance more similar to other languages. It was discussed when it was added a month or two back

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

          I see. I'll check out that blog. Thanks!

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

    I suggest you make a blog, I would like to know the answer to this too. I mean this is literally double the speed compared to the other 2.

    I tried resubmitting some of my code too and its significantly faster

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

    With GNU C++ 17 I think it is slightly faster or there is a little bit more optimization.

    I can be wrong, but you have long long (64-bit) type in your solution. That's why GNU C++ 17 got TL while 17(64) got AC — it works 2 times faster with 64-bit numbers.

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

    pretty sure operations with long longs are one instruction each in 64-bit, but multiple in 32-bit, so long longs are a lot faster with 64-bit.

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

      That seems to be it; I switched to integers and got the same execution time, but half the memory usage.

      PS: congrats on the red, the color changed right after my refresh on posting

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

    This blog might be related.

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

![ ]()

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

GG loosing 700 points for long long . . ., i just changed long long to int and got accept in D1C, why should the constraints be that much though?

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

    I think int should pass. As the distance to n can be at max (r+g)*m.

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

      I know that, but on that point i couldn't see any point to avoid long longs.

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

        I think long long might not pass because it might print numbers like this: 3e9+5

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

Problem were nice anyway, thx (especially D1C, E)

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

Div1E is so beautiful! I still do not fully understand why my solution pass, but it is so stupidly elegant! Unfortunately, made some mistakes in code during contest... Tnx for the wonderful problem :)

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

Apparently creating variables CAN be your code's bottleneck: 77824459 77859221

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

    This is rather particular to std::vector; vector::clear() doesn't actually deallocate the vector's internal buffer, so reusing the vector means you actually do many fewer dynamic memory allocations. This is compounded by the fact that vectors dynamically resize as you push_back (doubling when necessary), so you're actually saving a couple allocations per loop. You might be able to pass the problem by just doing vector::reserve(...).

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

Hacked 3 greedy solutions in D1-B using very simple case:

1 2
0010010

(This corresponds to a digit 1.)

Answer should be 4, but greedy solutions that consider the first compatible digit in descending order would pick 7 first then report impossible. Since there is 1 remaining broken segment, and such solutions only consider "patching" 9 -> 8 in such cases. And solutions which consider the first compatible digit in ascending order would pick 1, and report impossible as well.

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

Anyone can explain better how to solve Div1C-Div2E with 0-1BFS instead of dijkstra. Please. Thanks in advanced

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

    Construct a graph. Let a vertex in the graph be a pair $$$(i, k)$$$ where $$$i$$$ is the index of some intersection (sorted), and $$$k$$$ is the number of seconds which have passed since the light most recently became green. Every vertex (except when $$$i = 0$$$ or $$$i = m-1$$$) has two outbound edges, corresponding to the intersections before and after it (changing $$$k$$$ as we would expect). Note that we can only transition if we have enough time left before the light changes. In the case where we have to wait for a red light at the destination intersection (i.e. we reach the destination exactly as the light turns red), label the edge with weight $$$1$$$, otherwise $$$0$$$. Now run 0-1 bfs to find the shortest path to all vertices.

    Once bfs is finished, iterate over all vertices $$$(i, k)$$$. If the destination is reachable from this vertex in less than $$$g$$$ seconds, the final answer for this vertex is $$$(r+g)\cdot c+k+n-d_i$$$ where $$$c$$$ is the cost to reach this vertex in the graph. Output the minimum final answer for all vertices.

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

      Can you explain the intuition for labelling the edge weight 1 and 0? I understand the dijsktra solution but having a hard time understanding how it can be optimized to 0-1 bfs? I would appreciate it!

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

        I'm not sure which part you don't understand. The total cost of a path is simply the number of times we have to wait for a red light. If we have to wait, the edge has weight $$$1$$$. Otherwise, we don't wait for a light, and the edge has weight $$$0$$$.

        I guess the key intuition is that if you tell me, "I waited for a red light $$$c$$$ times, and then walked for $$$k$$$ seconds afterwards, ending up at position $$$d_i$$$," then that is actually enough information for me to deduce the exact number of seconds you took getting from start to finish, and it is given by the formula in my previous comment.

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

          Thank you for the response. After some thinking, (r + g) * c does make sense. because when you wait for the red light c times, c green light seconds must have occurred as well.

          But I don't understand the k + n - d[i] part and iterating over all vertices. Can you explain intuition? I would appreciate answer. I think n - d[i] is counter-intuitive because you are subtracting the end from the d[i]. Wouldn't you have to wait additional red lights when considering 1 to d[i] to N.

          Edit: https://codeforces.net/blog/entry/76348?#comment-609660 This is a similar solution, but it iterates all possible ending elapsed time on the last island (i.e. m). It's easier to understand, but of course, I still want to understand your variation

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

            Yes, I agree that some other approaches may be more elegant. The formula I gave above is just what occurred to me during the contest, so I went with it.

            The expression $$$(r+g)\cdot c$$$ gives us the amount of seconds from the start until the light last switched to green. The value $$$k$$$ gives us the amount of seconds since the light last switched to green until now. So adding them together gives the number of seconds to reach vertex $$$(i, k)$$$ from the start.

            Now, $$$(i, k)$$$ is not necessarily the destination. We would like to know how many additional seconds it will take to reach the destination from the vertex $$$(i, k)$$$. This is simply the distance between us and the destination, i.e. $$$n-d_i$$$. We only consider the cases where we don't have to wait for any additional red lights, so if $$$n-d_i > g-k$$$, we simply don't use this vertex for our answer.

            Among all vertices which do satisfy that condition, we want to find the shortest resulting path. Any vertex with $$$n-d_i \leq g-k$$$ constitutes a valid path, so we minimize over all such choices.

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

    Let d[u][t] the minimal amount of times you had to wait r + g seconds to get to vertex u and the green light has been on for the last t seconds. Transitions are possible if the amount of seconds needed to get to adjacent vertex does not exceed g. If it is possible to get to and adjacent vertex v and the green light had been on for g seconds then you have to wait r more seconds so the light turns green again. Don't know if I made myself clear

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

      Not sure if I'm missing something. But isn't that observation just enough to figure out the dijkstra solution? I'm still unable to understand the intuition how the edges can become 0-1. Because in each transition, the cost if the difference between the two safe islands.

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

        Let the state $$$(u, t)$$$ be that you are currently at island $$$u$$$ and have elapsed $$$t$$$ seconds since green light started. Then transitions will be:

        $$$(u, t) \rightarrow (v, t + dist(u, v))$$$

        • Cost: $$$0$$$
        • You only care about moving between neighboring islands (i.e. $$$|u - v| = 1$$$).
        • You only care if you can perform such step before Green light ends: $$$t + dist(u, v) \le G$$$

        $$$(u, G) \rightarrow (u, 0)$$$

        • Cost: $$$G + R$$$ You add all time spent to get here ($$$G$$$ seconds) plus the wait on the red light ($$$R$$$ more seconds).
        • Notice you only care about this when $$$t = G$$$ (when you have finished a non-stop trip during the green light time span).

        If you fix the time elapsed when you reach the final island to be $$$f$$$ the answer will be: $$$cost(m, f) + f$$$. Minimum time to reach $$$(m, f)$$$ plus the last $$$f$$$ seconds elapsed on the current green light.

        Iterate through all final $$$f$$$ and profit.

        Notice that the graph built only has two cost, (and one is $$$0$$$) so BFS0/1 can be applied.

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

Some examples. Not all of them are incorrect ofc., some just mean what they should mean in the worst manner:

"This road is not always can be crossed in one green light." <3

"...what is the maximum number that can burn on the board..."

"...there is a road of $$$n$$$ lines."

"From any square, you can get to any other in exactly the same way using these roads..."(exactly the same way as what?)

"...and will return to the first and at the same time the maximum time in which he visited will be minimal."

"If the number of spells exceeds limit..."

" power of each vertex is at most $$$3$$$"

"power" instead of "degree"; "peak", "pick", "top" instead of "vertex" — hard to find anything in E, as it's fixed now... Probably I'm not the only one who opens all the statements at the beginning of the contest, so believe me, fixing it during the round doesn't give much.

After the contest, I've read the first paragraphs, I like the one from E:

"The bees are strange because their honeycombs are pentagonal." Huh? What does it mean? Just a story, or should I care about it? Maybe the graphs are planar? Inequality from the input section is close to the planarity one: $$$m \leq 3n$$$. So? No, "powers" are at most $$$3$$$, so so somebody just wrote $$$m \leq 3n$$$ instead of $$$m \leq \frac{3n}{2}$$$...

About A: I don't see anything incorrect, but who let this statement appear as A?

An explanation for those who don't understand "pick", "peak" and "top". For people from Poland it's rather easy: vertex has some translation to Polish (wierzchołek) which also means the same as the top (of the hill for example) or peak, but of course, the meaning is very different. This also suggests that somebody has used google translate here. Russian is a bit similar to Polish, so...

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

    "peak" and "vertex" indeed both translate to "wierzchołek", but it never crossed my mind to associate these two with each other, so it by far was not clear to me, that "peak" means "vertex" :P. And "pick" does not mean "wierzchołek" in any way. P___ pasted initial statement of E (thanks!) above, and "peak", "top", "pick" and "vertex" have all been used alternately. There is no way that a person decides to keep using four different words for one thing. It is clearly produced by Google Translate. Or by a very very poor writer. And has not been proof-read by anybody. isaf27 any comment on this? And please remember, many people open statements at the beginning of each contest to ensure they can access them in case of any CF outage, so silent corrections during the round don't fix the problem.

    And raise your hand if after first reading it was clear to you what "there is a road of n lines." means xDD. And to top it off, followed by a beautiful "This road is not always can be crossed in one green light."

    I make a petition to make this round unrated for English speakers (ok, this is not serious suggestion, but you get the point).

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

      Man, antontrygubO_o wasn't the coordinator for this round.

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

        Whoops... Thanks, I will correct this.

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

      Yes, I'm sorry about the bad statements.

      Actually, they were translated by one friend of authors. The bad thing was, that he doesn't good at mathematical terminology. So, that strange things could be in the statements.

      There were more such thinks, I tried to correct them all, but some of them I missed (I don't know how I missed "power" and etc).

      My steps to avoid such things later:

      1) I will spend more time checking the statements.

      2) I will try to make them shorter and more clear

      3) I will ask for help from the English-speaking people.

      Sorry again.

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

        "Mathematical terminology" was definitely not the only problem with the statements, as "This road is not always can be crossed in one green light" illustrates.

        Those are some good suggestions; I notice your own English is not very good, which is perfectly normal, but in this case it's especially important that you follow 3) and get someone whose English is good to review the English version of the statements.

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

        While we are at it, the Russian statements could also use some fixing. Usually the errors don't make a statement ambiguous, but still, grammar and spelling errors are a continuous distraction from solving problems, and a bad example for the community.

        A few examples from today's problems:

        A: "...могла ли она получится в результате работы генератора." It's even correct in the next paragraph, "...могла ли получиться..."

        B, flavor text: "чтобы предложить ей стать парой.", "предлагает быть им вместе". Doesn't sound like Russian. Looks more like a too direct translation from English. And in the latter phrase, the order of words in the English version is also wrong.

        B: "если i-я палочка не горит и 1", "если включить ровно k палочек или −1": such complex sentences tend to lack a comma before "и" and "или", transforming the formal statement into something funny.

        All problems today: the em-dash signs look like they are written in TEX source as word ~--- word, which makes the left space longer than the right space. In that case, word~--- word or perhaps word "--- word would be better.

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

        I will be happy to contribute/help with the translation to English. How can I sign up for it?

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

        I suspect that friend of the authors used Google Translate.

        Testers can also help fix English. It's what I do sometimes when testing. Even for those who aren't very good at English, noting some mistakes helps and if there are many testers, the incremental improvements add up.

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

        By the way, do you have any idea if this scary creature was intended to speak broken English, or it was created by someone's friend who doesn't good at entomology? :)

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

    It's the same in most Slav languages. In Russian, vertex is вершина, and in Slovak it's vrchol — both have the same basic meanings as your example.

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

I have tried problem A during the contest but i didn't pass even the pretests. Here is the submission i got WA with during the contest: First try Here is the submision i got Ac after contest: Second try

The idea of the first try is to check if some i inside the interval [a-b,a+b] times n is inside the interval [c-d,c+d].

The idea of the second try is actually just the reverse. Check if some i inside [c-d,c+d] divide by n is inside the interval [a-b,a+b]. Why the second try works and the first one does not?

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

    Check if [(a - b) * n, (a + b) * n] intersects with [c - d, c + d].

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

      But this solution is actually very similar to me first try. Thank you.

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

        very similar != correct

        The intuition is that the minimum possible answer is n * ( a — b ) and the maximum possible answer is n * (a + b). And you can make any answer between min, max by adjusting. In your code, I'm not sure what the logic is.

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

          I see what you mean. In my code i tried to bruteforce every number in the interval [a-b,a+b] , but know i see that sometimes we my need 13+13+13+12 to make the sum fit into the interval [c-d,c+d], but my code only takes into consideration cases where we need only: 13+13+13+13 ( only equal numbers ) . Thank you.

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

            Lol mate, your solution is actually wrong and passes pretests by sheer luck. Sorry to ask, but how can I hack a solution in Codeforces (new member)?

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

              It actually did not even pass the pretests.

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

    That's because all weights do not have to be the same. When you try to find an integer from a-b to a+b, you assume all the grains to be identical. You are ruling out the possibility of some having a different weight, and hence a floating point average weight.

    So, when you do the reverse, that is division, you are also considering the fractions.

    Example: In one of the samples, you can see there is 2, 2, 3. You can't take one integer value for that!

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

      Exactly the second is correct because it also takes floating point into consideration. Thank you. This silly mistake made me lose a lot of rating today.

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

Can anybody help to understand the problem Div2 C, i still cant understand it :( Specially these paras:

  1. For all j from 1 to n, we calculate rj — the minimum index such that j≤rj≤n, and the position rj is not yet occupied in the permutation. If there are no such positions, then we assume that the value of rj is not defined.

2.For all t from 1 to n, we calculate countt — the number of positions 1≤j≤n such that rj is defined and rj=t.

  1. Consider the positions that are still not taken up by permutation and among those we consider the positions for which the value in the count array is maximum.

  2. The generator selects one of these positions for the number i. The generator can choose any position.

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

    The same happened to me. Understood after reading it for maybe 15 minutes...

    PROBLEM STATEMENT :

    Let me explain you
    1 > We have to check if the given permutation array is possible to generate by using the generator algorithm or not.
    2 > Understanding the algorithm :
    Step-0> Initially let perm be an array which we are creating to match it with input. Initially perm = [#,#,#......#] (# denotes free space)

    Step-1> For every position x [1...n] calculate an array called r which will have next immediate position available in our perm considering x itself.
    Let's say perm=[6,#,#,4,2,#] so our r = [2,2,3,6,6,6]
    Another example perm=[#,#,#,4,2,1] so our r=[1,2,3,#,#,#] because for last three positions we don't have any valid position to allocate.

    Step-2> Generate an array call count where for every i [1..n] it stores the frequency of i in array r.

    For above r = [1,2,3,#,#,#] , count = [1,1,1,0,0]
    For another example, let perm = [#,2,#,1], so r = [1,3,3,#], based on which we will make count=[1,0,2,0]

    Step-3> Now allocate an number to position who have maximum count in array count, if there are more than one maximum in count then choose any position you want(Here we will choose position according to input array).

    As for example let perm = [#,2,#,1], so r = [1,3,3,#], based on which we will make count=[1,0,2,0], here position 3 has maximum count in array count having count as 2. So we have to forcibily choose position 3.

    All those above step-1 to step-3 are just a process for only one iteration.
    So whole algorithm would be,
    initialize perm with free space
    for every number in [1 ... n] {
         generate an array r (our step-1)
         generate an array count (our step-2)
         allocate number to position in perm who has maximum count (our step-3)
    }
    check if the generated permutation is same as our input array

    EXAMPLE

    ip_arr = [2,3,4,5,1]
    perm = [#,#,#,#,#,#]
    for number=1:
         r = [1,2,3,4,5], count=[1,2,3,4,5], perm=[#,#,#,#,#]
         We can choose any postion we want to allocate 1 in perm bcoz every count is maximum,
        we will choose here 5 as 1 is in the position 5 in ip_arr
    for number=2:
         r = [1,2,3,4,#], count=[1,1,1,1,0], perm=[#,#,#,#,1]
         For allocating 2 we can choose any position from 1 to 4 but not 5 as it has lowest count,     
    we choose position 1
    for number=3:
         r = [2,2,3,4,#], count=[0,2,1,1,0], perm=[2,#,#,#,1]
         Now here we are forced to choose position 2 as it has maximum count,    
    so 3 is allocated to perm[2]
    for number=4:
         r = [3,3,3,4,#], count=[0,0,2,1,0], perm=[2,3,#,#,1]
         Again we are forced to choose perm[3]
    for number=5:
         r = [4,4,4,4,#], count=[0,0,0,1,0], perm=[2,3,4,#,1]
         We are now forced to choose perm[4] for number

    SOLUTION

    Observation to make is that when an lower number occurs in array it has to lead consecutive numbers,
    In test case 1: [2,3,4,5,1] 2 has to lead with 3, 3 has to lead with 4, 4 has to lead with 5, 1 has no one to lead
    In test case 3: [4,2,3,1] 1 does have any one to lead, 2 has to lead 3, 4 does not have to lead
    Eg. [4,5,6,1,2,3] 4->5->6, 1->2->3
    Wrong test case : [1,5,2,4,3] here 1 should have 2 next ot it
    Wrong test case : [1,3,2] here 1 should have 2 next ot it
    Wrong test case : [4,6,5,1,2,3] here 4 should have 5 next to it

    Implement it and you will get Accepted...
    I apolozize if i made it hard for you...have a good codeforces journey :)

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

      I was thinking about r and count array all the time, i did not think about permutation array that is why i could not able to build/relate r array. Now, it is clear.Thanks buddy!!

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

        Always available for help buddy. Your welcome

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

      You explained it way better than the actual problem statement I thank you for that

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

        It was a nightmare reading that statement at the time of the contest... You're welcome

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

split the background story with the actual question with a meme, pls. It makes no sense reading long story during contest.

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

Div1 C, Div2 E problem. I don't know reason that I get WA. Are there anyone who help me?

I used dynamic programming.

I used -2 to block from cycle.

I used 1000000000000ll to block from overflow.

Sorry, my pool English. But if you help me, I would really appreciate it.

https://codeforces.net/contest/1341/submission/77862656

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

    Interesting solution. I do not believe it is wrong, so I write some random tests and find a case:

    20 15

    0 1 2 3 4 6 9 10 11 14 15 16 18 19 20

    8 0

    Now I am debugging it. If you find out why, please let me know.

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

      I realize that dynamic programming can't solve cycle problem perfectly.

      Let assume that below sentence

      • There are problems(p1, p2, p3, p4, p5).

      • p1 has two subproblem (p2 and p3).

      • p2 has two subproblem (p4 and p5).

      • p3 is simple problem and has valid answer(cache value > 0).

      • p4 has two subproblem (p5 and p1). Here is a cycle.

      • p5 is simple problem and has invalid answer(cache value = -2, can't arrive target position)

      • If a problem has a subproblem which has valid answer, this problem has valid answer. If a problem has only subproblems which has invalid answer, this problem has invalid answer.

      When we try solve p1, recursive function try to solving p2, p3.

      - When we try solve p2, recursive function try to solving p4, p5.

      -- When we try solve p4, recursive function try to solving p5, p1

      • p5 has invalid answer and p1 is cycle. so p4's answer is -2.

      - now p4's and p5's answer is -2. So p2's answer become -2. And this value will be saved in cache.

      p2 has invalid answer. But p3 has valid answer. So p1 has valid answer.

      Now solving process of p1 is over. p1 has valid answer. But now assume we have to solve p2.

      • p2's answer saved in cache. p2 has invalid answer(value is -2). But it is wrong answer. Because p1 is subproblem of p4 and p4 is subproblem of p2. p1 has valid answer, so p4 has valid answer and p2 has valid answer. So I think caching answer to solve cycle problems is wrong method.

      PS : Sorry for my poor English. I am practicing English speaking and writing. I want to share many ideas of problem solving with other people. Good luck to me :)

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

        Good explanation! I think this is the problem that memorized dfs (dp) can not solve but bfs can.

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

Though problems were nice but statements were unnecessarily twisted!

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

I just downvoted your contest.

FAQ

What does this mean? The amount of contribution on your blog and maybe codeforces account has decreased by one.

Why did you do this? There are several reasons I may deem a blog to be unworthy of positive contribution. These include, but are not limited to:

Rudeness towards me,

Making a bad contest,

Sarcasm not correctly flagged with italic font,

Giving me negative delta.

Am I banned from the Codeforces? No — not yet. But you should refrain from making contests like this in the future. Otherwise I will be forced to issue an additional downvote, which may put your commenting and posting privileges in jeopardy.

I don't believe my comment deserved a downvote. Can you un-downvote it? Sure, mistakes happen. But only in exceedingly rare circumstances will I undo a downvote. If you would like to issue an appeal, shoot me a private message explaining what I got wrong. I tend to respond to Codeforces PMs within several minutes. Do note, however, that over 99.9% of downvote appeals are rejected, and yours is likely no exception.

How can I prevent this from happening in the future? Accept the downvote and move on. But learn from this mistake: your behavior will not be tolerated on CodeForces.com. I will continue to issue downvotes until you improve your conduct. Remember: Codeforces is privilege, not a right.

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

    Stop whining and enjoy the contest already, it has some beautiful problems.

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

    It's my first codeforces round (but I did several problems for other Olympiads). I made a lot of conclusions and next time I hope that there will be no such problems. Sorry(

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

      No problem man!! It was a good contest and high quality of problems were there...I appreciate you!

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

When will the editorial come out? It hasn't come out yet.

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

And there are up to 11 testers for this round smh.

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

I was the one who deregistered ~30 mins before the start of round.

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

Thank you for the amazing round. This round is very special for me. For the first time ever I can solve almost 5 problems and I can feel being in top 10 before system test.

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

I got a strange issue, My same code failed when I used 64 bit C++ but passed when submitted using normal c++ 17. Can anyone explain why? Fortunately, this did not happen during the contest. Failed Passed

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

    Perhap that's due to an undefined behavior on Ln 24 & Ln 35 :

    if(arr[i] > arr[i-1] && arr[i] > arr[i+1])

    When $$$i=n-1$$$ , this can slightly cause a UB.

    Please try to enlarge the size of arr and resubmit it. I think then it will be all right.

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

so long problem statements dude, work on it. It was not at all fun or clear.

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

How to implement the dp of div2D. It looked really hard for me to implement.

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

I'm feeling real bad :(. How can I debug my code when it's just one digit away from the answer :)

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

I would like to point out few points regarding this contest please read this carefully whoever has come across similar problems thanks for reading it :-

  1. I wrote $$$n^2$$$ * $$$t$$$ solution it passed in Div2A and failed main cases weakest pre cases testers even failed to check these type of solutions.

  2. I struggled in problem Div2B for 40 min and was super confused in the language with poor correlation of story and what actually the problem was asking for it seemed I was solving an April Fool's Problem.

  3. Finally I chocked at Div2C for about 1 — 1.5 hours just to understand the problem while never being able to code the problem actually.

  4. I was having doubt on my comprehensive skills at that point of time. Meanwhile I saw many of Div2D problems failing main cases since brute force solution was allowed to pass pretests which is horrible in itself.

  5. I respect Codeforces because it is great for learning but I would request my fellow competitve coders to discourage this type of contests making with some random red and yellow by heavily downvoting, guys. Please make standard question statements which is grammatically correct not English mixed with Russian. P.S not hate for Russian language though but mixing doesn't seems pleasing.

  6. Please don't do that again don't make contests at high frequency. It would be just nice if contests are of quality for which Codeforces is well known I saw some of previous 300+ rounds I literally had tears in my eyes that is what quality is. Please don't ruin this reputation with some nonsense rounds with absolute absurdity

If you find this offensive or bad feel free to downvote also if you find it relevant don't forget to hit the upvote button. Have a Good Day

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

    Bro, You didn't even submit a single solution. Also, a problem comprises of two parts- the ability to understand the actual problem and then finding a solution for that. Not to boast but I found the solutions for Div2 B and C quite simple so I guess the author I_love_myself had to make the problem statements interesting.

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

      We have not tested the English statements.... It was a huge mistake. It will not happen in the following times.

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

        Yeah The problem statements were too long but don't judge the problems by that ... Problems were really good with a balanced contest ... Mistakes happen by everyone !!

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

It seems the tests for div2 A problem are not correct. My solution could not pass these tests but I consider it as correct. Most contestants use solution based on algorithm like checking just n*(a-b) and n*(a+b) against c-d and c+d. And the system considers these solutions like successful ones. For example, p=n*(a-b) q=n*(a+b) r=c-d s=c+d f=0 if(p>s or q<r): f=1 if(f==1): print("NO") else: print("YES") Check this algorithm on such data like n = 10, a = 5, b = 1, c = 55, d = 1 and you find this algorithm incorrect. (p=40, q=60, r=54, s=56 => f=0 => Yes). I ask testers to verify their tests or to request author for problem reformulation.

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

    Some of people wrong in here. for all $$$i$$$ and $$$j$$$, $$$1\leq i,j\leq n$$$ $$$i$$$ and $$$j$$$ different, it shouldn't be $$$x_i = x_j$$$. In other word all $$$x_i$$$ shouldn't be same

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

Problem Div1D was very cool. Thanks for a nice contest).

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

can some explain what problem Div2 D wants to say ? I do not get the problem statement .

What i have understood till now : example case 1 :

1 7
0000000

We can get maximum 8 because we can turn on 7 sticks .

Test 3 :
3 5
0100001
1001001
1010011

Why answer is -1 ? for example , first string itself has 5 zero , and we can fill them .

Also i did not got few more things in problem statement , like "Number that can burn" , "k sticks break .........turn on exactly k sticks" .

Please some one explain the problem.

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

    You have to change exactly k zeros to ones, such that all strings correspond to valid numbers from 0 to 9. If it is possible, you have to maximise final number.

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

      yeah , so in string "0100001" , i can change 5 zeros to one and i get "1111111" but -1 in statement ?

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

        After all the sticks are used, all the strings should be a digit (0-9). Here, the second and third strings don't form a digit, we have to add sticks there also.

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

when will the editorial be published??

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

I think the time limit in Div2D was too tight. I used a recursive dp solution with memoization, which had time complexity of O(n*k), and the time limit was exceeded. Had to convert it to an iterative solution to get it accepted.

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

    I had it accepted using memoization, then carry the string in function was giving tle.

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

I don't understand the mistake in my code (Div2 Prob D). Can anyone help me out here. Even the test case for which its failing looks similar. It don't show for which digit its failing. My Submission 77853885

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

The stories were very weird. I liked it!

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



#include<bits/stdc++.h>
using namespace std;

                            
							 /* ----------------------------- START of Template ---------------*/
#define ll long long int
#define FOR(x,to) for(x=0;x<(to);x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(ll i=a;i<b;++i)
#define repd(i,a,b) for(ll i=a;i>=b;--i)
#define mp make_pair
#define hell 1000000007
#define vvll vector<vector<long long int> >
#define vll vector<long long int>
                       

					   /* ----------------------          End Of Template --------------------------------*/


ll kn;
ll solve(ll rem,ll index,vector<vector<ll> > &val,vector<vector<ll> > &dp){
	ll n=kn;
	if(index==n){
		if(rem==0)return 0;
		else return -1;
	}
	if(rem<0)return -1;
	ll i;
	if(dp[index][rem]!=INT_MIN)return dp[index][rem];
	ll ans=-1;
	for(i=9;i>=0;i--){
		if(val[index][i]!=-1&&val[index][i]<=rem){
			ll g=i*pow(10,n-index-1)+solve(rem-val[index][i],index+1,val,dp);
			if(g>=i*pow(10,n-index-1)){
			  return dp[index][rem]=g;
			}
		}
	}
	return dp[index][i]=ans;
}


// this finds changes required to make s into t
ll findmin(string s,string t){
	ll cnt=0,i;
	for(i=0;i<s.size();i++){
		if(s[i]=='0'&&t[i]=='1')cnt++;
		else if(t[i]=='0'&&s[i]=='1'){
			return -1;
		}
	}
	return cnt;
}

ll findans(){
	ll n,k,i,j;
	cin>>n>>k;
	vector<string> v2(n),v={"1110111", "0010010", "1011101", "1011011", "0111010", "1101011", "1101111", "1010010", "1111111", "1111011"};
	kn=n;
	for(i=0;i<n;i++){
		cin>>v2[i];
	}
	vector<vector<ll> > dp(n,vector<ll>(k+1,INT_MIN));
	vector<vector<ll> > val(n,vector<ll>(10));
	for(i=0;i<n;i++){
		for(j=0;j<10;j++){
			val[i][j]=findmin(v2[i],v[j]);
		}
	}
	ll ans=solve(k,0,val,dp);
	cout<<ans<<endl;
	return 0;
}

int main(){
	ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	ll t,i;
//	cin>>t;
t=1;
	for(i=0;i<t;i++){
		findans();
	}
return 0;
}


this is code for D..Can someone tell me why this code is giving runtime error on testcase 3 but works in compiler?   Ignore the part where leading zeros need to be printed
→ Reply
»
5 years ago, # |
← Rev. 7   Vote: I like it +2 Vote: I do not like it

Div2 D. I get it! Nastya is a cyborg, and Denis punched her in her seven-segment display (засветил ей в табло) trying to persuade her to date him.

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

I tried to submit a few hacks (problem B) after the contest just now, but they all get "Unexpected Verdict". I'm pretty sure the test is perfectly valid. Anyone know why this is?

2 2
1110111
1011101

EDIT lol, some searching around suggests this means the checker crashes?

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

So, my solution worked 998ms out of 1 second TL?

ಠ_ಠ

What was the meaning of that TL? I really don't understand how it can be lower than 2 seconds in such problems. So that non-C++ users hate you, and C++ users gamble? :) Even in C++, my solution TLs on the older compilers.

To be clear, I know that priority queue was not required in this problem, and without it my solution passes in ~150ms. But I still think TL is unnecessarily tight, and pretests also don't fail you on that.

Anyways, problems were pretty good, thanks to the authors, and looking forward to your next contests!

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

Can anyone help why my bottom-up dp approach for Div2-D is giving TLE.
77895150

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

How do I know if my Div2D submission is correct (as system tests were weak based on some comments above)? 77847563

EDIT: Sorry, just realized I can view uphacking testcases as well as expected output.

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

thanks MikeMirzayanov for such amazing contest I am very like question C he is awesome

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

Story of Nastya and a Simp.

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

fucking network :(

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

If codeforces cannot afford to hire someone to translate problem statements into decent English, I can agree to do it for a contest named in my honor.

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

    To all of you rushing for the downvote button — lighten up, the above was a joke. :)

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

When are we going to get editorial.

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

Wish for a better contest next time.

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

    I will rather prefer a short and formal statements over reading a novel in the contest.

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

      A novel of questionable artistic value, I might add. But, on the other hand, those novels come with an extra half hour. :)

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

What is the problem with my solution code, I am getting TLE. My complexity is O(10nk). Can anyone please help? Thanks

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

I am trying to solve Div2D/Div1B question. I have a DP solution that is [n+1][k+1][10] for O(10*n*k). I TLE on test case #7, but it would seem that this solution (as others have also done it this way) should work within the time limit. Is this not efficient enough, or am I doing something wrong? Additionally, I am not great with PD and I don't understand the [n][k] DP solution at all, so any information on that would also be great!

EDIT: I changed DP solution to [n][k] but TLE on #22. 78075008

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

Thanks for the nice round <3

→ Reply