Cirno_9baka's blog

Codeforces Round #593 (Div. 2)
By Cirno_9baka, 5 years ago, In English

Hello, Codeforces!

I'd like to invite you to take part in Codeforces Round 593 (Div. 2). It will held on Oct/17/2019 16:35 (Moscow time). The round will be rated for the participants with rating lower than 2100.

You will be given 6 problems and 2 hours to solve them.

Scoring distribution: 500—1000—1000—1750—2000—2500.

The problems of this round were developed by me. Thanks a lot to isaf27 for his excellent coordination, to Mike MikeMirzayanov Mirzayanov for Codeforces and Polygon platform, and to mnaeraxr, antontrygubO_o, NIWIS, win11905 for testing.

This is my first round ever. I hope everyone will enjoy it.

Good luck!

UPD: The round is over! Congratulations to the winners:

Div.1 + Div.2 participants:

  1. LayCurse
  2. nuip
  3. Geothermal
  4. liouzhou_101
  5. Pelmelnik2

Official participants:

  1. Pelmelnik2
  2. lrvideckis
  3. zml
  4. DAL_DAL_USHEL
  5. phosphoric

UPD: Now the Editorial is available.

  • Vote: I like it
  • +183
  • Vote: I do not like it

Comments Comments (205)
| Write comment?
»
5 years ago, # |
  Vote: I like it +54 Vote: I do not like it

It's the contest season again :D

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

PS. I hope anyone record the process of preparing one problem with commentary, will publish it on Youtube after the contest. It's useful.

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

Who else is going to make this contest a priority to gain back the rating points that we lost in Tourist's contest ?

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

    I have a suspicion that contenst was just a measure to target rating inflation at Codeforces.

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

    I hope I can do that. Good luck!

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

    well,I did too badly on tourist's contest I don't think one contest is enough to make it up. Anyway,I wish you all good luck and high rating.

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

Best of luck for your first contest

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

How short the announcement is!

However, hope your first round will be successful!

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

Request for This contest :: Please make large inputs downloadable

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

Hope for a great contest as it’s your first time !

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

i wish it be safe from any hacker attack .. Cirno_9baka

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

Do you think this round will be the strongest?

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

I will try to wake up on time to participate. Now, I have a challenge: For every rating point lost, I will do one pull-up. For every point won I will do three pushups. Everyone is welcome to join the fitness challenge. Write what you'll do if you lose or win rating.

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

    I screwed up badly. This is gonna hurt.

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

A bus left the Scarlet Devil Mansion; $$$a$$$ people boarded at the start.

At Hakugyokurou, $$$b$$$ people left and $$$\frac{b}2$$$ people boarded. (It is guaranteed that $$$b$$$ is odd.)

At Yakumo-san's house, $$$d$$$ people left, where $$$d$$$ is the imaginary solution to $$$ad^2 + bd + \sin c\pi = 0$$$.

How many passengers remain? Print the answer modulo $$$993\ 244\ 853$$$.

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

According to the writer's name, I bet this round may include some Touhou-themed problems.

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

Good luck with your first contest!

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

I smell math problems O_o

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

UwU

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

I hope the round contains some basic graphs problems

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

    I hope this round does not contain strings problems

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

      yeah seriously

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

      Why?

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

        By strings I meant strings related some advanced DS or KMP etc. for a stupid and mean reason because I don't know about them. Though I should not worry about them because even if they are present, they will be in later half of the set.

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

        Btw since you are tester and your reply to this particular comment gives a hint that there will be some sort of strings related problems.

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

Thanks for the contest :)

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

Oh, maybe I'll become green after this round.

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

[Deleted]

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

i hope statements wiil be without anime

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

wish short problem not hard code good pretests and high ratings :)

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

A speed typing test?

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

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

Speed Test :/

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

