ch_egor's blog

By ch_egor, 4 weeks 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, grikukan, DebNatkh, grphil, voidmax, V--gLaSsH0ldEr593--V, volcolac, Sehnsucht, isaf27, _kun_, Flyrise, Nebuchadnezzar, platypus179, Endagorion under my supervision with great help of GlebsHP, _meshanya_, Endagorion, Zlobober and Helen Andreeva.

Thanks to _kun_ 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. tlwpdus
  2. rhrnald
  3. ainta
  4. dorijanlendvaj
  5. wxhtxdy
  6. maroonrk
  7. djq_cpp
  8. QWE_QWE
  9. Marcin_smu
  10. 300iq

Div. 2:

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

Editorial will be published soon.

UPD2: Editorial

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Score distribution?

»
4 weeks 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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How many shared problems are there between div1 and div2?

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

    Each division will have 6 problems.

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

      Question was about shared problems

  • »
    »
    4 weeks 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.

»
4 weeks 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 :)

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

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

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

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

      • »
        »
        »
        »
        4 weeks 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 :)

        • »
          »
          »
          »
          »
          4 weeks 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:(

          • »
            »
            »
            »
            »
            »
            4 weeks 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

»
4 weeks ago, # |
  Vote: I like it -55 Vote: I do not like it

So where is div3 for guys who cant solve div2.A like me? :D

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

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

»
4 weeks ago, # |
  Vote: I like it +26 Vote: I do not like it

A big team of the problem setter!

»
4 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

Also a friendly time for Chinese!

»
4 weeks ago, # |
  Vote: I like it +148 Vote: I do not like it

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

Great

»
4 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Tonight I'm gonna sleep a lot :]

»
4 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

Lol, why are grikukan and V--gLaSsH0ldEr593--V both mentioned? Aren't they the same person?

»
4 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

I hope I will become CM :)

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

Good Luck then

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

score distribution??

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Hope to become Blue today. Good luck all!

»
4 weeks ago, # |
  Vote: I like it -42 Vote: I do not like it

Is the round rated?

»
4 weeks ago, # |
  Vote: I like it -18 Vote: I do not like it

score distribution ?

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

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

»
4 weeks ago, # |
  Vote: I like it +48 Vote: I do not like it

About the order of difficulty......

»
4 weeks ago, # |
  Vote: I like it +97 Vote: I do not like it

Div1 C is the most frustrating problem ever made

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

    wth is pretest 4

    • »
      »
      »
      4 weeks 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).

    • »
      »
      »
      4 weeks 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 :/)

      • »
        »
        »
        »
        4 weeks 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.

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

      maybe sth. like

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

        what should the answer to be for this instance

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          51 41 31 21 11 
          
        • »
          »
          »
          »
          »
          4 weeks 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

  • »
    »
    4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

in Div2-C, what is pretest 7 ?

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

    n = 2; m = 5.

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

    what is the idea of C ?

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

      Fibonacci

    • »
      »
      »
      3 weeks 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 ;)

»
4 weeks ago, # |
  Vote: I like it +43 Vote: I do not like it

difficulty balance be like

»
4 weeks 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.

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

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

    • »
      »
      »
      4 weeks 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.

»
4 weeks 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.

»
4 weeks 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......

»
4 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

This is what you call a truly imbalanced contest!

»
4 weeks 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 :/

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

    OMG ! Div1 C = English test :/

  • »
    »
    4 weeks 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.

  • »
    »
    4 weeks 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.

    • »
      »
      »
      4 weeks 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.

    • »
      »
      »
      4 weeks 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://codeforces.com/contest/1239/submission/62998813

      • »
        »
        »
        »
        4 weeks 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.

  • »
    »
    4 weeks 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

»
4 weeks 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.

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

    You mean div2 D

  • »
    »
    4 weeks 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}$$$.

  • »
    »
    4 weeks 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?

    • »
      »
      »
      4 weeks 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!

  • »
    »
    4 weeks 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)

  • »
    »
    4 weeks 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)

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The first problem is poorly explained.

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

how to solve div2 c ??

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

    Bruteforce + finding pattern for answer

  • »
    »
    4 weeks 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.

    • »
      »
      »
      4 weeks 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...

    • »
      »
      »
      4 weeks 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?

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

      please could you explain the idea behind it

  • »
    »
    4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Did anyone try hard to push cubic solution for Div2D1?

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

    My solution is cubic, it passes pretests

  • »
    »
    4 weeks 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.

    • »
      »
      »
      4 weeks 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.

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

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

HOW TO SOLVE DIV 2C?

  • »
    »
    4 weeks 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

  • »
    »
    4 weeks 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!

»
4 weeks ago, # |
  Vote: I like it +194 Vote: I do not like it

You forgot to sort problems

»
4 weeks ago, # |
  Vote: I like it +30 Vote: I do not like it

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

»
4 weeks 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?

  • »
    »
    4 weeks 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.

  • »
    »
    4 weeks 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

»
4 weeks ago, # |
  Vote: I like it +27 Vote: I do not like it

Can I meet Balanced Problem Set ever??

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
4 weeks 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 ?

  • »
    »
    4 weeks 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.

    • »
      »
      »
      4 weeks 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.

    • »
      »
      »
      4 weeks 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 >_<

  • »
    »
    4 weeks 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".

»
4 weeks 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 -_-.

»
4 weeks 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. :(

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

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +104 Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it +23 Vote: I do not like it

Hardest div1A for me, back to div2..

»
4 weeks 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

»
4 weeks 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

»
4 weeks ago, # |
  Vote: I like it +240 Vote: I do not like it

a random picture

A random picture

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

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

    • »
      »
      »
      4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

setter should not have made div2d only 750 points. It was more hard than a,b,c combined. I earlier thought bf with n4 would pass but it didn't. then i realised that its not as easy as it is mentioned.

ch_egor

»
4 weeks 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 :)

»
4 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

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

»
4 weeks 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

»
4 weeks 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!

»
4 weeks 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?

»
4 weeks 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.

  • »
    »
    4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Why do cubic solutions pass on D1?

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

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

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

      My whole life was a lie.

      • »
        »
        »
        »
        4 weeks 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 :(

»
4 weeks 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?

  • »
    »
    4 weeks 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.

  • »
    »
    4 weeks 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

»
4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how can we prove the solution for div2C ?

  • »
    »
    4 weeks 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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain the soluition of F?? Why SCC is used in this question.. Thanks in advance

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

waiting for editorials: )

»
4 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

TIL that seats can be busy.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Another Mathforces.

»
4 weeks 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.

  • »
    »
    4 weeks 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.

»
4 weeks 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?

  • »
    »
    3 weeks 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.

  • »
    »
    3 weeks 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.

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

    The same question =))

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

what is the idea behind Div2 C? Didn't get the editorial.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

why am I getting a TLE here: https://codeforces.com/contest/1248/submission/63239483 the Algo is same as the editorial.