pwned's blog

Codeforces Round 987 (Div. 2)
By pwned, 2 months ago, In English

Hello Codeforces!

We (pwned, ACGN, HappyPacMan, maomao90, AverageDiv1Enjoyer, and trunkty) are thrilled to invite you to Codeforces Round 987 (Div. 2) on Nov/15/2024 15:35 (Moscow time) (note the unusual time)! After more than two years of preparation and nearly thirty problems on our shortlist, our contest is finally here for your enjoyment!

In this round, you will help Penchick as he embarks on a world trip through the Philippines, Indonesia, and even through the Australian beaches and attempt six problems in two hours!

The score distribution will be as follows: $$$500-1000-1500-2000-2500-3000$$$.

This round would not be possible without the support of everyone behind this round:

Lastly, we thank MikeMirzayanov for creating the incredible Codeforces platform, where many of us have engaged in friendly competition, honed our problem-solving skills, and forged lasting friendships throughout the years!

From our keyboard to yours, we (and Penchick) wish you good luck, positive delta, and an exciting competition experience!

Note: There is at least one interactive problem, so please read the guide for interactive problems if you are unfamiliar with them.

UPD: Editorial has been posted, go check it out!

UPD: Congratulations to the winners!

Div. 1 + Div. 2:

  1. tourist, as expected, fully solving all problems in 53 minutes
  2. antontrygubO_o, who did so just 2 minutes later
  3. noimi
  4. A_G
  5. Pyqe
  6. StarSilk
  7. dyppp
  8. kotatsugame
  9. busamate
  10. tarjen

They, along with 8 other contestants, are the only AKers (full-solvers) in the whole contest!

Div. 2 only:

  1. LGlcx, who full-solved in 100 minutes!
  2. Sky_Maths
  3. G2Esports
  4. boboquack
  5. ac_de_taffy
  6. Jack.YT
  7. Alex2184
  8. MrPizza
  9. priyanshu.p
  10. CC_cccc

We hope you all enjoyed the round!

Want more of Penchick?
  • Vote: I like it
  • +537
  • Vote: I do not like it

»
2 months ago, # |
← Rev. 5   Vote: I like it +22 Vote: I do not like it

pwned orz!

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

Omg “highschool CPers” CF round!!! Expecting an interesting problemset!!

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

:penchickpride: pwned orz!!

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

:pinoypride: penchick pwned orz!!

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

I waddle for the fish!

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

pwned orz!!

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

As a taster, I found the problems very delicious

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

    So true, the flavortext is very delicious! Especially the diverse cuisines and dishes featured in the round!

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

      I admire you, testers. It looks like this round will be cool. I'll give it my all this round.

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

hi orz ppl @pwned @culver0412

i will definitely join! :penchickcheer:

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

As a tester, maomao90 is gay

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

As a setter, I'm surprised Penchick hasn't had jet lag yet.

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

pwned orz

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

excited for penchick-pilled round !!!!! (pwned orz)

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

As a tester, I'll let you in on some facts:

Facts

GL&HR!

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

as a participant, here is an obligatory penchick image that nobody has posted yet

penchick-squak

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

After more than two years of preparation and nearly thirty problems on our shortlist

Couldn’t be more excited to get into this

images

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

Excited to participate, pwned orz!

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

As a tester W round

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

as someone giving their advice in creating interesting problems, please upvote

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

As a participant, I love Penchick!

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

As a participant, I read all the comments and wondered why only one peng' has orange beak and why are the 2 rubik's cubes having 2 different "**shades of green**" ?!

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

duckforces

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

Hoping for the best Div.2 Round! Btw, the penguins are cute <3

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

penguinforces

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

So excited,hope that the problems are as cute as the announcement and the penchicks.

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

As a tester, good luck and

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

Penguiiiiiiiiiins

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

"Why is there no Div 4? The last one was 1.5 months ago..."

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

You for being an awesome member of the CF community! The "You" of this sentence is surprising!!!!!!!!

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

As a tester, after creating six problems for us, Penchick is now resting peacefully.

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

i will get another positive contribution with this comment

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

As a participant, I am not a tester.

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

Hope to comeback CM after this round.

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

omg NeroZein mentioned

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

Masters Masters Everywhere.

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

I think "note the unusual time!" should be bold and large font like

note the unusual time!
→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

pwned orz!

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

Oh,this Penchicks are so cute!

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

As a tester, did I come late? I kept asking Penchick for the delicious feast and almost forgot the time for this round.

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

