Блог пользователя ch_egor

Автор ch_egor, 5 лет назад, По-русски

Всем привет!

В воскресенье в Москве пройдет XVII Московская командная олимпиада — командное соревнование для школьников, проходящее в Москве как отборочное соревнование на ВКОШП. Над туром работала Московская методическая комиссия, известная вам также по Открытой олимпиаде школьников по программированию, Московской олимпиаде для 6-9 классов и олимпиаде Мегаполисов (раунды 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567, 583).

Раунд состоится в 20.10.2019 12:05 (Московское время) и продлится 2 часа. В каждом дивизионе будет предложено по 6 задач.

Задачи соревнования подготовлены wrg0ababd, vintage_Vlad_Makeev, DebNatkh, grphil, voidmax, vintage_Vlad_Makeev, volcolac, Sehnsucht, isaf27, cdkrot, Flyrise, budalnik, platypus179, Endagorion под моим руководством, а также GlebsHP, meshanya, Endagorion, Zlobober и Андреевой Е. В.

За координацию раунда и перевод условий спасибо cdkrot, а так же MikeMirzayanov за системы codeforces и polygon, который использовался при подготовке задач этой олимпиады.

Всем удачи!

UPD1: Победители!

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

Разбор будет опубликован скоро.

UPD2: Разбор

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

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

Score distribution?

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

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

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

How many shared problems are there between div1 and div2?

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

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

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

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

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

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

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

        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 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

я (и многие школьники) будут очень благодарны, если вы отложите контест хотя бы на час.Много кто пишет всесиб

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

    а лучше на четыре часа — тогда участники мкошпа тоже будут благодарны

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

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

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

A big team of the problem setter!

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

Also a friendly time for Chinese!

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

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

Tonight I'm gonna sleep a lot :]

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

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

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

я не понял, чем отличаются дивизионы? по сложности или как? и они будут одновременно проводиться?

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

    Первый дивизион — более сложные задачи, и на него могут зарегистрироваться только пользователи с рейтингом от 1900. Чаще всего задачи в двух дивизионах пересекаются (поэтому они проводятся одновременно), но тогда, например, три самые сложные задачи во втором дивизионе — это три самые легкие в первом.

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

I hope I will become CM :)

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

Good Luck then

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

score distribution??

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

Hope to become Blue today. Good luck all!

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

Is the round rated?

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

score distribution ?

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

unbalanced contest.

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

About the order of difficulty......

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

Div1 C is the most frustrating problem ever made

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

    wth is pretest 4

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

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

      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 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

      maybe sth. like

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

        what should the answer to be for this instance

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          51 41 31 21 11 
          
        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится +8 Проголосовать: не нравится

          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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

in Div2-C, what is pretest 7 ?

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

    what is the idea of C ?

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

      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 лет назад, # |
  Проголосовать: нравится +43 Проголосовать: не нравится

difficulty balance be like

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

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

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

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

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

Div 2 D, what would be the correct way to compute a string's beauty? I've tried finding the longest suffix where the number of opened parenthesis is greater than the number of closed parenthesis, cycle the string so that suffix becomes a prefix, and then find out the number of concatenations the string was made with (as long as it is a valid string).

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

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

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

This is what you call a truly imbalanced contest!

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

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 лет назад, # ^ |
      Проголосовать: нравится +79 Проголосовать: не нравится

    OMG ! Div1 C = English test :/

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

    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 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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 лет назад, # ^ |
        Проголосовать: нравится +15 Проголосовать: не нравится

      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.net/contest/1239/submission/62998813

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

        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 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    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 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You mean div2 D

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

    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 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

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

    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 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

how to solve div2 c ??

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

    Bruteforce + finding pattern for answer

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

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

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

      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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Did anyone try hard to push cubic solution for Div2D1?

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

HOW TO SOLVE DIV 2C?

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

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

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

    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 лет назад, # |
  Проголосовать: нравится +194 Проголосовать: не нравится

You forgot to sort problems

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

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

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

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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

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

Can I meet Balanced Problem Set ever??

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

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

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

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 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

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

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

      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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

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

    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 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

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

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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

Hardest div1A for me, back to div2..

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

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

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

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

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

a random picture

A random picture

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

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 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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

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

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

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

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 лет назад, # |
  Проголосовать: нравится +61 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

в D div1 слишком большие ограничения, на java нужно пихать

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

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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Why do cubic solutions pass on D1?

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

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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Как-то в последних трёх (или даже четырёх) контестах подряд, где я участвовал на codeforces, баллы за задачи не соответствуют их сложности, и за более простые дают больше баллов.

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

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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how can we prove the solution for div2C ?

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

    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 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

.

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

TIL that seats can be busy.

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

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

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

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

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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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