Was B meant to use OEIS???? How come B is on B? 1000???

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

    PROBLEM B is (2^m-1)^n

    I TYPED THIS FOR SO LONG OK SO PLEASE READ https://pastebin.com/Qjr3h8Ui

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

      care to explain ?

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

        The number of ways to include the ith kind of item is the number of ways to pick k boxes out of the m boxes. Also, the number of ways of picking the ith kind of item is independent of the number of ways of picking the jth kind of item.

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

        For each type you need to choose subset of boxes. And subset must be non-empty

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

        I have added explanation sorry it took me long time

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

        The idea es the following: If we only focus on a certain number, we have clearly (2^m)-1 possible options. This is because any box can be either "full" or "not full", this is, with the number on it or without it. We substract 1 because we don´t consider the case in which every box is "not full". Then, as we have n possible numbers, for every number we have (2^m)-1 combinations, resulting in ((2^m)-1)^n.

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

    My answer is (2^m — 1)^n

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

      How did you come up with this solution?

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

        We need to distribute every present to at least one box ie (2^m — 1) (-1 because you remove the case where all boxes dont have this present)

        We do this for every present... hence: (2^m — 1)^n

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

How to solve F ????????????????????????????????????????????????????????????????

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

How to solve D?

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

    Seems like the doll's trajectory is a spiral from $$$(1,1)$$$ to the center, therefore the obstacles must only be in the end of the spiral (or form complete rows / columns on the bounds of the grid).

    If this is the case, I don't know how to code it neatly and concisely.

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

    The path must be a spiral... somehow. "Simply" check if one can run that way.

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

      Isn't that O(nm) which is 10^10?

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

        You don't actually visit each cell. On each row (or column), you just move to the end of the row, which means finding the first obstacle hit, or the last column not yet hit. This is O(lg k) time (binary search the obstacles on the row). So, each row or column is O(lg k) time, and each row/column is done only once, so total time is (m+n)(lg k).

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

        No. You run from (1,1) to (1,n-1), then to (m-1,n-1), then (m-1, 1)... And so on.

        It loops 1e5 * 2 times.

        One can use two sorted lists of the obstacles to optimze the search.

        Sort one list by colums, one by rows. Ie use vector<pair<int,int>>, onc sorted by first, one sorted by second, then first.

        To check if all fields where visited, count them. Fieldcount + k == n*m

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

How to solve D ?

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

    The first observation would be that if there is a solution, then the path will look like a clockwise spiral. The second observation would be that we don't have to simulate each step. Instead we should simulate all the steps in one direction in one move.

    Let's initialize the variables n1 = 1, n2 = n, m1 = 1, m2 = 2 the borders of submatrix we should be able to visit. Also let's keep sets on each line/ column in order to store the obstacles on those lines/ columns.

    Now let's say we're at position (i, j) and just changed direction to move to the right. If there is an obstacle in our way at position (i, k), with k from [j + 1, m2]), then we can only ever reach column k — 1. Thus m2 will become k — 1. Moreover, a solution exists only if the submatrix ((i, k), (n2, m2)) is filled with obstacles, else there is no solution. We can easily check this using our COLUMN sets (i.e. if a column k -> m2 has exactly n2 — n1 + 1 elements then it is filled with obstacles, else not). To be able to make correct checks in the future, we will remove all these obstacles found in the said submatrix from their corresponding LINE sets. Now we can update n1 to n1 + 1 (since we will never return to this line), update the doll's position from (i, j) to (i, k — 1) and change the direction to moving downwards. Everything works in a similar way for the other directions.

    We know we reached the end if the number of steps taken + the number of elements removed == n * m.

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

Perfectly imbalanced.

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

    Did you find what is test case 4?

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

      There was a problem in the logic of my solution, and I found that the actual solution will require much heavier implementation, so I couldn't make it in time.

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

This was perfectly imbalanced round.

I really hope the problem D has some pretty and easy to implement solution.

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

    Yeah I agree; the one I was thinking of was really nasty to implement (lots of if cases and room for error) so i figured it wasn't worth it given how much time I had left. Watch there be some 5 line mathematical solution lol ;P.

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

    Indeed, I've figured the spiral logic, had 140+ lines of code but I was still writing code 5 minutes before the time ended.

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

    Basically we have to check the frame and blocked and one central blocked component.Heavy implementation !!!

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

      If it was so easy then why didn't you submit it? Oh, I understood...

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

Greedy solution for $$$D$$$:

Keep going in the direction you are facing until you have to change it. When you can't move anymore, see if you covered all squares, if you did, answer is yes otherwise answer is no.

Try to prove this.

Implementation: 62820909

Edit: Why the downvotes?

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

    Correct. But hard to implement, as N, M <= 10^5, which makes it impossible to mimic every step.

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

      I implemented the simulation by C++ upper_bound but I am missing some cases.

      Edit: I just realized that I had just forgotten to replace a $$$x$$$ by $$$y$$$ after copy-paste. Got AC now. :(

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

        I also implemented using upper_bound but got TLE on case 4

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

          Cool. It's the first time I've heard of this method... Silly me implemented a sort of binary searches.

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

      It was indeed a pain to implement. But, you don't have to visit every cell. Just determine how far you can travel on that row/column.

      I used binary search to find the next obstacle on that row/column, and then just moved that many spaces (or, until I had reached a previously hit row/column). So, total time is just (N+M)lg(K).

      Still this was very annoying, and I ended up just copying sets of code 4 times to handle the different directions; not at all elegant.

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

        And you check whether you cover all cells by (N*M — K — cells_visited)?

        Nice move! I even write a function to confirm a rect is filled by obstacles and proved the overall complexity is O(klogk)...

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

problem C feels like "dont know why does it work but gonna send it anyway"

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

    The problem C reminds me of printing snake print of a given matrix.

    If n is 3, then insert elements till n**2 (i.e. 9) in spiral order in a 2D matrix:

    1 6 7

    2 5 8

    3 4 9

    Finally, print it. As simple as that

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

    Yeah the problem was too wordy so I skipped straight to the example, figured out a weird pattern, coded it up super fast, and watched it get passed pretest with disbelief. I was fully expecting a WA but I got lucky o_o.

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

      So, i can prove it. Let's explore f(X,Y) and f(Y,X). Of course, f(X,Y)+f(Y,X)=n^2. so max value of min(f(X,Y),f(Y,X)) is (n^2)/2. So, (n^2)/2 is our top estimate.

      Let's try to reach it. Let's build an example, where min(f(X,Y),f(Y,X))=(n^2)/2. (for any X,Y) This way, I divided n^2 labs at n sequential sectors. Let every sector is a permutation of {1,2,3,4..n}. So we have sequence A, A.size = n^2. This sequence means that lab with index i has group number A[i].

      Let's take two random groups X,Y. Understand, that for each sector water can go from A[x] = X to every A[y] = Y where (sector of index y)<(sector of index x). So, f(X,Y)>=n*(n-1)/2 Likewise, f(Y,X)>=n*(n-1)/2. (observe that n*(n-1)/2 + n*(n-1)/2 = n^2-n, that is we lost n pairs).

      ok, we didn't explore such A[x]=X, A[y]=Y, where (sector of index y)=(sector of index x) Here is n pairs. And we need to distribute them roughly in half between f(X,Y) and f(Y,X) to maximize min(f(X,Y),f(Y,X)). So, in roughly half sectors $$$x<y$$$ and in other half is $$$x>y$$$. My solution is to make sectors such way: sector1 = {1,2,3,...n}. sector2 = {n,n-1,...,2,1}. sector3 = {1,2,3,...n}. sector4 = {n,n-1,...,2,1}. ...

      Easy to see that we reached our purpose: in roughly half sectors $$$x<y$$$ and in other half $$$x>y$$$, for every groups X,Y, where A[x]=X, A[y]=Y. After writing this solution you can see that it will be a number-snake in answer table.

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

How to solve B? I've used b*(2**a)+1 formula but getting TLE

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

    (2^m-1)^n remember to use fastpow

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

      Can you exaplain how did you reach this equation ?

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

        Sum of binomial coefficients i.e. nC0 + nC1 + ... + nCn is equal to 2^n. This is a common property of binomial coefficients.

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

        for the situation of n=1 obviously the answer is 2^m-1(all have 2^m situations, but the situation of all of m is none is incorrect) So when n is greater than 1, the answer is multiplication of n numbers which is 2^m-1.

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

        It's like suppose there is a ball. Now for every box, I have 2 choices to make whether to put that ball in it or not. So 2^m for m boxes. Now this includes a way where we haven't put that ball in any box. Hence, allowed ways — 2^m — 1. Now,since there are n such balls therefore ( 2^m — 1) ^n

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

      i used the same thing but wrong answer on pretest 3

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

        Maybe your fastpow is error

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

          i changed long to long long and it worked .Can u explain whats the need of long long?

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

            emmm, In fact,long has the same range as int while the answer which mod 1e9+7 may be large（near by 1e9). So your data may overflow in your code of fastpow. Check your code and you will find there will be some multiplication which makes your data overflow

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

    you were close, i also did the same at first but got WA on test case 3.

    after that i realize that, for 1 item the probability is 2^m — 1, what about 2 item? just multiply both of it (2^m-1) * (2^m-1). since n = 2^19, iterate it would be TLE.

    so the solution is (2^m-1)^n and don't forget to use Modular Exponentiation

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

