DeMen100ns's blog

Codeforces Round #779 (Div. 2)
By DeMen100ns, 3 years ago, In English

Xin chào, Codeforces! (Hello, Codeforces!) ٩ (◕‿◕｡) ۶

Me, _FireGhost_ and SPyofgame are glad to invite you to Codeforces Round 779 (Div. 2), which will take place on Mar/27/2022 17:35 (Moscow time). The round will be rated for participants with rating lower than 2100. You will have 2 hours to solve 6 problems, one of which is divided into two subtasks.

In this contest, you will meet Kitagawa Marin and her friends Gojou, Juju and Shinju from My Dress-up Darling! We hope you will find our problems interesting. Good luck to you all! (ﾉ ◕ ヮ ◕) ﾉ *: ･ ﾟ ✧

We sincerely thank the following people for their contributions in the round:

Score distribution: $$$500-1000-1750-(1250+750)-2500-3000$$$

UPD: Editorial

Congrats to the winners:

  1. tourist
  2. disorientation
  3. A-SOUL_Official
  4. Geothermal
  5. oleh1421
  • Vote: I like it
  • +606
  • Vote: I do not like it

Comments Comments (210)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it +99 Vote: I do not like it

As a tester, f--k you SPyofgame.

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

Round is good.

Source: trust me dude I'm the authors' caretaker.

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

I'm only here because our beloved coordinator told me to

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

As a tester, I recommend participating in this round.

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

    Nice elephant!

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

