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

Автор SPatrik, история, 10 месяцев назад, По-английски,

Hello, Codeforces!

I am glad to invite you to take part in Codeforces Round #577 (Div 2), which will be held on Sunday, 4 August at 16:35 UTC.

You will be given 5 problems, one of them will have 2 subtasks and 2 hours to solve them.

The round will be rated for the second division.

Huge thanks to _kun_ and KAN for helping to prepare the round.

I would like to thank to 300iq, isaf27, V--gLaSsH0ldEr593--V, pllk, mohammedehab2002, tractor74.ru, Rox, opukittpceno_hhr for testing the round.

And thanks to MikeMirzayanov for the great codeforces and polygon platforms.

This is my first Codeforces round. Hope you will enjoy it.

Good luck and have fun!

UPD: The scoring distribution is: 500 — 1000 — 1500 — 2000 — (2000 + 1000)

UPD2: Editorial

UPD3: Congratulations to the winners:

Div2:

1: wwaynetuu

2: jerome_mei

3: satu0king

4: Yazmau

5: Tlatoani, 2-SAD, boba5551

Unofficial Div1:

1: neal

2: uwi

3: scott_wu

4: I_love_Tanya_Romanova

5: ecnerwala

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

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

All the " Author's First Codeforces round " are always carefully designed. Can't wait attending this contest.

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

Wish you the best of luck for organising your first contest

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

Which question has two subparts? Please share the points of all problems.

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

The time is not friendly for Chinese

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

I hope it's the first of many.

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

We expect problems would be interesting and this round will be remarkable for PARTICIPANTS & JUDGES.

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

Which problem has two subtasks?

And the what's the markes for each problem?

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

i have a question... current my email "not visibled" in codeforces, how to fix???

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

    It means other users can't see your email.If you want to show it,you can change it in "settings".

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

Hopefully, I will become spec.

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

Hope C1 and C2 I want rate inflation

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

coding sucks

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

Hope this round goes well.

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