Finally, a plush toys photo session in round announcement <3 Thanks, guys!

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

Penchick

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

I'm back :)

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

The way right penchick is saying Good Luck

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

Very cute!

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

what are penchicks?

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

So many people registering for this contest! Hope everyone +ve rating!

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

very good unusual time, very scary interactive problem, like from porcelain

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

NO way C is a real problem

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

This is true SpeedForces.

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

i choked really hard today. C is the worst C i ever met in a div 2 too

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

    Anybody forgot $$$3^2+4^2=5^2$$$ in contest? Note: I spent an hour remembering that lol

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

      Lol I had to spend some time remembering.

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

      i remembered the pythagoras but im too dumb

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

      I spent some time to figure out if there's a smaller triplet than $$$(3,4,5)$$$

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

i just spent 30 minutes searching for a mistake just to discover that i wrote cerr instead of cout

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

is D a graph problem?

edit : can you give some hints

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

    Yes.

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

      How did you solve it as a graph problem? I used

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

        I used a segment tree can you share your logic

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

          Can you explain your Solution

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

            just as said in the problem you can travel to larger elements in the left

            so first i calculated the prefix maximum for the array this will tell you what is the largest element that you can travel if only first operation is allowed now i created a segment tree that can give maximum in any range of array , then traversed the array from right to left

            if i am at an index i what is the value that i can reach anything smaller in the left from 1, prefixmax[i]-1 (as going to the prefix maximum will increase the scope of traversal in left ans the result will be even larger) so just calculate the maximum for this modify answer[i] with max(query(1,prefix[i]-1),prefix[i])

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

      I used dsu and set. Iterate from left to right, and for current val, all the left side larger than the val should be connected with current val (and we can do this recursively with dsu.find).

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

    At least my solution has nothing to do with graphs.

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

plz provide enough test cases

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

    Sometimes there is a deliberate shortage of provided test cases since otherwise the pattern to the problem would be obvious. Few test cases often indicates you just need to find a pattern yourself by working through some examples.

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

      ok understood thanks for your explanation . I try to find it by practicing more problems.

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

What is the solution for odd in C ?

