pwned's blog

Codeforces Round 987 (Div. 2)
By pwned, 2 weeks 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
  • +529
  • Vote: I do not like it

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

pwned orz!

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

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

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

:penchickpride: pwned orz!!

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

:pinoypride: penchick pwned orz!!

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

I waddle for the fish!

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

pwned orz!!

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

As a taster, I found the problems very delicious

→ Reply
  • »
    »
    11 days 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
    • »
      »
      »
      8 days 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
»
11 days ago, # |
  Vote: I like it +8 Vote: I do not like it

hi orz ppl @pwned @culver0412

i will definitely join! :penchickcheer:

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

As a tester, maomao90 is gay

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

    Hormat 🫡 maomao90 🐱 for contributing to civil defence 👮 and protecting 🙏 us from people like iLoveIOI 🥶

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

      Hormat 🫡 maomao90 🐱 for contributing to civil defence 👮 and protecting 🙏 us from people like iLoveIOI 🥶

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

        Hormat 🫡 maomao90 🐱 for contributing to civil defence 👮 and protecting 🙏 us from people like iLoveIOI 🥶

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

    Oh, really?amazing! ! !

    → Reply
»
11 days 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
»
11 days ago, # |
  Vote: I like it +8 Vote: I do not like it

pwned orz

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

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

→ Reply
»
11 days 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
»
11 days 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
»
11 days 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
»
11 days ago, # |
  Vote: I like it +11 Vote: I do not like it

Excited to participate, pwned orz!

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

As a tester W round

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

    As a unique problem idea-er, W round.

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

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

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

As a participant, I love Penchick!

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

    As a participant, i love high rating

    → Reply
»
9 days 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
»
8 days ago, # |
  Vote: I like it +8 Vote: I do not like it

duckforces

→ Reply
»
8 days 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
»
8 days ago, # |
  Vote: I like it +14 Vote: I do not like it

penguinforces

→ Reply
»
8 days 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
»
8 days ago, # |
  Vote: I like it +30 Vote: I do not like it

As a tester, good luck and

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

Penguiiiiiiiiiins

→ Reply
»
8 days 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
»
8 days 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
»
8 days 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
»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

i will get another positive contribution with this comment

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

As a participant, I am not a tester.

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

Hope to comeback CM after this round.

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

omg NeroZein mentioned

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

Masters Masters Everywhere.

→ Reply
»
7 days 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
»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

pwned orz!

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

Oh,this Penchicks are so cute!

→ Reply
»
7 days 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
»
7 days 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
»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Penchick

→ Reply
»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm back :)

→ Reply
»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

The way right penchick is saying Good Luck

→ Reply
»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Very cute!

→ Reply
»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

what are penchicks?

→ Reply
»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

NO way C is a real problem

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

This is true SpeedForces.

→ Reply
»
6 days 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
  • »
    »
    6 days 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
»
6 days 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
»
6 days 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
  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes.

    → Reply
    • »
      »
      »
      6 days 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
      • »
        »
        »
        »
        6 days 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
        • »
          »
          »
          »
          »
          6 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Can you explain your Solution

          → Reply
          • »
            »
            »
            »
            »
            »
            6 days 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
        • »
          »
          »
          »
          »
          6 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Spoiler
          → Reply
    • »
      »
      »
      6 days 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
  • »
    »
    6 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    At least my solution has nothing to do with graphs.

    → Reply
»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

plz provide enough test cases

→ Reply
  • »
    »
    6 days 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
    • »
      »
      »
      6 days 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
»
6 days ago, # |
  Vote: I like it +3 Vote: I do not like it

What is the solution for odd in C ?

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

      n>=27*

      → Reply
    • »
      »
      »
      6 days 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
      • »
        »
        »
        »
        6 days 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
    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      how for n==25

      my code get AC for n>=27

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

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

        → Reply
  • »
    »
    6 days 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
  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Asking for the same :(

    → Reply
  • »
    »
    6 days 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
    • »
      »
      »
      6 days 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
      • »
        »
        »
        »
        6 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        1 is a perfect square

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

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

          → Reply
          • »
            »
            »
            »
            »
            »
            6 days 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
            • »
              »
              »
              »
              »
              »
              »
              6 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Real hit the gym!!

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                6 days 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
      • »
        »
        »
        »
        6 days 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
        • »
          »
          »
          »
          »
          6 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Exactly :(

          → Reply
          • »
            »
            »
            »
            »
            »
            6 days 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
            • »
              »
              »
              »
              »
              »
              »
              6 days 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
  • »
    »
    6 days 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
  • »
    »
    6 days 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
  • »
    »
    6 days 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
»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you very much for the contest.

→ Reply
»
6 days 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
  • »
    »
    6 days 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
  • »
    »
    6 days 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
»
6 days 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
»
6 days 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
  • »
    »
    6 days 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
  • »
    »
    6 days 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
»
6 days 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
  • »
    »
    6 days 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
»
6 days 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
»
6 days 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
  • »
    »
    6 days 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
    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
6 days 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
  • »
    »
    6 days 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
    • »
      »
      »
      6 days 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
»
6 days 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
»
6 days 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
»
6 days 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
»
6 days 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
  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

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

      → Reply
»
6 days 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
  • »
    »
    6 days 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
    • »
      »
      »
      6 days 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
      • »
        »
        »
        »
        6 days 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
  • »
    »
    6 days 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
»
6 days 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
  • »
    »
    6 days 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
»
6 days 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
  • »
    »
    6 days 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
    • »
      »
      »
      6 days 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
      • »
        »
        »
        »
        6 days 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
»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

C and D were interesting

→ Reply
»
6 days 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
»
6 days ago, # |
  Vote: I like it +3 Vote: I do not like it

comeback CM now (probably)

→ Reply
»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Good Problems..

→ Reply
»
6 days 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
»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Will I get back to 1900 after rollback?

→ Reply
»
6 days 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
  • »
    »
    6 days 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
    • »
      »
      »
      6 days 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
    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
6 days 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
»
6 days 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
»
6 days 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
»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

sto sto orz orz

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

Good contest, thanks.

Also the problem F is amazing.

→ Reply
»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Congrats to programpiggy for finally reaching M!

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

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

→ Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Loved solving the 3rd problem. Interesting problem.

→ Reply
»
4 days 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
»
42 hours 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