ch_egor's blog

By ch_egor, 5 years ago, translation, In English

Hi everybody,

This Sunday there will be a XVII Moscow Team Olympiad, high school students competition based in Moscow that is an elimination contest for All-Russian Team Olympiad. This contest is prepared by Moscow Olympiad Scientific Committee that you may know by Moscow Open Olympiad, Moscow Olympiad for Young Students and Metropolises Olympiad (rounds 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567, 583).

Round will be held at Oct/20/2019 12:05 (Moscow time) and will last for 2 hours. Each division will have 6 problems.

Problems are prepared by wrg0ababd, vintage_Vlad_Makeev, DebNatkh, grphil, voidmax, vintage_Vlad_Makeev, volcolac, Sehnsucht, isaf27, cdkrot, Flyrise, budalnik, platypus179, Endagorion under my supervision with great help of GlebsHP, meshanya, Endagorion, Zlobober and Helen Andreeva.

Thanks to cdkrot for the round coordination and statement translation, and also thanks for MikeMirzayanov for systems codeforces and polygon, which was used to prepare problems of this olympiad.

Good luck everybody!

UPD1: Winners!

Div. 1:

  1. TLEwpdus
  2. rhrnald
  3. ainta
  4. dorijanlendvaj
  5. jqdai0815
  6. maroonrk
  7. djq_cpp
  8. kort0n
  9. Marcin_smu
  10. 300iq

Div. 2:

  1. lolkekaidarbek
  2. qdd
  3. mathusalen
  4. conan1412yang99
  5. fauzdar65
  6. DeepThought42
  7. mikeleven
  8. AnnieCai
  9. liuandi6
  10. jyf111

Editorial will be published soon.

UPD2: Editorial

Tags 594
  • Vote: I like it
  • +243
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Score distribution?

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

This is my first div 1 contest! UPD. Oh nope, too hard. My div1 contest flew away

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

How many shared problems are there between div1 and div2?

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

    Each division will have 6 problems.

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

      Question was about shared problems

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

    Usually Div.2 C is the same as Div.1 A, so I think there will be four.

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

If my rating can increase 33 , I will be so happy XD Good luck everyone :)

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

    Wow, we have the same rating! Hope for the best results :)

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

      We failed together XD I believe we can do it soon:D

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

        Did you get positive rating? It's bad luck for us QQ

        I think that I will rest for some time, after taking a regional contest yesterday I'm a little tired to solve more problem

        Hope u can do it as fast as possible :)

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

          Wow..I think you should have a rest:D I will take part in a regional contest in Nanjing:) To be honest,I am nervous because I got a bad rank last regional contest:(

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

            Wish u a good luck and making the best performance! :) Yesterday was my first time traveling to the other city for a contest, actually not having a good outcome make me a little sad
            maybe I need some time to adjust myself...

            I'll take your advice, thanks. XD

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

Multiple contest in a Queue.. Thanks codeforces ...

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

A big team of the problem setter!

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

Also a friendly time for Chinese!

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

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

Tonight I'm gonna sleep a lot :]

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

Lol, why are vintage_Vlad_Makeev and vintage_Vlad_Makeev both mentioned? Aren't they the same person?

»
5 years ago, # |
  Vote: I like it -6 Vote: I do not like it

I hope I will become CM :)

»
5 years ago, # |
Rev. 2   Vote: I like it -21 Vote: I do not like it

Good Luck then

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

score distribution??

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

Hope to become Blue today. Good luck all!

»
5 years ago, # |
  Vote: I like it -42 Vote: I do not like it

Is the round rated?

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

score distribution ?

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

    You'll find out in a minute, why so impatient?

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

About the order of difficulty......

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

Div1 C is the most frustrating problem ever made

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

    wth is pretest 4

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

      Pretest 4 (i think) is a situation when there actually can be a queue before the tank. Once you understand this situation, you understand the pretest.

      (idk, maybe it's obvious, but I understood this only after like an hour of solving).

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

      You need to read the statement multiple times — there is a queue involved too.

      (Unfortunately, I made an implementation bug somewhere probably and failed on pretest 10, back to CM for me :/)

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

        After two wrong submissions, I realized oh queue is also involved, then I got what is wrong with my code, but didn't get the time to implement it.

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

      maybe sth. like

      5 10
      5 4 3 2 1
      
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        what should the answer to be for this instance

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          51 41 31 21 11 
          
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          At 1-th minute, the fifth people go and take water. But at the 2-th minute, the fourth people want to take some water, and find that all people before him is sitting there, so he will go and wait behind the fifth person.

          So actually there is also a queue in the place where the water is taken.

          But during contest, I didn't realize there is a queue, and I checked my code for an hour, thinking there is nothing wrong. LOL

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

    I felt this way about div1 B. Not sure if my solution or implementation was wrong but having to reconstruct made it much more work.

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

in Div2-C, what is pretest 7 ?

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

    what is the idea of C ?

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

      find a few facts then you can use backtrack and dp to find the answer I thing tutorial is published and you can read it to find your answer Good Luck ;)

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