→ Reply
  • »
    »
    2 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it
    Spoiler
    → Reply
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      n>=27*

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

      I realised this that 3,4,5 is the smallest pythagorean triplet but could not construct it

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

        1 10 26 can have same fillings as they have diff of square of 3,4 and 5. Also, we can set 27 and 23 with same fillings. Now we are only left with consecutive even length numbers {2,9}, {11,22}, {24,25} and {28, inf}. Set every 2 consecutive numbers with any same fillings [2,3] [4,5] [6,7].....

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

      how for n==25

      my code get AC for n>=27

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

        Yeah, it was a mishap in my mind. Edited to 27.

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

    there is a fixed pattern of length 27 291641087 in odd cases and then the remaining part becomes even.

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

    Asking for the same :(

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

    "1 3 3 4 4 5 5 6 6 1 2 7 7 8 8 9 9 10 10 11 11 12 12 13 13 1 2"

    works for 27 and beyond

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

      In your solution, 3 3 are adjacent while there distance is 1, How so?

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

        1 is a perfect square

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

          OK, I should visit KOTA(suicide Center) now :(

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

            Just hit the gym, watch some anime and you will be fine.

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

              Real hit the gym!!

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

                Your physique tells everything about you. Respect ++ Although I have seen one your solution in Edu section .. maybe in Binary Search course if I am not wrong.

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

        I literally implemented with the similar doubt. Actually the problem becomes quite complicated if the solution excludes similar adjacent elements.

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

          Exactly :(

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

            I challenge you to solve the problem when adjacent elements aren't allowed (i.e. you cannot use $$$1$$$ as a square)!

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

              Yes, I have solved this exact problem in the contest. Here are some observations I've made; please correct me if I'm wrong:

              1. if n is ODD then answer -1
              2. else we can solve for all mod of 8
              • for n%8==0 we can use 4 distance
              • for n%8==2 we can use one 9 at 0th then use the old 4 distance
              • for n%8==4 we can use two 9 at 0th and 2nd index and then old 4 distance
              • for n%8==4 we can use three 9 at 0th, 2nd and 4th index and then old 4 distance
              → Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 10 10 11 11 12 13 13 1 12

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

    Observe if we can have a Pythagorean triplet, where x^2 + y^2 = z^2 then the odd case can be done easily, and the smallest Pythagorean triplet = (3,4,5) so the gap should be minimum 25, so if start with 1, then last value should be >=26, and the smallest odd number for which it's satisfied is 27. So for all odd values >= 27 we can have a valid possible ordering.

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

    if(n>=27):

    1 on indices 0, 9, 25

    2 on indices 22, 26

    other as with even n: cur = 3 if i and i+1 is still empty then: a[i] = cur; a[i+1] = cur; cur++

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

Thank you very much for the contest.

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

what was the distribution technique for question 3rd... I thought of pairing in 2 because their difference will be 1 which is a perfect square but for odd N, i paired index 1 10 and 26 as their difference is also perfect sqaure.

Anyone ? whose solution got AC ? Thanks !!

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

    with this approach you get a dist of 2 between idx 25 and 27 since there is gonna be an odd number of elem between 10 26.

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

    you have to make sure [1, 10, 26] = 1 lets say, then [23, 27] = 2, so if n>=27 and odd this will work..

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

Is this correct for F? I was not able to submit it due to the fucking internet

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

Did thought about pythagorean triplet, and still choke at problem C.

Double the pain again.

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

    So can we find out a valid filling when n<101 and n is odd?

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

    Same brother, I didn't took the n=27 test case, so got wrong

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

the B problem has an issue with python solution did you ever test it with python? i always get TLE

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

    We tested it and it works on our side. Not sure what went wrong with your solution :(

    I submitted your solution in python 3 and it works. 291715567

    → Reply
»
2 months ago, # |
  Vote: I like it -13 Vote: I do not like it

LETSGOOOO! I solved 4!

Nice contest! C was a cool problem. Thanks for the round pwned ACGN HappyPacMan maomao90 AverageDiv1Enjoyer and all testers!

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

I submitted E in the last 10s of the contest but unfortunately got WA.

Anybody got an idea why this got WA on pretest 23?

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

    floating point inaccuracies can accumulate; floats are not accurate enough for this problem, you need an exact way to solve it.

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

      Man that's such a pity! I could've solve it >_<

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

Why does cpp23, cpp20 and cpp17 give different results for these solutions??

291657006 291656787 291655971

Code

nvm, overkilled it, realising it now that it could've been solved in a much more easier manner T_T

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

    Haven't looked into the code yet, but if the same code gives different results in different compilers, there's a good chance that it's undefined behavior and some hidden errors.

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

      yeah, tried looking for that, couldn't find so pasted the code here

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

I really thought I would end up screwing up this round because I spent way too long on B, but I pulled off C and D quickly enough :D

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

Did anyone else get Runtime error pretest 61 on E? Sys tests aren't happening and the suspense is killing me T-T

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

My solution:

[D]

Observation1: note the maximum value as mx, and the number to the right of mx will definitely reach mx.

Observation2: if a[i]>min(mxpos,n), all a[i,...n] can reach mx.

So we can maintain a variable pos and continuously execute the following process:

pos=posmx initially.

  • find min i (1<=i<pos) such that a[i]>min(a[pos,...,n])

  • update pos:=i, or break if no such i

So we found a suffix that can reach mx. Then recursively solve the sub-problem.

[E]

Consider reverse operation: add nodes from the given tree to make it a perfect binary tree.

DP. Note dp[x] as the minimum depth at which subtree x becomes a perfect binary tree.

Observing the process of adding nodes (from leaves to roots) is actually a classic Huffman tree.

So we can use greed+priority queue to process dp [son[x][i]] to obtain dp[x].

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

Great problem C, really like it! Thanks for the round :)

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

    Yeah, good one. Myself completely missed the 9,16,25 case

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

      You are still missing.. Thats actually [1, 10, 26], [23, 27]

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

Why is there such an important change in E so much later into the contest??? I was already working on the solution according to the problem statement by then, trying to write this complicated re-rooting dp code, and after submitting towards the end of the contest notice this change. How is this fair?? Please make this contest unrated.

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

    The roots of the trees have always been well-defined in the statement. The binary tree is rooted by definition.

    The clarification was made to point this out, and didn't change the statement.

    → Reply
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it -19 Vote: I do not like it

      What do you understand from this statement — "Since Penchick and Chloe are good friends, Chloe wants her tree to be isomorphic to Penchick's tree"? I don't know why whould you change a well known definition for your convenience. Please make clear problem statements.

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

        We did not change a well known definition for our convenience. The two trees are rooted, and rooted isomorphism is defined exactly as we did in the footnote.

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

    Footnote 2: A full binary tree is rooted tree, in which each node has 0 or 2 children.

    Combined with

    Footnote 1: A rooted tree is a tree where one vertex is special and called the root. The parent of vertex v is the first vertex on the simple path from v to the root. The root has no parent. A child of vertex v is any vertex u for which v is the parent.

    Is sufficient to define that the root of the binary tree is the top-most vertex.

    The root of Penchick's tree is defined as 1 in the statement "... with vertex 1 as the root".

    In footnote 3, isomorphism of rooted tree is clearly specified "Two rooted trees, rooted at $$$r_1$$$ and $$$r_2$$$ respectively, are considered isomorphic if there exists a permutation $$$p$$$ of the vertices such that an edge $$$(u, v)$$$ exists in the first tree if and only if the edge $$$(p_u, p_v)$$$ exists in the second tree, and $$$r_1 = p_{r_2}$$$."

    Hence, there are no issues with the original statement.

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

D can be solved with dsu. For each point, merge it with the point to the left of this point and with the highest height, and also merge it with the point to the right that is farthest away from it and with a height smaller than it. The answer corresponding to the set is maintained while merging. It can be shown that this merging is optimal.

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

    Can you please explain how did you develop this intuition? I thought about DSU but was not able to construct connected components in less than O(n²)

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

Is there any reason for the memory limit to be smaller than the size of the stack for max N in python? I had a very inelegant solution to D that failed due to stack not fitting the memory.

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

    Actually, there's no easy way to expand the stack size of Python on Windows, as the Python executable is already compiled with the default stack size (1MB, IIRC).

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

      eee you can, sys.setrecursionlimit(10**5) increases memory usage so I suppose also the stack limit, but with 256MB you can fit just about 10**5 and N is 5 times more in D.

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

        That function increases the internal recursion limit, but it does not expand the stack size of Python runtime.

        For example, running the following code with custom invocation will give you a stack overflow error (both in PyPy and Python). This means Python can't handle recursion calls nested just 10000 times, which indirectly shows Python runtime's stack size remains small even if you call sys.setrecursionlimit.

        import sys
N = 10_000
sys.setrecursionlimit(N + 100)

def f(n):
    if n == 0:
        return 0
    return f(n - 1) + n

print(f(N))
        → Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

C and D were interesting

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

All problems here are bangers!! E is my favorite, but F is cool as well

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

comeback CM now (probably)

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

Good Problems..

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

How is it that suddenly 2000+ people solved C problem in the last 20-30 mins? Hope the cheaters are found and removed!!

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

This was a really fun contest, with lots of interesting problems!

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

Will I get back to 1900 after rollback?

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

https://codeforces.me/contest/2031/submission/291676661

Can anyone let me know why my solution for B is wrong? I cannot find any edge case for this.

Please let me know why my solution is wrong, thank you very much

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

    When $$$n=1$$$, you didn't read the input array, which causes the testcases afterwards to be shifted.

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

      I spent so much time trying to figure out what is wrong with the algorithm LOL; never forget to read everything from cin before outputting the answer

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

      Thank you very much! I'd never make the same mistake!!

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

So many new accounts on top positions :(. One has to improve if they want to simply keep their rating (otherwise they will be in an equilibrium rating lower than their “true” rating. Maybe this is not a problem if the amount of Smurfs is constant between contests, but I feel like this one has quite a lot)

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

Making $$$2 \le k \le n$$$ i.e., asking subsequence of length atleast $$$2$$$ will make the problem $$$F$$$ as troll D2C ig ;)

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

nice round

only flaw is the statement of E is a bit misleading, I assumed the usual definition of isomorphic and got stuck (it seems that in such meaning it can be solved with tree decomposition with matrices, but I'm unable to make it clear)

my rating still did increase tho

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

sto sto orz orz

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

Good contest, thanks.

Also the problem F is amazing.

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

Congrats to programpiggy for finally reaching M!

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

Thanks for the contest! Participated virtually. Love problem C!

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

Loved solving the 3rd problem. Interesting problem.

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

How the heck did I get 9.8k official rank when there are only 8.3k official participants?? And I saw a guy in the standings list who is rated like 1k something, has the same rank as me, still got a +6 rating change meanwhile I got -46. Whats up with this

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

There is a cheat alert sent to me says that my code is similar to other codes (about 12 or 13 person), I didn't do that but of course my code will be similar it's an idea and it's my implementation for it of course another person made the same. So please let me understand what's your point of view. finally sorry for inconvenience.

→ Reply