I submitted my solution just before the contest ended and I got an idleness limit exceeded. What does this mean? Link 62815630

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

How to solve E?

I tried to solve it with DP, but my table dimensions were too big, which was something I couldn't reduce ...

Even though I agree the problems were not really balanced in terms of difficulty, I liked them a lot (especially D and E seem to be very interesting and I'm looking forward to read the editorials).

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

After a perfectly balanced round, comes a perfectly unbalanced round.

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

    N(balanced)== N(imbalanced) -> perfectly balanced

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

It took me 15min to undertand statements of Problem E...

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

I think this round is very imbalanced, because tester's team mainly consists of div1 persons

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

Me after solving A,B,C:This round doesn't seem to hard. Promblem D:I'm going to end this man whole carrer.

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

touhou round so hard q.q

What is test 7 in D?

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

D is a debugging nightmare...

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

    It would be worse if pretests is weak..
    I submited 4 times to pass the pretests...

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

      Nonetheless, LayCurse managed to pull off 5 hacks in a room of yellows and reds, with only 9 submits for D..

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

        And I just found my submission failed at m = 1, n > 1....

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

Why is this code getting TLE in problem D? Code I used binary search for the current location and changed the location accordingly.

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

    Do you have an infinite loop for most grids? That's the mistake I made and this looks similar. Try input 5 5 0, for example.

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

      Infinite loop for this case :/ Thanks!

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

Can someone please explain how did you come up with (2^m -1 ) ^ n for B?

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

    Sum of binomial coefficients i.e. nC0 + nC1 + ... + nCn is equal to 2^n. This is a common property of binomial coefficients.

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

    From input explanation you can see that there is 2^m — 1 ways to divide one present to m people. All n presents have the same amount of combinations so from here answer is (2 ^ m — 1) ^ n

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

    consider present type x: you have 2 options for each box to put present in it or not. so in total you have 2^m options but one of the at least should not be empty so 2^m-1.

    and each of present types are independent from each other (do same procedure for all types) so (2^m-1)^n.

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

fot problem E it takes me almost 60 minutes to find the trap it turns out to be the situation that n=1.

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

didn't like problem c so tried to solve D. tried for 70 mins solved it 5 min after contest was already over smh . should have just sticked to C.

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

For E is it correct that for any x the pairs (x, y) that satisfy will be such that all the possible y's for that x will be continuous integers ? Like (3, 1), (3, 2), (3, 3) where x is 3 and y belongs to [1,3]?

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

    Yes, since after reaching a position y you can always stay there by moving right if ai = y, and moving back after the last one, stay there for the rest of the cases. However I got stuck on finding maximum and minimum y

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

      Ya, I realised my solution failed on pretest 15 since I didn't consider N = 1 case.

      Anyways here's the solution to find the maximum and minimum:

      The brute method is to increase/decrease whenever possible.

      Brute Code

      To optimise this we can create an array of size M that says for each position p if we have a number equal to A[p] at that point what's the max or min I can get at the end. This can be calculated in M log M. We can use the same array to find for each number what's the max/min I can get if i start with it.

      code that fails on pretest 15

      Update : Got AC by fixing N = 1 Link

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

        Man I thought an array like so might not be able to transition but after reading your idea I wrote it on paper and yes it can be calculated in M * logM. Thanks.

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

Disgusting problem D

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

For everyone waiting for system tests:
there's a new twice mv out now
https://www.youtube.com/watch?v=zQELp93xxfo

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

Amazing Round .

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

Although deriving formula for B is not that hard (just in my opinion), I think it was not appropriate to put such problem in Div2B since it requires fast exponentiation.

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

    correct. B should have been easier than this one. C should be D. D = E.

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

    How about python? Time to learn a new language

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

      python does binexp?? I just wasted 15 minutes debugging my bin exp in python3 X(

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

        pow(a,b,m) returns a^b mod m :D

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

    I think the formular is unreachable if one has to figure it out by himself.

    I tried to come up with a solution for n=1, and did not found it. After seeing the formular here in the comments it is fairly simple to implement it.

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

I meet a strange bug when using m2.codeforces.com:

The statement of A says 'The statement is not available'.

So I think there're some technical issues and throw A away...

I didn't realize the problem until I looked at the standings after one hour!

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

    The same here. However, this is a lesson for you to open every problem before solving any of them.

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

    Always have both the main site and a light version open. Main site gets attacked, light site has bugs.

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

      Main site gets attacked, light site has bugs

      balanced?

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

      Main site gets attacked, light site has bugs.

      However if both happen, it's imbalanced. (I used the light site because I can't get connected to the main site during the contest, at least in the first 5 minutes...

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

Who else forgot n=1? :)

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

    It is glad to see that the author determined to make the $$$n=1$$$ case in the pretests. Or there will be plenty of FSTs, for example, me.

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

      Totally agree. :) I'm glad that pretest 15 was there to block me early.

      (And pretest 14 reminded me to use a long for the answer, lol).

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

