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

Автор Cirno_9baka, 4 года назад, По-английски

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.

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

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

It's the contest season again :D

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

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

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

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

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

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

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

    I hope I can do that. Good luck!

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

    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.

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

Best of luck for your first contest

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

How short the announcement is!

However, hope your first round will be successful!

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

Request for This contest :: Please make large inputs downloadable

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

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

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

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

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

Do you think this round will be the strongest?

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

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.

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

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$$$.

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

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

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

Good luck with your first contest!

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

I smell math problems O_o

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

UwU

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

I hope the round contains some basic graphs problems

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

Thanks for the contest :)

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

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

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

[Deleted]

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

i hope statements wiil be without anime

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

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

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

A speed typing test?

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

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

Speed Test :/

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

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

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

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

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

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

      care to explain ?

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

        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.

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

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

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

        I have added explanation sorry it took me long time

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

        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.

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

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

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

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

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

How to solve D?

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

    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.

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

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

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

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

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

        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).

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

        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

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

How to solve D ?

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

    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.

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

Perfectly imbalanced.

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

    Did you find what is test case 4?

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

      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.

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

This was perfectly imbalanced round.

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

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

    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.

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

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

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

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

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

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

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

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?

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

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

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

      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. :(

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

        I also implemented using upper_bound but got TLE on case 4

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

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

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

      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.

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

        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)...

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

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

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

    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

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

    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.

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

      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.

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

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

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

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

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

      Can you exaplain how did you reach this equation ?

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

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

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

        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.

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

        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

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

      i used the same thing but wrong answer on pretest 3

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

        Maybe your fastpow is error

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

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

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

            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

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

    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

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

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

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

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).

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

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

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

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

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

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

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

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

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

touhou round so hard q.q

What is test 7 in D?

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

D is a debugging nightmare...

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

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

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

    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.

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

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

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

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

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

    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

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

    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.

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

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

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

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.

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

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]?

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

    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

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

      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

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

        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.

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

Disgusting problem D

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

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

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

Amazing Round .

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

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.

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

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

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

    How about python? Time to learn a new language

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

    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.

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

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!

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

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

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

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

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

      Main site gets attacked, light site has bugs

      balanced?

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

      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...

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

Who else forgot n=1? :)

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

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

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

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

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

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

    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.

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

I missed the DDOS attack this round :(

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

Upvote if you got the solution to C from sample

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

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

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

Deleted

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

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...

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

Aaaaaaaannndddd.... WA218!

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

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

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

Поменьше бы таких раундов...

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

Can you explain your thought process for B?

Like from when you saw the problem

IMO C was easier than B

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

    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

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

    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.

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

problems are very interesting. I really like it!

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

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.

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

I guess that one Specialist tester wasn't enough.

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

F seems to be interesting.

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

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.

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

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.

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

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

    UPD: Accepted with 6 TLE attempts..XD

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

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

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

    You will do better next time, keep it up

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

    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 :/

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

    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.

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

      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".

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

      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.

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

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

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

Anyone got what pretest 4 is? Please share

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

How to solve E?

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

    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.

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

      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?

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

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

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

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.

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

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

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

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

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

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

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

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

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

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

Hard code for D and Good test 218

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

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

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

    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}

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

After the contest ended, I received an e-mail from [email protected] 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?

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

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.

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

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

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

Can someone explain problem B pls?

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

    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

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

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.

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

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

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

    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.

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

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

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

Aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

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

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

Прошу прощения за беспокойство. Сегодня (вчера?) на контесте некто coder_aditya скопировал мои решения с открытого (каюсь, сам виноват) исходника в ideone. Так, этот недобросовестный пользователь полностью скопировал мои решения по задаче А (62787915 и 62785873) и по задача С (62803225 и 62803022). По неясной причине он сначала отослал полные копии (зачем???) а затем отредактировал оригинальный код с тривиальными изменениями, получив OK за задачи А (62813924) и C (62814398). К тому же задача B у него также засчитана как решенная, так что не удивлюсь если он и ее у кого-то украл. Прошу принять меры, так как я в итоге остался без рейтинга, а он после редактирования чужих решений поднялся.

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

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.

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

Finally back to purple!!!

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

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?

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

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

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

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

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

Congratulations to you and me both for our first contest.

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

Great conto

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

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 :)

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

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" :|