as a person who suffers from their goddang Marin cult (and because I'm jalsol), please give me contribution

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

Monarchuwu orz

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

As the person whose tasks were rejected by DeMen100ns, I strongly recommend participating in this round.

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

As a tester, please give me contribution. Try not to cringe as long as you can.

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

orz KarD1m

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

why are there always contests on usaco weekend :(

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

I want to be pupil. I wish I will reach the pupil as soon as possible. Good luck to everyone. I wish everyone will do well in this contest. And I wish all newbies will pupil.

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

As the results of Vietnam Olympiad in Informatics (VOI) are coming very near, I wish all of the problemsetters who participated in VOI a wonderful prize.

Edit: The same goes for all the other Vietnamese participants.

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

hope that Marin won't cause me another trauma like VOI

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

goofy ass announcement made me skip round

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

My sincere appreciation for Marin Kitagawa <3

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

As a contestant f--k you SPyofgame

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

My rate-up darling!

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

We need an Emilia themed round in the future

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

Good luck and have fun.

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

I thought it was gojou from Jujutsu Kaisen :)

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

I start every contest hoping it will be better than my last. I hope I don't brick :)

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

Looking forward to this round, especially after I read, that there will be My dress up darling characters! Great anime, I recommend watching it! Good luck on contest!

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

Picture in the blog:

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

How are you going to make me choose between going to the gym and participating in this round.

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

Where's the gif from?

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

sus

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

why is everyone harsh on SPyofgame

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

RIP SPyofgame

rest in peace

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

DeMen100ns is so handsome

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

love you SPyofgame

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

Kitagawa Marin already hyped for this round. Good luck guys.

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

Monarchuwu orz

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

wuvforces.....

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

Judging by all the tester's reactions I think SPyofgame's problem statement had manga spoilers lmao.

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

    Ahaha, I pray not to be so, otherwise, I will f--k him too

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

    Fact: My problem F used to be d2A, d2B, d2C, d2D, d2E and now d2F

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

Anime collab ? My delta definitely will be positive.

Marin is best anime girl of 2022, even, Gigguk said this ! Thanks to authors

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

Marin is the top, and the others are photoshop.

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

Uwwuwuwuwuu

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

Want to view all blogs on Codeforces? Check this out

https://mirror.codeforces.com/blog/entry/101288

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

It is going to be the cutest contest that have ever been on CF

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

Hello, I'm new here. What are the cutout ratings for the different divisions?

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

    The round will be rated for participants with rating lower than 2100

    So yeah you're eligible

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

I hope that I can be master

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

    And I do it, thanks a lot

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

      good luck

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

        saying "good luck" after the result comes up... Interesting

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

          How could I know whether he will get good luck before the contest? He knows my meaning well because we come from the same nation and the same province.

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

permutationforces!

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

Is the name of problem D haiten code ??

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

hentaiforce

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

how to solve problem C ?

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

    check that there exists exactly one 1 check that v[(i+1)%n]-v[i]<=1 holds for all 0<=i<=n-1 check that v[(index_of_one+i)%n]<=(i+1) holds for all 0<=i<=n-1

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

      Feeling so angry i implemented above all condtions but forgot to check count of 1 should be 1.. damn!

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

        Yeah I feel you. I implemented all of these conditions but the one in the middle and had to come back an hour later to figure it out. So many unnecessary points wasted.

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

D2 should have worthed more.

Sad to see lots of people solved D2 ranked below people who don't.

maybe D1(750) + D2(1250) will be much better.

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

    How to solve D2?

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

      You can check if x is good with trie, $$$min(a_i \oplus x) = l$$$ and $$$max(a_i \oplus x)=r$$$. D2 solution: since $$$min(a_i \oplus x)=l$$$ you can just check $$$a_i \oplus l$$$ as candidates.

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

      Let's fix some index i. Now we assume that before performing operation (^ x) this element had value of l. Okay, this means that after permorming operation its value is l ^ x. So, if we do (A[i] ^ l) we get a possible value of x. How to check that value x is good? It's easy to see that after performing operation all our values will be distinct. So, minimum value of (A[i] ^ x) over all i should be l and maximum value of (A[i] ^ x) ovel all i should be r. How to check this? Using trie. Sorry for my bad English.

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

        Wonderful, I just fall into my D1 idea and try to optimize it, because I can not find out this idea.

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

          lbm364dl have provided a bit by bit solution below, which I think is an optimization of D1 idea.

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

how to solve C?I struggle with it for more than an hour:((((

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

errorgorn should have rejected more problems

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

Hints for D1 (Easy): Precompute the number of ones at every bit position for first $$$N$$$ natural numbers.

Then, for each bit position, compare the expected number of ones and zeroes. If $$$x$$$ had 1 at that bit position, the count of ones and zeroes would have been swapped. If it had 0 at that position, it would've stayed same. However, it $$$cnt[zero] == cnt[ones]$$$, there's no way of finding out if any swap did occur. Hence, this bit position is, in some sense, free.

Finally, $$$x$$$ has to be present in the array, since $$$0 \oplus x = x$$$. Iterate over the array elements to return any element which does not violate the non-free bit positions.

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

    discovered the solution few minutes before the contest's end, guess that's what i deserve for arriving late to the contest.

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

    Using the idea of free bits, you can also solve D2. Just iterate over all subsets of the free bits and try to use them in the xor answer. If every number of the array remains between l and r, then you have an answer. You can check my submission.

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

      This is really cool.

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

        Well, somehow I just realized this should TLE. The subset thing is $$$O((r-l+1) \cdot 2^{free})$$$ where $$$free$$$ is the number of free bits, and it should be around $$$10^{10}$$$ operations. I stop the iteration when it finds an element out of range, so I guess this happens many times. There may be some obscure math that can prove that I always stop a lot of iterations or just weak tests.

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

          Actually I tried to hack your solution, but failed. And then I realized that it is just theoretical but really hard to find a real case.

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

    Are there proofs that any element in array which does not violate the non-free bit positions will be the answer ? It's clear that one of them will be the answer, but why any ?

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

      Suppose you found a valid $$$x$$$ with $$$i$$$-th bit free and does not violate the non-free bit positions. Suppose $$$x$$$ is $$$0$$$ in the initial array ($$$x = 0 \oplus x$$$). The $$$i$$$-th bit being free means that it has the same number of ones and zeroes on that bit. This happens when you initially had a prefix of a multiple of $$$2^{i+1}$$$ numbers, so in particular, $$$2^i$$$ must be in the initial array (you had at least numbers between $$$0$$$ and $$$k \cdot 2^{i+1}-1$$$). If you have $$$2^i$$$ in the initial array, then applying the operation gives you $$$2^i \oplus x$$$ which must be in the final array. This number only swaps the $$$i$$$-th bit of $$$x$$$, which was free, so it still does not violate the non-free bit positions. Therefore, $$$2^i \oplus x$$$ is also valid.

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

        Thanks very much. That was a great answer. I finally understood all only just now.

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

        condition: "If you have 2^i in the initial array, then applying the operation gives you 2^i⊕x which must be in the final array." result: "Therefore, 2^i⊕x is also valid." I can't understand the reasoning, why we can get the result from the condition, could you please explain it more detailedly?

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

          I reread my comment and you are right, there's something off with that. It was kind of a circular reasoning. Let's try again.

          We know that if $$$x$$$ is a valid answer, then it must not violate the non-free bit positions. We still don't know anything about the free bits, we know there is at least one solution, nothing else. This is a necessary condition.

          We want to check the sufficient condition, that is, any $$$x$$$ that does not violate the non-free bit positions is actually a valid answer.

          To show this, we first notice that $$$set(a \oplus 2^i) = set(a)$$$ for any free bit $$$i$$$, where $$$a$$$ is the initial array. That is, the set of numbers will be the same (still $$$[0, r]$$$) if we XOR every number with $$$2^i$$$, where $$$i$$$ is a free bit. Why? Because, as mentioned in the previous comment, if $$$i$$$ is a free bit, then the size of $$$a$$$ is a multiple of $$$2^{i+1}$$$, which means that for each number with a $$$0$$$ in bit $$$i$$$, the equivalent number with a $$$1$$$ (everything else the same) is also in the array. This proves the equality since XORing by $$$2^i$$$ just swaps pairs of numbers like $$$p0q$$$ and $$$p1q$$$, and they are all in the array.

          Now, suppose $$$x$$$ is a valid answer. Then denote $$$a \oplus x$$$ as the final array. From the previous result we then have $$$set(a \oplus (x \oplus 2^i)) = set(a \oplus 2^i) \oplus x = set(a) \oplus x = set(a \oplus x)$$$, which means that $$$a \oplus (x \oplus 2^i)$$$ generates the same final array and is therefore also a valid answer.

          From this you can set or unset free bits as you like, and in particular, you can unset all of them and you have the claim in the editorial.

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

            Awesome! Now I got it, thanks a lot.

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

So difficult div2

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

This contest is a rubbish

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

151135032 I submitted a random solution on D1 and it passed pretest. Does pretests weak ? UPD : FST :))

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

I was confident in solving C until I looked at todays third! : (

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

What does 388535 mean, the title of problems D1 and D2 ?

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

This contest is sponsored by permutations

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

...

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

How does it happen that I notice a difference between the statement and input format for the second time this month? Perhaps I could help you test these things in advance?

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

Can I say that I am in love with Marin Kitagawa? Thanks for your time.

→ Reply
»
3 years ago, # |
  Vote: I like it +29 Vote: I do not like it
This contest in a nutshell
→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

The idea of considering parity and considering bits individually while solving bitwise problems really helps.

https://mirror.codeforces.com/contest/1634/problem/B

The above idea used in this problem helped me in today's D1 :)

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

    i remembered that problem too, but didnt solve d1 :(

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

can someone explain me why my code in d1 give runtime error on pretest2 ( look at the submission before the last one )

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

    You need to replace for(int i=0;i<n;i++) { at line 34 for for(int i=0;i<40;i++) { and you won't have runtime error. This was happened because size of arrays vars and need is 40 and if n>= 40 you are requesting a non-existent element of this arrays.

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

    Beside this I know, why your code gets TLE (Time limit exceeded). If it's interesting to know the reason, it is under the spoiler

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

      firstly thx so much on advice(it got ac :D) , but I just want to know why it give TLE when I broke the input values rather than wa , since I was inputting wrong values from a point

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

        Probably this happens because in some test case after breaking numerations your programme inputs some big value as n and wants to input then n values but this test doesn't have so many values. So your programme waits for them endlessly.

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

Whoever decided the name for D problem is a true man of culture. Respect.

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

Got my answer

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

Sucks to solve more problems but still have a performance difference of +350 with someone solving less :/

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

I Accepted the problem C without understanding the justification for the solution at all...

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

I feel like D is a little bit too standard?

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

    Solve numbers of D2 says it's not so standard.

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

    How to solve D1?

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

      It is provided that we can always convert [0...r] to array by xor for all test cases. So for each bit, we count its occurance in [0...r] as well as in array. If the count is changed we add current bit to xor value, otherwise we can skip it.

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

How to solve problem C ? (with proof of correctness please)

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

    you can shift input,to make first number in input 1(if there is not 1 answer NO),it means that N is first,then every next number can be at most one bigger than last(cuz after every shift by one in right it can increase not more than one .,u should check about there exist only one 1

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

      how do we know that we can always contruct the array if these conditions are true?

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

    when in the given array c[i]=1, it means at that moment n will be the first element inside the permutation because c[i]=1 means the first element is greatest ,after c[i]=1 we r confirm that the lowest value of c[i] should be 2 because no other element greater than n will come in the beginning and the greatest value of c[i] should be 1 greater than the previous one because it is not possible to increase the value by more than 1 just by adding one number in the starting of the permutation . so we r having lowest and highest values , we have to just check either these are following properly from i+1 to n and then from 0 to i-1. just assume your permuation is having nth element in the starting and after that what can be the range of next c[i]..

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

    There is exactly one cyclic shift that gives $$$1$$$ (when $$$n$$$ is the first element). We can start from this position (let it be $$$pos$$$) and iterate in the right direction (cyclically) until we process $$$(pos-1+n)$$$ $$$mod$$$ $$$n$$$.

    Each iteration denotes the movement of all permutation values one position to the right (the last element comes first). Let the current power be $$$p$$$, the new $$$1^{st}$$$ element should either be $$$<$$$ the new $$$2^{nd}$$$ element (increasing $$$p$$$ by $$$1$$$), or $$$>$$$ the new $$$2^{nd}$$$, $$$3^{rd}$$$, ..., $$$i^{th}$$$ and $$$<$$$ the new $$$(i+1)^{th}$$$ element ($$$i<$$$ the new position of $$$n$$$), which will give a new power $$$np$$$ in the range $$$2\le np\le p$$$.

    We can always construct a permutation satisfying the previous flow. Proof: Assume we represent each $$$>$$$ or $$$<$$$ constraint in the previous flow by an edge going from the larger to the smaller value. The resulting graph is acyclic and we can assign permutation values to its nodes by traversing in topological order.

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

How to solve E?

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

    Compute the answer for cells in decreasing order of $$$v_{i,j}$$$, starting from $$$n^2$$$ (the maximum $$$v_{i,j}$$$), for which the answer is $$$'M'$$$. Let's call each cell marked by $$$'M'$$$ so far, a winning cell. For every other cell, if there exists a winning cell having distance $$$>k$$$, Gojou can jump to that cell after the first move, guaranteeing him a win. If not, Marin wins (and we mark this cell as 'winning'). Checking this condition can be done by maintaining segment trees for diagonals.

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

Interesting difference gaps. Not very easy Problem A, not very hard Problem F. But nice contest, thank you, problem setters.

However, I poorly misread "the cuteness of concatenated string" as "the sum of cuteness of all selected strings" in Problem F and got stuck into it until encountered those unbelievably brief solutions... I could have done better TwT...

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

    Can I get your feedback for problem F ?

    I mean "How hard is this adhoc ?"

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

If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table to increase/decrease the constraints.

If you are not able to find a counter example even after changing the parameters, reply to this thread, mentioning the contest_id, problem_index and submission_id.

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

    Eh, dont you have problem F :<

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

      HeHe, was too lazy to write the checker. Moreover, people who attempt the last problem are able to debug it by themselves, so I skipped it.

      Do you want me to add it? (However, my generator won't be as good as yours, since you're the author).

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

        Eh, if you really want to add it then I can provide you with my validator, checker, generators, and tests.

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

For the ones confused by name of problem D. Here is the meaing.

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

    True Men of Culture. The author's Rental Girlfriend "parody" series is pretty great as well. It has 4 stupendous chapters so far.

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

396419 this one is better. Or this one 396084. So much ntr stuff, nice!

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

Codeforces Round 779: problems A-D1 explained

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

When you try to cheat and google the name of problem D, then everything goes wrong -_-.

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

I was just wondering — in the announcement it says that the round would be rated for users under 2100. However, it says that the round was unrated for me. I looked around at other participants and it was also unrated for them.

Just a bit unsure of if its just a processing thing or if the round wasn't rated for anyone.

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

    It is rated. What makes you think it's not?

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

      The contest has finished and it is at final standings — so ratings should have been added right?

      If you look at your profile on progress and look at only rated this is not the last contest — for you it is the TON contest.

      If you then switch from only rated to all, you can see this contest as the last one greyed out and it says unrated.

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

        It usually takes a few hours until the rating changes are applied.

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

          Thanks, that makes sense now.

          Most of the other contests that I've done released the rating changes when the final standings were released I think.

          I guess they just need to process the data or smth.

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

The problems are all about the "permutation"

how difficult!

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

f--k you SPyofgame

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

I just received a message from the system telling me that my solution(151118707) for the B problem is similar to notnotTehlka/151113394. I had reviewed the code of both the people; the fast io template of python is matching. Moreover, the solution was simple and trivial. So, Please look into the matter.

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

    Dude, it's obviously the same solution as the notnotTehlka's one...

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

      But it is a straightforward question it's the obvious answer is what I wrote.

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

One of the most terrible rounds I have seen.

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

    Eh, why tho :< Can I have your feedback for better improvements in the later rounds ?

    It is the first time we set a round on codeforces so there might be some advantages we can further improve, some disadvantages that we need to learn to fix.

    I don't mind learning from feedback but I think you should go into detail about what made you annoyed.

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

      Actually I didn't take part in this round. I just felt it hard to understand the statements when I reviewed it. Maybe it's because of my poor English.

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

If you cannot represent a problem with a clear concept DO NOT TRY TO DO SUCH NONSENSE!!

FACT Problem A

Never want to see you again in any contest @SPyofgame

.... you!

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

    ehh, I am not the tester of this problem but you can still give feedback to me tho. I will try to improve myself along with these experiences too.

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

Could someone help me understand why this code is getting TLE? 151271702

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

The posts that say dirty words are placed on the top, while the posts that speak regularly are hidden.

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My reaction to this contest blog on the front page:

Thanks for reminding me of the contest where I resubmitted to a question not knowing it skips the old submission and as a result lost tons of ranks due to it

→ Reply