As always, I find out everything at the last moment( Good luck to you to!

Как всегда, узнаю всё в последний момент( Удачи и Вам!

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

It's interesting that writing of contest problems is a free creativity. So many authors use imagination and fantasy almost without limits, sometimes even insert jokes.

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

    i love good jokes

    here is one:

    what did the microscopic cow say?

    Спойлер
    • »
      »
      »
      10 месяцев назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      This is anime cow

      Meow -> nya

      Moo -> μ

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

      It's a most funny joke that I see in problems

      B. Tavas and SaDDas

      Once again Tavas started eating coffee mix without water! Keione told him that it smells awful, but he didn't stop doing that. That's why Keione told his smart friend, SaDDas to punish him! SaDDas took Tavas' headphones and told him: "If you solve the following problem, I'll return it to you."

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

This is my first time! gogogo~!

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

Guess I'll be master after this round.

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

There are fewer people take part in this contest.

Maybe it is too late,but I'll still enjoy it!

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

I hope the problem statements are short and clear.

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

Please don't be stuck, server

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

When codeforces adds another speedforces.

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

WHY CANT I HACK PROBLEMS?

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

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

D is too hard for D.

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

    And E is too hard for E as well

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

    D is not too hard. It is too shitty.

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

      What is the solution? I feel fucking stupid. :'(

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

        think it's just some dp on leftmost/rightmost element in each row. lots of typing

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

        DP. Iterate over rows and for each treasure holding how fast you can reach that treasure with all treasures in the same row be gotten too.

        That's just my thinking. Late for submiting. RIP rate:)

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

        I think modifiable BFS or something similar.

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

        $$$dp_{row, lasty, lastcol}$$$, where $$$row$$$ is the number of row (we need to consider only rows with at last one treasure but in fact it does not matter), $$$lasty$$$ is either $$$0$$$ or $$$1$$$ and means that the last $$$y$$$ on the current row we visited is the leftmost $$$y$$$ of some treasure on the current row or the rightmost such $$$y$$$. And $$$lastcol$$$ is either $$$0$$$ or $$$1$$$ too and means that after visiting the leftmost/rightmost $$$y$$$ with the treasyre we go to the left safety column or to the right safety column from this $$$y$$$. Transitions are very easy to understand but hard do code.

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

          Can you elaborate more ? I am not able to understand :(

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

            Since you can go only up, never down, you have to collect all treasures of one level at once. This end in standing on the leftmost treasure of one level or the rightmost one.

            From these two positions there are again four paths to the left/right treasure of the next level.

            These paths are simple. You can allway either go left, then up, then to the treasure, or go right, then up, then to the treasure.

            So, you need to write that down in terms of dp recurrence, which is no rocket science, but nasty index fiddling.

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

          Said Vovuh and get WA)

          You lost chanse to become a master on this contest((

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

      Exactly, it is just tons of typing. And E seemed like this as well :(

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

TypingForces. Also D is unusually tough.

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

I can't see B solution meh feels stupid

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

How to solve B?

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

    You can always make everything to zero if and only if :

    1. Sum of all given numbers is even.
    2. No element of array exceeds half of the sum.
    • »
      »
      »
      10 месяцев назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      Try 3 3 3 5

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

      Could you explain the second point please?

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

        Try to think number $$$x$$$ as $$$x$$$ balls of one color. We can match a ball with another ball with another color (pair with same balls is not allowed). Then, we note that if there are odd balls, we can't complete matching. This is first point. If we have too many balls of one color (by "too many", I mean more than half of all balls), by the pigeonhole principle (although it is pretty straightforward), at least one pair must contain two balls of that color.

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

      What about 2 2 2

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

      please is there a proof for point 2?

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

        If a color has cardinality over n/2, there is no solution because you will need to pair up two elements of a color at least once. Otherwise, we construct a solution as follows: make each move by choosing of the two largest groups of colors. It is intuitively clear to me that making this kind of move will ensure that, in subsequent moves, no color gets to cardinality over (total number of balls)/2. And if we always preserve this property, there will always be at least 2 piles.

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

      I also thought first one but the second was too away from me :'( how did you find this solution? (I mean the second approach)

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

        It seems quite awkward for me to explain how I approached this problem since I struggled twice (If you take a look at my submission, you'll notice that I tried 2 completely different logic which both were not working).

        However, I think for this problem some caseworks can help. I basically noticed second approach when I thought of following case :
        2 numbers, (1, 7). Sum is even, but we can't do the task.

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

          I also noticed that (1, 7) case but I couldn't bring more :(

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

            Maybe more casework would have been helpful. Restricting to 2 or 3 numbers (which is hand-doable)? Such as (1, 3), (2, 2), (2, 3), ... and thinking with more data.

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

      How do I prove it?

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

      Try 12 3 9 4

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

      how do you know that these are all the necessary conditions? How do you know there aren't more? I thought of these in the contest but didn't think it was that simple

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

      can you prove it?

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

    sum all elements. Than if the sum is odd then return "NO" else check if the largest element is bigger than the sum/2, if it is than "NO" else "YES"

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

    Just think nothing!

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

How to solve D?

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

Is N^4 the intended complexity for E1 ?

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

What is pretest 5 in B ?

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

Logic behind B?

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

    sum(1,n) % 2 =0 and sum(1,n-1) >=a[n] with array a sorted -_- -_-

    bad at english sorry -_-

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

    Think about this test case: 6 6 4. I think you will understand the logic behind solution of B.

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

    If the biggest element is not larger than the sum of the rest, then it is possible. If the sum of all elements is even, of course.

    Basically, if all this holds, then you can take pair "smallest element — largest element" and decrease them until the smallest one becomes 0. Then you just reduced the number of elements, but the two main conditions still hold. You can show by induction that you cannot end up in a situation when you have only one number left -- otherwise the first condition did not hold from the very beginning.

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

      wow!

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

      Consider the following array: 4, 17, 19. Sum % 2 == 0 and 19 < 17 + 4. So it should work.

      If I apply your method of taking smallest — largest pair and decreasing the following happens:

      First step, take 4 and 19 and reduce and you get 0, 17, 15. Next, take 17 and 15 and you are left with 0, 2, 0.

      Did I misunderstand anything?

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

        You don't have to reduce 4 all the way to 0 because when we have 1 17 16 then we will decrease 1 and 17 because they are the biggest and smallest right now. This will retain our claim

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

          Ah I see, thanks for clearing it up.

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

          So, basically you have to sort the whole array after each turn to make sure the arr[0] and arr[n-1] are getting reduced by 1 where they are smallest and largest pair. Got it. Looks a lot simpler this way.

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

    I solved without sorting. 'YES' if sum of all elements % 2 == 0 and there's no element which is more than all other values' sum, 'NO' otherwise

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

any guesses on test case6 of question 3??

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

Test 5 B == killer.

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

Anybody know what pretest 7 in D was?

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

Dafuq was B omfg

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

Logic behind c?

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

    binary search

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

      More precise please

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

        If you want the median to be at least X, you need at least (n / 2) + 1 elements to be greater or equal than X.

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

        Then binary search the value of the median. Let's say the value you want to check is X. Then you have to check, whether you can increase all numbers with indexes from N/2 to N up to X, using only k moves. For this you need: a) prefix sums of array elements, b) to search the first element in the second half of the array which is already larger than X (also binary search).

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

        You sort the array. Find out the middle element each time. Increment it by 1. But array must remain sorted throughout. Thus, a multiset might help. (I didn't implement it during contest, but I guess the logic is correct. Correct me if I am wrong)

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

      binary search gave me TLE on 2 solution one n*log(n) & the other log(n)² , had to implement the O(n) solution

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

A, B, C are standard problems. D is a good problem. For this thank you author.

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

Когда предлагаешь контест просят указать особенности задач, которые даются. Кому какие сегодняшние задачи показались необычными и интересными? В чем их особенность? У кого после решения задачи появилась радость, что ты придумал классное решение и оно зашло? Лично мне не понравилась ни одна из АВС. Тем более у меня не появилась радость после решения баянистого С. Кроме того, D и E, по-моему, очень сложные для D и E.

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

i wanna to ask why my code wrong on pretest 2. https://ideone.com/rwIkPi. they say it is undefined behaviour, but i didn't figure out where it happens.

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

B reminded me of AGC 036 C.

By the way, could somebody hack my solution for D? I solved in a dijkstra-like style. I checked 998244353 times but I couldn't find my bug.

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

    My solution is working fine on custom testing on cf for all sample 3 test cases . But failing for 1st test case while submitting. can anyone plss check it

    https://codeforces.com/contest/1201/submission/58300351

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

      So what about your mistake? At least, now custom invocation shows "10000000000000000", not the right answer.

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

    OMG, edit distance was 1...

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

      what is the mistake?

      • »
        »
        »
        »
        10 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Спойлер
»
10 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

When you propose a contest, you is asked to indicate the features of the tasks that are given. To whom what today's tasks seemed unusual and interesting? What is their feature? Who, after solving the problem, got the joy that you came up with a cool solution and it came in? Personally, I did not like any of the ABC. Moreover, I didn’t have joy after the decision of the old C. In addition, D and E, in my opinion, are very difficult for D and E. Sorry from my poor English

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

My solution is working fine on custom testing on cf for all sample 3 test cases . But failing for 1st test case while submitting. can anyone plss check it

https://codeforces.com/contest/1201/submission/58300351

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

Hey guys, Could anyone please explain to me what is the hack means for contests?

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

    If your solution's imperfect(even though you passed pretest, it's possible), the others who locked that problem can hack your solution with data which is counterexample.

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

      Could you please more clear :D I am new for contests

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

        During the contest, your submissions are only tested on a limited set of test (pretests). It's possible that an incorrect solution can pass pretests, so during the contest, other people in your room who have solved the same problem can choose to lock their problem and "hack" your solution (provide a test case where your soln will fail). Hackers are awarded +100 pts for succesfull hack, -50 for unsuccessful.

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

        The pretest doesn't cover all of test data. So although you passed pretest, it can be a wrong answer. After pretest passed, you can lock the problem. It means you cannot change your answer and you can read other user's code. When you reading code, if someone's code have counterexample, you can enter counterexample and if the hacking attempt's successful, you can get 100point. but if it failed, you lose 50point. Can you understand? (sorry for my poor english)

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

Wasn't the contest a bit unbalanced? Still, quite a good contest for a first timer setter. :)

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

Problem D looks similar to a recent task from TCO, except that the one from topcoder restrict the number of safe columns to exactly two.

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

--deleted--

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

A nice version of problem D: 1066F - Очередная ходьба в 2D.

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

Okay, why is E1 worth 2000 and E2 worth 1000? E1 is nothing but dumb coding that doesn't even require much thinking from my perspective, while E2 is a beautiful (in my opinion) and hard problem.

Subtasks are getting a bit annoying on CF :(

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

    From perspective of Div2 users both of them are almost unsolvable)
    P.S. Sorry, not almost:D

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

    "Dumb coding"

    When even with the unoficials contestants, only 2 persons for 7000 contestants solved it, and that even high rated like scott wu, ecnerwala and a lot others red contestants couldn't solve it, I'm not sure the problem was so "dumb".

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

    Do you see better scoring solution under assumption that subtasks are there?

    I agree that it sounds questionable when you look at it from this perspective, but it all kinda makes sense. Proper solution gives you E1+E2, for which 3000 is reasonable. During the contest I spent 25-30 minutes thinking on E2 before abandoning it — and the case work that I had at that point was more complicated and messy than the editorial.

    Yes, E1 is straightforward coding which requires even less thinking than D — but it is, by div2 standard, quite a lot of tedious coding. I don't think it would be fair to say that 58306483 is worth less than solving D. Is it really that wrong to look at it like "either you just code the trivial part and get 2000 for it, or you solve a full problem for 3000"?

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

Even though I may not have solved most of the problems, I quite enjoyed the contest. The questions were challenging and intriguing at the same time.

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

Can anyone recommend some problems to solve to develop skills to solve problems like B ?

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

A, B and C are too easy and D was too tough I think this contest just focuses on speed.

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

SPatrik, can you explain to me why did you need this statement that knights are allowed to capture each other? Does it affect anything except solutions that fall as mine because the case was forgotten when I need to capture an opponent`s knight? And why was not it covered by pretests?

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

    Without capturing, the problem would be really easy. Just select the knight that can reach it's target faster. With capturing, there is a situation where you have to move more tricky. First go to the opponent target, then to your target. Read the editorial for more details.

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

      Of course, I meant that it would have been greater if knights hadn`t been able to move under attack at all, not allowing moving under attack and being immediately captured afterward.

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

        Yeah, that could be done. That would remove the possibility of those minor error. I didn't think that way. There wouldn't be any other differences, capturing just makes the game more realistic.

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

          If you like this so, this case should be in pretests at least :). But as I would think in your shoes, the statement that doesn`t affect should be removed. Anyway, thanks a lot, I like this problem very much despite that mistake!

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

Are you kidding? A B C are too easy and D is so hard. it is not suitable as D.

For E & F , are you sure you were not make a kidding to us?

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

Thanks to SPatrik for problem C. The same problem was given to the participants of Lipetsk Municipal Olympiad and some participants who wanted to qualify for Sirius (December 2018) about one year ago. So, I had the same problem prepared in Polygon and you helped me realize that my testset wasn't full and some authors' solutions weren't right. Thank you very much :)

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

for god sake WA on C because of int overflow, Shame ._.

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

WOW fast system testing

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

Can someone help me find out why is this submission getting MLE? 58305730

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

    How deep can your recursion be? If it is too deep, it keeps all variables in the stack.

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

      In the worst case the recursion's depth will be equal to the number of states which is N^4 * 2 which is ~ 5 million. Is it really enough to fill up 256 MB?

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

        I do not really know, what exactly each call stores. For sure it is your method variables (passed + 2 internal), it is below 15 B though. But there should be something else, I guess.

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

I dont get why a lot of people failed to solve B.

can somebody explain

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

    Can you explain how you find it to be easy ? Also can you recommend similar problems ?

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

    How to solve it ?

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

      the sum of all elements must be even.(because we decrease the whole sum by 2 after each operation)

      also the biggest element should not be larger than half of the whole sum.(because for every operation that we decrease the biggest element there should be another element bigger than 0 to decrease)

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

    i forgot that i have to reduce by 1 instead was trying to solve it by reducing full number from other

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

    They didn't guess that one of elements maybe greater than all another. In this case also there is impossible do it

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

    First I thought that you can simply take two biggest numbers, and reduce them as much as possible — and then repeat this procedure until all become 0. But this logic does not always work, for example, for the case 99 100 101.

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

one should never overthink B otherwise, it cost him his rating

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

    True, At the first glance I thought about a partitioning problem and this would have got TLE easily lol

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

This is my last Div2 Round. But I was late in submitting E1 about 10 seconds so I missed the last chance to win in Div2. QAQ so sad....

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

    I was not sure that my solution is correct and my implementation is correct. So I inserted some assertions in my code. But I accidentally did a wrong assertion. So you can see that I got some REs in my contest submissions. And then I replaced those assertions with exit(0) so I got WA. Then I realized that my assertions was wrong. As soon as I finished to erase them, the contest ended.

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

    Maybe it's not your last Div2 round :)

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

My rating did not update. Why?

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

How this case could be "YES"? Problem B.

Test case 5 :

5

1000000000 1000000000 1000000000 1000000000 1000000000

Answer YES

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

    Just because i dont want do write zeroes, here is explanation for 5 10 10 10 10 10

    9 9 10 10 10 9 9 9 9 10 9 9 9 8 9 9 9 8 8 8 8 8 8 8 8 (and repeat until all are 0)

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

    take half of 1000000000 and half of the next 1000000000 ,they cancel out one 1000000000 now we left with: 500000000 500000000 1000000000 1000000000 now it's trivial...

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

    make it

    1000000000 1000000000 1000000000 0 0

    then you can make them

    1000000000 999999999 999999999 0 0

    999999999 999999998 999999999 0 0

    999999998 999999998 999999998 0 0

    as you can see ,you can reduce all of them by 2 after 3 operation. so you can make all of them zero as well

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

    A similar example is {2,2,2,2,2} you can take operations like {1,1,2,2,2} {0,1,1,2,2} {0,1,1,1,1} {0,0,0,1,1} {0,0,0,0,0}

  • »
    »
    10 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    • 500000000 500000000 1000000000 1000000000 1000000000
    • 500000000 500000000 500000000 500000000 1000000000
    • 500000000 and 1000000000 give 500000000
    • so we get : 500000000 500000000 500000000 500000000
    • now you can conclude the result
»
10 месяцев назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

can anyone help me finding error in this code

int main()
  {   
      ios_base::sync_with_stdio(false);
      cin.tie(0);
      cout.tie(0);            
      //std::setprecision(20);    
      int tests=1;
        //freopen("input.txt", "r", stdin);
     //  cin>>tests;
       
     while(tests--) 
      {   
        ll n,k;
        cin>>n>>k;
        ll a[n+1];
        for(int i = 1;i<=n;i++)
           cin>>a[i];
         a[0]  = 0;
        sort(a,a+n+1);
        ll i = (n+1)/2,j;
        j = i;
        ll median = a[i];
        for(j = i;j<n;j++){
          if(a[j+1] > a[j])
          {
            if(k >= (a[j+1]-a[i])*(j-i+1)){
                k = k-(j-i+1)*(a[j+1]-a[j]);
                //cout<<a[j]<<" ";
                median = a[j+1];
            }
            else{
                break;
            }
          }
        }
        if(k){
         // cout<<k;
          ll len = (j-i+1);
          median = median + k/len;
        }
        cout<<median;
 
      }
}
»
10 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What wrong with me? It's second consecutive time I passed pretests and got wrong answer in system tests. It's not wrong approach, it is overflow integer. So sad for my rating.

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

How to solve E? Is it SG function or something else?

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

The code of neal’s problem D has a problem.In its last loop,safe_index might equal to safe.size(),and safe_col has random value.It might lead to “wrong answer”.(Sorry for my poor English)

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

Problem D:Could anybody tell me why I always fail on test 13? After reading the editorial,I found that my idea is correct.Maybe some details!

code:58360651

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

In problem div2 C i think like the position of median is not changing right. so sort the array take sum from mid to n add k and divide it with number of element from median position to end that will give the max median . //{sum of(a[position of median to n]+k) divide (n-mid)} but its not working for all case. somebody have any idea