difficulty balance be like

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

The one, who came up with such a great problem as Div1B : you can go and prepare problems for yourself.

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

    how to solve easy version of it with n <= 500.

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

      brute force the two swapping positions and then count the number of satisfied cyclic shifts.

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

I think in every new round setter competes with the previous setters for setting more difficult problems.

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

So I think I made a <= 3 character bug for 2 consecutive rounds......

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

This is what you call a truly imbalanced contest!

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

Wow, B was really hard and annoying for a div1B. Does anyone have an easy solution?

I only realised with 2 minutes left that the queue-stuff from C's statement was actually relevant, since for example passenger 2 could get ready to get water at time 1, and passenger 1 at time 2, then passenger 1 sees no empty seats in front of him and goes to the queue. Would have been nice to have a sample that shows that this is possible :/

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

    OMG ! Div1 C = English test :/

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

    In case too many passengers will go for boiled water simultaneously, they will form a queue
    Ok, so there is a queue.

    Nobody likes to stand in a queue.
    Oh, so no queues?

    There is an unspoken rule, that in case at some moment several people can go to the tank, than only the leftmost of them will go to the tank, while all others will wait for the next moment.
    Alright, no queues it is.

    This is what I was thinking.

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

    I'm not sure if it's that hard as a solution, but it's easy to get lost looking for it. The quantity we're maximising is the number of minimum prefix sums. If we swap parentheses $$$i$$$ and $$$j$$$, prefix sums $$$i+1$$$ through $$$j$$$ change — either they increase by 2 or decrease by 2, depending on parenthesis $$$i$$$.

    Obviously, if we don't select all occurrences of the current minimum, the resulting minimum of all prefix sums can only decrease, by at most 2. If we select it, then the resulting minimum can only increase or decrease by at most 2 as well. We can now try all possibilities for the resulting minimum and "increase/decrease", since there are $$$O(1)$$$ of them.

    If we want minimum $$$m$$$ with "decrease", all prefix sums in the range $$$[i+1, j]$$$ must be at least $$$m+2$$$, at least one must be exactly $$$m+2$$$ and all prefix sums outside this range must be at least $$$m$$$. For a fixed $$$i$$$, we can choose the maximum $$$j$$$ such that the first condition holds, i.e. prefix sum $$$j+1$$$ is $$$m+1$$$, and check the other conditions. Since $$$m$$$ is fixed for all $$$i$$$, this runs in $$$O(N\log{N})$$$ and maybe even $$$O(N)$$$.

    If we want minimum $$$m$$$ with "increase", all prefix sums in the range $$$[i+1, j]$$$ must be at least $$$m-2$$$, at least one must be exactly $$$m-2$$$ and everything outside this range must be at least $$$m$$$. It can be solved in the same way.

    It needs more ideas, but they're not really that hard.

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

      My ideas were using a stack:

      • If we push the string on to a stack and keep popping the matched ones, we will be left with $$$..))((..$$$ Then you swap the first and last of the leftover on the stack.

      • Do above with string s[n-1]s[0..n-2]. (to tackle $$$(()())$$$ case)

      • Print max of the two as answer.

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

      You could further simplify it by assuming when we swap parenthesis $$$i$$$ and $$$j$$$, instead of the prefix sums $$$i+1$$$ through $$$j$$$ increasing by 2, the remaining prefix sums decrease by 2.

      Now, if the original minimum is $$$m$$$, then you just need to consider 2 cases, where the minimum $$$m'$$$ is $$$m$$$ or $$$m - 1$$$.

      The above simplification also reduces the search for the segment to $$$O(n)$$$, since for each case, you can just loop over the string and keep a count of elements exactly equal to $$$m' + 2$$$ and reset whenever you find an element $$$ < m' + 2 $$$

      Submission for reference: https://mirror.codeforces.com/contest/1239/submission/62998813

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

        I actually simplified by rotating the string so the minimum is $$$0$$$. Then we don't want to increase anything. Still, that's an extra idea and the shortest path to knowing you have a working solution is more along the lines of what I wrote — $$$O(1)$$$ cases and queries for range minimum.

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

    First note that any string that can become balanced with one swap, can be rotated to be balanced. So no need to waste the swap here; find the prefix with the minimum sum ( = 1, ) = -1 and move it to the end.

    If the string is still not balanced, the answer is 0.

    Otherwise we need to use the swap to maximize the number of balanced parts in the first level (...)(...)(...).

    There are two cases:

    • (()x()()y): swapping x and y will move the parts between them to level zero and will create one more part to the left, so this swap adds 3 to the base answer.

    • Swapping the two ends of any part in level 0 (...) will leave 1 + the number of parts between them. For example (()()) -> )()()( which is ()()().

    In a single pass with a stack, you can consider the two cases for all ends and maximize the answer: 63011541

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

Div 2 D, what would be a correct way to compute a string's beauty? I've tried finding the string's longest suffix where the number of opened parenthesis is greater than the number of closed parenthesis, cycle the string so that become a prefix, then find out the number of concatenations this new string is made with (0 if the string is not valid). Wrong answer on test 8.

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

    You mean div2 D

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

      Oh yeah, thanks mate

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

        Isn't the number of 0's in the prefix sum of a string equal to its beauty?

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

    I did finding and counting all such suffixes such that $$$N_{closed} - N_{opened}$$$ in the suffix is less or equal than $$$min(N_{opened} - N_{closed})$$$ on all prefixes. Also make sure that overall $$$N_{opened} = N_{closed}$$$.

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

    If the string contains an equal number of 1's and -1's, the beauty equals the number of minimum prefix sums. However I think what you described should work as well. Maybe there's a bug?

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

      Could be a bug, I'll wait to see the test it fails on and try debugging with it. Thank you for your explanation!

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

    Using stack and then while inserting least recently used opening bracket may be tracked and counter increased when it matched. (for D1, do for all n rotations)

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

    String's beauty is number of minimal balances, if balance of all string is 0; (Balance is number of '(' on prefix minus number of ')' on prefix)

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

how to solve div2 c ??

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

    Bruteforce + finding pattern for answer

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

    I sent $$$\big(m$$$-th Fibonacci number $$$+$$$ $$$n$$$-th Fibonacci number $$$- 1\big)\cdot 2$$$. No idea why.

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

      Wow, that's a very clever approach, and a valid one too i think according to dp states... With matrix exponentiation we could have even solved for very large n,m then...

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

      Was trying to make the product of Fibonaccis work. Can't prove why this works when n != 1 and/or m != 1. Any suggestions?

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

    Consider there is only 1 line. You can use a easy DP to get that there are $$$S$$$ ways to color the first line. Except ways $$$101010...$$$ and $$$010101...$$$ there are $$$S-2$$$ ways to color the line with surely $$$\ge$$$ one pair of $$$00$$$ or $$$11$$$.

    For these $$$S-2$$$ ways of coloring the first line ,because they contain substrings $$$00$$$ or $$$11$$$ ,there is excatly $$$1$$$ way to color the rest for each ways. So the contributions to the answer is just $$$S - 2$$$

    For $$$101010...$$$ and $$$010101...$$$ ,in the rest lines ,there is no way to color $$$00$$$ or $$$11$$$ in a line but maybe in a column. And you can use the same DP to solve it.

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

Did anyone try hard to push cubic solution for Div2D1?

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

    My solution is cubic, it passes pretests

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

    Isn't the intended complexity cubic? My cubic solution passed pretests in 529 ms.

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

      My cubic is TLE#8. Ok, maybe my solution isn't as cubic as it need to be.

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

    $$$O(n^3/2)$$$ will pass

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

HOW TO SOLVE DIV 2C?

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

    try to solve the problem for 1 * m table . then you can see that in only 2 cases second row isnt unique

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

    Try to make just 1 contiguous equal pair, you'll find that you cannot place any vertical contiguous equal pair if horizontal is present and vice versa, ie, the other one is alternate.Also a row or a column can only repeat at max 2 times in an assignment, and there are only 2 types of those, alternate, so I ran a dp of n*2*2, and another along column m*2*2, and just added their final states at n,m respectively.States were (position, current type of row(column), length of contiguous sequence till then). Also at the end remember to subtract 2 from answer so as to avoid the repetition of case when no contiguous blocks are equal.... Hope it helps!

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

You forgot to sort problems

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

Every contest seems to be highly unbalanced after the tourist balanced round

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

Hi,

Regarding Div2D, Can it be proved that a string with equal number of '(' and ')' can be made correct by a certain k-rotation?

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

    Yes, if you push given string on the stack, and pop matching ones, you will be left with something like $$$...)))(((...$$$ always, and then you can rotate the mid point to balance everything.

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

    Yes, you can pick a k-rotation, such that count of '(' minus count of ')' on prefix n-k is minimal

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

Can I meet Balanced Problem Set ever??

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

How to solve div2d easy in O(n3) time.

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

How to solve Div1 D/Div2 F? Does any greedy work for the case when the bipartite graph is completely connected , i.e., just 1 connected component ?

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

    Edges are actually directed so think of SCC. There's an answer iff there's more than 1 SCC.

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

      Ya got it, thanks. I wasn't considering directed edges and hence was always getting answer for more than 2 connected components and wasn't able to think how it works for just 1. But on scc the same logic works, just answer no for 1 scc.

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

      Damn, I was thinking of SCC number but for some reason I directed some edges in both directions >_<

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

    My solution is, given the input graph, you just need to create strongly connected components and then, if there is only one, output "NO".

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

I think I can get substantial increase in rating in the next round given the distance from my average rating -_-.

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

OMG!!!! problem C takes me over 1 hour,but D only 30 minutes.unluckily when I pass all the examples in problem D ,it's 3 minutes after the contest. :(

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

    Don't you mean D1? D1 is less points than C.

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

Strong pretest and no successful hacking attempt in div 1. Yeah!

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

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

Hardest div1A for me, back to div2..

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

Today I learned that Python has a preset recursion limit of 1000. Cost me Problem C lol

»
5 years ago, # |
Rev. 3   Vote: I like it +9 Vote: I do not like it

This round reminds me of the Codeforces Round 588 (Div. 2) on which the problem set was created by Radewoosh

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

a random picture

A random picture

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

    What's wrong with that, if B and C were both 1250?

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

      In fact D1D is also random, but it's not strictly a "random picture" discribed in D1A.

      I think the main reason is that D1D is 2000, if it's 1250, we'll have a random picture with 3 columns.

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

Great contest, fast testing (during and after). Fun problems that required more thinking than edge-cases and writing. Thank you all involved in writing, keep em coming :)

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

These days are crucial for contestants with poor math skills :|

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

It was the best round I had participated in from a long time

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

I believe today's contest (Div. 2) was awesome, for me personally at least, with less system test failure's and a good and simply code-able problem C.....Looking forward to such and even better contests in future on codeforces!

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

This round reminds me of Codeforces Round 543 (Div. 1, based on Technocup 2019 Final Round). How on earth is D worth more than B?

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

why is this submission got WA on pretest 4?

I thought passanger 1 gets the boiled water at 2000000009, because after the first person (idk which index, but seeing the result has suffix 9, it must be 9), every passanger already wanted to take the boiled water, but the leftmost (index=1) will be getting the boiled water first.

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

    Because when passenger 3 wants to cook their noodles, he checks the chairs left to them. In this case no one has left their seats so passenger 3 would definitely get their noodles cooked before passenger 1 does.

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

Why do cubic solutions pass on D1?

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

    500^3 == 1.25*1e8 It is well within time limit

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

      My whole life was a lie.

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

        Yes! despite getting to bruteforce solution I didn't submit cause of above calculation and given 1s time limit :(

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

Div 2 Problem E
Can someone justify why 3rd value in the answer is less than the 1st one?? Shouldn't it be greater?

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

    Because when passenger 3 wants to cook their noodles, he checks the chairs left to them. In this case no one has left their seats so passenger 3 would definitely get their noodles cooked before passenger 1 does.

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

    I have the same output like you ??? I don't know where i was wrong in reading the statement :V But i don't know why the answer can reach 1e10 when p<=1e9 and ti<=1e9 :V It doesn't make any sense ???? Pls explain too me .Tks you ans sorry for my poor English

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

There is a mistake in the statement of problem D. Instead of

"Cyclical shifts i and j are considered different, if i/=j"

it should be

"Cyclical shifts by i and j are considered different, if i/=j".

It can be deduced from the examples though.

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

how can we prove the solution for div2C ?

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

    If you filled the first row cells and first colm cells you will find that there is only one way to fill the remaining cells

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

.

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

TIL that seats can be busy.

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

I found these submissions: 62996146 62993334. It really looks like they were cheating.

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

    Codeforces plagiarism checker is really very bad that they can spot these same codes with some variables changed. Nice done buddy, I think admin must look into this once.

»
5 years ago, # |
Rev. 4   Vote: I like it +6 Vote: I do not like it

The tutorial of C said that it's a strip problem and the solution seems easy... But the question is what is a strip prolem... Am I retarted?

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

    You should look on case when n = 1. It will help to understand whole problem.

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

    It can be solve by easy dp.

    dp[i][j] — number of such coloring, if last j colors are equal.

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

    The same question =))

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

O(n) solution for div2.B is to use count sort ?