WHEN I SAW problem B ![ (https://images.app.goo.gl/H9q9HbBeTSCQTjVS8)]

WHEN I SAW PROBLEM C ![ (https://images.app.goo.gl/P7HnpmTw4LKifK2J8)]

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

Red coders should stop making Div2 only contest. Their contests are so inbalanced. :(

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

    In my opinion the imbalance matters because solving a harder problem differentiates the people who are skilled and not skilled. For example, tmwilliamlin168 is extremely skilled so he always solves more problems than me. tmw OFZ.

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

I missed the DDOS attack this round :(

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

Upvote if you got the solution to C from sample

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

If I get to 1400 rating I change colour right? OMG I might get there plz

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

Deleted

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

62815596

Can somebody explain (TASK D) why this is not correct?

First I remove full lines with block (right and bottom)

Next I check that all remaining blocks in tail of snake-filled array

for example if left 3x3 array and two blocks, I check that this blocks in 8 and 9?

Is it correct? Or idea was wrong

1 2 3

8 9 4

7 6 5

upd. I think I understand, I need to delete all left vertical lines with all blocks except 1 row...

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

Aaaaaaaannndddd.... WA218!

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

Congratulations with your first contest! Congratulations with your last contest too!

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

Can you explain your thought process for B?

Like from when you saw the problem

IMO C was easier than B

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

    I tested with examples, noticed that we needed to assign one present to someone for each type and listed out the ways for the rest.

    My kinda messy (not the smartest but i guess easy to understand) explanation https://pastebin.com/Qjr3h8Ui

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

    B is quite clearly a math problem (very large input parameters, O(n) fails, reads like combinatorics), so the idea would be to try and derive a formula to solve B.

    My solution used inclusion-exclusion and was very messy, but the expression simplifies quite nicely to the simple formula.

    Edit: So you count all the ways to distribute the gifts without considering whether every gift is used, to get 2^NM ways, and then you consider the case where at least one gift is not used, and then the case where at least two gifts are not used, et cetera. The result is a well-known expression (binomial theorem), so you can get (2 ^ M — 1) ^ N.

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

problems are very interesting. I really like it!

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

Can someone verify if the following logic is correct for D?

If we just consider all obstacles, they're also going to form a spiral path. We can fix one obstacle and break this path down into two spirals: — a clockwise spiral path and an anticlockwise spiral path. So, we start from this obstacle and simulate the moves, the clockwise starting from direction 1, while the anticlockwise starting from direction 3. If we can cover all the K obstacles in either of the 2 (disjoint) spiral paths, it's a valid input.

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

    i do not think anti-clockwise path is a valid one....

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

    No, I think the obstacle doesn't have to form a spiral path always.

    Consider the following grid: (1 = Obstacle, 0 = Empty)

    0 0 0 0 1

    0 0 0 0 1

    0 1 0 0 1

    0 0 0 0 1

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

I guess that one Specialist tester wasn't enough.

But I have to say, that I like these problems.

F seems to be interesting.

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

Why problem creators make such problems as C? there is no any logic just like guess output and get AC. I think at least 95 percent of participants solve it so. I dont like this round for me the tasks were uninteresting and disbalanced.

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

Sorry for the difficult problem D.

I thought it may be just a simulate problem and may not so hard, but the fact isn't. It contains many details and not so easy to write.

Again I will say sorry. I will try to improve myself on controlling the difficulty of the problems.

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

    I submitted at last minute. So, I am scared of TC218.

    UPD: Accepted with 6 TLE attempts..XD

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

    So what is the content of test #218? Is it pre-determined or from hacking?

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

    You will do better next time， keep it up

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

    I believe that the main problem with it was the weak pretests, if test 218 was in the pretests, maybe the percentage of AC would be way more different :/

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

    I think the main issue of this round not problem D. It was pretty hard to implement but doable. But the problem C is not a good problem for such round. I'm pretty sure that 90% of AC on this are just "hm, I consider some pattern in the output, what will happen if I submit it? Oh, AC, great!". Almost nobody proved this solution during the contest and this turned out the problem to finding the pattern faster than others.

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

      Problem C rewarded people who were like "Let's try this non-sense first and then think more" and punished people who were like "Let's think first, if no ideas, try some non-sense".

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

      Exactly my thought. Seemed to be a very Codechef-esque problem (at least for me). Every time in the Div 1 long challenge, they give one of the first 3 problems like this. But, at least, they give 10 days to think. Lol.

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

    My problem with D was that I didn't realise every cell can only be visited once until the clarification came.

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

Anyone got what pretest 4 is? Please share

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

How to solve E?

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

    Observe that the reachable points for each starting point form a continous interval.

    Say that for each starting point, we want to know the farthest point to the left it can reach, which can be done by each time make one move to the left if possible. We can simulate the process in $$$O(n)$$$ by maintaining the number of starting points at each current position.

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

      Is true, you just need to calculate the most away reachable point to the left and right of each position. But how can you make it in O(n) time. I think about using ST to simulate it, but it turns into a complicated implementation, can you explain me how to solve the problem using your idea?

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

        Process every position in parallel. Each time every position should move to the left except one. This should lead to an $$$O(n)$$$ implementation.

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

If anyone is curious, I suspect test 218 for problem D is something along the lines of:

3 1 1 3 1

The correct answer is Yes, but many solutions are printing No, because on your first step you can't make any steps to the right. However, that's not an issue here because you can immediately turn right (so you're now facing down) and move down one step. I tested a few WA218 solutions on this case and found that they all printed No here.

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

    Yeah, my solution fails on 218 and fails locally for 5 1 0. :(

    Edit: resubmitted with a fix for this and got AC.

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

    Yes, it has to be the case where you are expected to take a turn at the starting cell itself.

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

      Yeah. My code also failed this test case. Although they should have added this test in pretests itself.

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

    The person who hacked someone with this test is Thanos of our generation. With one click he killed half of AC solutions on D.

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

Hard code for D and Good test 218

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

The absent of test case 218 in pretest seems to f**k participants up deliberately, right?

edit/ I didn't get that 218 was hack data. It seems that it was not deliberation, just failure to consider corner case

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

    me too. 0 1 1 1 1 \n 0 1 1 1 1 \n 0 1 1 1 1 \n 1 1 1 1 1 \n 1 1 1 1 1 \n it should be moving from {1, 0}

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

After the contest ended, I received an e-mail from noreply@codeforces.com saying that my solution for problem A 'significantly coincides' with a solution from other user. I entered his profile that was on the e-mail and checked his solution. It is quite similar, it uses the same idea, but this is a simple ad-hoc problem, and I'm pretty sure a lot of other people must have made similar solutions.

Anyway, the email said "If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details". Well, there obviously was no source published before the competition, and I just solved it by myself, and considering it was an easy problem I'd not be surprised that many similar solutions exists.

What can I do? I'm from Brazil and that profile is from a random guy in China, and as it was the easiest problem and most people solved it pretty quickly there's no way we would have gotten the same code on purpose.

The e-mail says "Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.". But it wasn't a violation, obviously a problem that occured, what could I do to remove this violation?

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

The round was quite unbalanced. My friend has got only 72 points more than me, but he's 500 places higher. Guess the author should learn from tourist how to make BaLaNceD contests.

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

There is no test case against int overflow in D...

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

Can someone explain problem B pls?

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

    We can take every present into account separately. There are totally 2^m ways to place. Obviously, we can not take the way of "all the box is empty", so there are (2^m-1) reasonable ways. Every present is irrelevant. So we can get the answer : (2^m-1)^n

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

i solved B using,total ways — invalid ways, i calculated invalid ways using inclusion-exclusion principle, which is sum r=1 to n ( nCr * 2^((n-r)*m) — 1)* (-1)^(r+1) which reduces to (2^(m*n) — (2^m-1)^n — 1) also total ways = 2^(m*n) — 1 .......substracting 1 for empty sequence hence valid ways = total ways — invalid ways = (2^m-1)^n.

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

Hey, can any of you guys help me with problem C ?

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

    first thing to notice that is highest numbers must be in one column,then as first row gets bigger number then put lowest in it, this is the most optimal way to put numbers.do it column by column.

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

Java BigInteger became useful for problem B. I used the same formula (2^m-1)^n. Here's my JAVA code: 62824862

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

Aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

(found a mistake in D after 50 min debugging during the contest and 2 hours after the end)

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

Sorry to bother you. Today (yesterday?) At the contest, someone coder_aditya copied my decisions from the open (I confess, it's my fault) source in ideone. So, this unscrupulous user completely copied my decisions on Problem A (62787915 and 62785873) and on Problem C (62803225 and 62803022). For an unclear reason, he first sent out full copies (why ???) and then edited the original code with trivial changes, receiving OK for tasks A (62813924) and C (62814398). In addition, task B was also counted as accomplished from him, so I won’t be surprised if he stole it from someone. I ask you to take action, because in the end I was left without a rating, and after editing other people's decisions he got a little rating.

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

Finally back to purple!!!

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

I want to ask a question, why the testcase's answer is no? 

4 7 8
2 2 
2 3
3 2
3 3 
2 5
2 6
3 5
3 6

It starts from (1,1) and turn right at (1,7).After walking across the big circle, it returns to the original point (1,1). then it goes on and turn right at (1,4) and end at (4,7).

All points has been visited. And at every point it turns right at most once.

Do I misunderstand the problem?

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

    The announcement specifies that you can only visit each cell once.

    "The doll should visit all cells without obstacles exactly once"

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

      Thanks for your answer!

      But If the problem becomes what I said, what's the answer?

      I have an idea, but I don't know whether it works / how to prove it.

      1. check how many components it has, it must equals to 1
      2. check how many points with one degree, (1,1) is not included. If there are two or more. We get "no"
      → Reply
»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Congratulations to you and me both for our first contest.

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

Great conto

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

Hello MikeMirzayanov and Cirno_9baka. So my friend dewitast got an issue that her rating was changed when she participated in this contest. You can see that, she is not eligible for div 2 rated contest (she already master when joining this contest, of course you can check it by yourself in the last contest in her profile). She already contacted both of you and she haven't hear any good news from you. Well she is not a vocal person, so I'm here to help her. Thanks :)

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

I was checking the solution for problem D of some people and I found that one of the accepted solution fails the following input.

Input:

2 2 1

1 2

This input should give an output "No", as I have checked with some other accepted solutions. But the following AC submission gives "Yes" :|

→ Reply