0doO's blog

Codeforces Round 939 (Div. 2)
By 0doO, history, 7 months ago, In English

Ciallo, codeforces～(∠・ω< )⌒☆

We are pleased to invite you to participate in Codeforces Round 939 (Div. 2), which will start on 13.04.2024 17:35 (Московское время).

The problems are from Otomachi_Una and me.

This round will be rated for participants whose rating is below 2100. Participants with higher ratings may participate out of the competition.

You will be given 6 problems and 2 hours to solve them. We hope you find them interesting.

We would like to thank:

Score distribution: $$$500-750-1500-1750-(1500+750)-2500$$$

Good luck on the round and high rankings to everyone!

UPD: Editorial out.

UPD: the winners

Div. 1 Div. 2
BurnedChicken zjy114514
StarSilk King_of_Beggars
maspy _MyGO_Tomori_
415411 LegendaryGrandmasterLjm
Rubikun naniak

Photo of authors (unfortunately, I can't come, so my profile is shown in the picture): photo

UPD: The rating changes for Educational Codeforces Round 164 will be applied after this round.

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

»
7 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Auto comment: topic has been updated by Otomachi_Una (previous revision, new revision, compare).

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

Auto comment: topic has been updated by 0doO (previous revision, new revision, compare).

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

have mixed feeling of looking at pics.. registering contest written by literal 7-th grader (redcoder) from china which clearly 10^10 smarter than me.

why Chinese are so smart.

→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it +120 Vote: I do not like it
    As a tester and schoolmate of Otomachi_Una...
    → Reply
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +62 Vote: I do not like it

      Well that makes me feel much better..

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

      that feeling when I saw my high school's uniform showing up on codeforces...

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

      We are both in the same grade. One is cyan one is red. How are you guys so good? Teach me the ways please.

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

    super DNA :)

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

    When author of this competition in such age made problems in codeforces, than I can't even imagine about our compare (He is my age)

    RESPECT FOR HIM!!!! MY ADMIRES!!!

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

    But why one auther comes from Japen?

    Or it just a joke?

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

    They don't all have top talent (although they are generally quite talented), but it's more because of their strong interest in programming. In addition, they join the school's training camp during middle school, where they are trained by teachers and sometimes even skip classes to train.

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

    I think that it may be because of China's huge population. You know, China has about 20% of the population on Earth. It is common that some of them are gifted. Besides, a big population also means that you can easily find friends who share common interests and dreams with you, just like on Codeforces or in Competitive Programming. By chatting with those friends and exchanging learning experiences, people can learn more from each other.

    And that is why I really appreciate the communicating platform, various interesting problems and their corresponding tutorials that Codeforces provides to me. It offers equal opportunities for every one to contact with peers and learn useful skills.

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

    An old legend says: "Being chinese is a cheatcode"

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

    Chinese is not smart, such as me.

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

    Redcoder's rating is 2400 and yours is 1411. dude! He's less than twice as smart as you, don't worry.You could be a Redcoder in the future.

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

As a tester,Otomachi_Una is very cute :)

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

As an author, give me Contribution!

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

    Huge thanks to everyone who contributed! Let's jump into the fun of problem-solving together!

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

Me looking at the pic and wondered which rock had I been living under when I was grade 9 i.e. 11-12 years ago...

Kudos to the youngsters, and hope the contest run well.

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

    So true. :(

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

      Bro says this while being in 9th grade himself

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

        doesn't make it less true

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

        wait how'd u know he is in 9th grade? Is there a secret society of codeforces who are in 9th grade? /s add me too

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

Ciallo～(∠・ω< )⌒★

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

qrz

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

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

UWU

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

As a big fan of yuzusoft(see my id), i will definitely enroll it though i have 3 college experiments tomorrow. Ciallo~

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

    Why there is no Yoshino in problems ToT ... I supposed it was a party for all yuzu characters, while it turned out to be nene solo TwT, and I gained a rating drop due to be uncommon with mathematical induction....

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

Yu...Yuzu soft fan?

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

Wish everything goes well!

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

Wish everyone gain more ratings, and me too :)

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

As a tester, I can confirm that round has some nice problems.

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

    Every round , always say. Div2 is hard for me , hahaha~~.

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

Cute pfp so I'll take a chance ^^

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

As a tester, I ask you to:

  1. Play Omori to be as op as Yahia_Emara

  2. Play Hollow Knight to be as op as Octagons

  3. Downvote Heap_OverFlow for farming contribution

  4. Give me contribution

→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it
    1. Done [but I am still not op :( ]
    2. Pending..
    3. Done
    4. Done
    → Reply
»
7 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Hi! From Vietnam with love <3

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

i need to study more

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

Nice picture! pretty sure it will be a good contest:")

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

OMG! Unrated tester yurongyi0504

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

As a tester, I hope everyone enjoys the contest!

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

"unfortunately, I can't come, so my profile is shown in the picture" sad

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

Otomachi_Una round. les go

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

Ciallo～(∠・ω< )⌒★

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

yuzusoft round(

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

clear and short description we like it ...Ciallo～(∠・ω< )⌒★

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

It seems to be the same account.

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

Please I need cm :)

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

Ciallo～(∠・ω< )⌒★

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

OMG Huafu jvxue!

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

when i see ciallo i know it's an uncommon round

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

I think I need to go to the library and play this round. Ciallo～(∠・ω< )⌒★.

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

Now imagine what the comment section will be like if it was a girl

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

    wut

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

      Having a photo in public without getting any nasty comments on appearance is very nice. I never got that as a female on algo community online which made me kind of jealous tbh

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

        Admins delete those comments and put commenters in read only mode.

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

          she didnt say whether she got them here, or somewhere else.

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

        oh. im sorry you had to face that

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

Who is this anime cartoon characters?

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

    Ayachi Nene(left) and Kariya Wakana(right).

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

Ciallo～(∠・ω< )⌒★

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

我真是服了你们这种柚子厨了。

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

What if my rating is now < 2100, but if they give me a rating for the previous round, it will become > 2100 and I will not re-register for this round, will I write a rating or not?

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

Ciallo～(∠・ω< )⌒☆

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

score distribution?

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

Ciallo～(∠・ω< )⌒

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

wow

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

It is getting late to publish score distribution!

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

upvote!!

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

I hope the problem statements are short and clear.

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

西亚洛～(∠・ω< )⌒★

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

Auto comment: topic has been updated by Otomachi_Una (previous revision, new revision, compare).

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

Auto comment: topic has been updated by Otomachi_Una (previous revision, new revision, compare).

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

cute/qq

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

Auto comment: topic has been updated by Otomachi_Una (previous revision, new revision, compare).

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

Hope this contest will be best for everyone. Best of luck guys.

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

operationforces

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

Constructiveforces.

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

A question regarding problem D sample cases, did getting WA on test 2, 3 which are given in the statements used to always give penalty ?

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

C is not a good problem.

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

    It actually was a great problem because it penalized the guessforces squad.

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

      I am confused what is the correct way to come with a solution then ?? What I usually do is based on the problem statements and output I try to figure out any pattern, and once I find it, I dry run it on several testcases to check its validity. But since you are pretty experienced so would you like to explain me the correct way of solving the problems and coming up with correct solution ?? Thanks.

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

    it's easy to guess the wrong answer i think.

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

    Because your "beating around the bash" didn’t work, doesn’t make it a bad problem

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

the worst C i have ever seen

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

    Such tasks provide basic ideas and constructions for an inexperienced person. Stop thinking about the rating lol

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

      no worries about the rating just an opinion

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

      whats the basic idea here ?? Is it that to make a matrix sum maximum, fill it with row-column manner ??

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

D is actually not too hard, but it's somehow painful to implement

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

    Wtf is the solution to D? I thought about bitmask dp, but no idea tbh.

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

      Just use backtracking LOL. Generate all subset and try to use the operation on those subset. It's easy to see that for each consecutive subset, its maximum sum is the sum of that subset itself, or (size of subset) ^ 2

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

        Generate all subsets of what?

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

          Sorry, I forgot to say. Generating all subset such that you will only use operations on those subsets. The key idea is that for example, you have an subarray with x elements, you can always make the sum of this array to be at least x * x by making all the elements equal to x. The construction is not hard to think if you write on the paper, but the implementation is... I don't know

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

      It is cubic dynamic programming on ranges (segments), but construction of answer takes exponential time and space since size of answer is exponential

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

        I only come up with the DP implementation when the contest has like 5 minutes left :(. At first I'm going to do it recursively

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

    that's right, my idea came in 5 minutes after reading this problem.

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

problem C in a nutshell : Wrong answer on pretest 2

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

    for real.. made 7 submissions :)

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

      I did 6 submission increasing closer to optimal construction but was not enough...

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

        yea same here. Figured that I had to do Type-1 operation till (i think) n/4 rows. But still pre-tests failed :(

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

ok, what was the edge case for C?

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

https://codeforces.net/contest/1956/submission/256521913

Can someone please tell me why do i get wa on pretest 6?

Basically my idea is that we can construct a sequence of operations that sets everything on interval of lentgh n to n

Then i do dp to get the best division

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

why does this retarded code for F runtime error i will kms 256536946

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

Feedback on the problems:

  • A & B: Both nice easy problems. However, it seems that difficulty of A = B.
  • C: Interesting constructive problem. The key is to observe the pattern of the final verdict of the matrix, then the construction is easy.
  • D: Not my favorite but okay. The data range gives a huge hint, and the method of using dp to calculate the answer is trivial. The implementation is a little too heavy (at least for me). And the pretests seem weak. (There are only 11 pretests. Why don't the authors use multi-cases?)
  • E1: Good brute-force problem. By simulating some small cases, especially the case when the ring has been reduced to a chain, you can come up with the key idea. My favorite problem from this round. However, the pretests seem weak.
  • E2: I don't really get the main idea of setting the harder version. Just by brute force, I passed it again. Maybe because of the weak pretests?
  • F: Not read.

In all, this round seems to be a good one (if the pretests are strong). Thanks to the authors!

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

    For D, I think the $$$5 \cdot 10^5$$$ upper bound on operations made it too IO-heavy for checker to make multitest.

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

    Actually we come up with the idea of E2 first, but it was too difficult to solve without the hint E1 provide, so we just add an easy version. In fact, it can be proved that brute-force only need $$$ O(nV^{\frac{1}{3}}) $$$ to solve the problem, so it's possible to solve E2 by using code of E1.

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

Figured out a solution for c, but contest is over by 1 minute.

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

Too large problem statements for A and B. And difficulty gap between B and C is huge. Getting big negative delta :(

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

    it took me 8 min just to read and understand what the statement is asking...

    and solution was pretty easy but statement is too long

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

C made me played like a fool. Haha, being outsmarted by youngsters...

Late submissions were when I realized how beautiful and simple the solution was, and I wished I solved it sooner.

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

    Can you explain how you came up with the correct approach for the problem C ?? My strategy was like first, apply first operation in all n rows. Now starting from first column check if the sum of the column is less than "n*(n+1)/2". If it is then the second operation should be applied. So the total number of operations applied were "n + cnt_col". But when the contest was over and I saw the further testcases then I realised the correct way to maximise the sum. So my question is, how did you come up with the correct solution in the first place ??

    Because seeing this type of solutions now I've started fearing and getting anxious that would I even be able to come with such smart and clever solutions ever ??

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

      I actually got into the same mental trap as you, and took a very long while testing locally and observing my own output to figure out my errors.

      Spoiler

      No advice on constructive problems as a whole either. I'd just say that let your imagination grow wide, experiment with many things, and also simultaneously hone your instincts at detecting things going right.

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

        Sorry, I by mistake downvoted you. You really helped me. Thanks.

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

          Mistakes happen, I won't mind that. Glad I could help.

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

      For what it's worth, I also got WA at first, and with the same strategy as you. But, after getting WA, I tried the case of $$$n = 3$$$, which gives useful intuition for the other cases (the optimal final matrix you want to get). Then, I tried $$$n = 4$$$, but couldn't do it in $$$\le 8$$$ operations. Then, I drew out the entire thing for $$$n = 4$$$, and stared at it for 5 minutes or so before finally realising that "oh I can just overlay stuff". In my opinion, the last part was the hardest one, because everything before that can be done using trial and error, but this requires a "flash of inspiration", so to speak.

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

I hate the long story statement of A. long statement is ok in long contest only (:

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

    Exactly!

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

    Agreed. Bro it made my mind so fuzzed up that I had to solve it by ITERATION! And that too in 17 mins. I was like: this contest is OVER for me until I saw C :(

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

Ah I got the idea of C but couldnt implement it because of time.

Just a summation of (n-i)*(2*(n-i)-1)

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

.

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

any idea how to solve C ? was stuck on it for the whole contest :(

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

    Hint: For a square of $$$n \times n$$$, swipe the last line and last column, then solve the problem for a square of $$$(n-1) \times (n-1)$$$.

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

      ^let's stop thinking of every iterative problem recursively. Please avoid giving misleading hints,

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

        It's not that recursive. I think I oversimplified my thoughtstream in the comment, but I meant that hint when typing it out, and even thinking that it was more of a solution than a hint.

        Perhaps the only mistake I made here was giving the swipes in reversed order.

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

        It is not a misleading hint at all, just because the idea is recursive doesn't mean it cant be coded up iteratively. It is a great hint and I also solved it that way.

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

      I did find out the pattern during the contest but after messing around for an hour I thought it was impossible to implement using only $$$2n$$$ moves. Can you tell me how to construct the pattern?

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

        for i from n to 1 do 1 i 1 2 3 ... n and 2 i 1 2 3 ... n

        Example for 4
        → Reply
»
7 months ago, # |
  Vote: I like it +14 Vote: I do not like it

0 hack attempts among 20k+ people :(

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

Can someone explain why iam getting wa on my submisson for C :256512434

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

    should be this when n = 4

    1 2 3 4
    2 2 3 4
    3 3 3 4
    4 4 4 4

    is your solution get this?

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

      wait, how are you replacing the 2 with 3 in the second row?

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

        try this
        every time use same permutation 1, 2, ..., n
        use operation 1,2 and select i = n, n-1, ..., 2, 1

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

          yep now i've got it,should've seen it because i kept wondering what to do with the extra opration...thanks anyway

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

is C basically build this pattern in 2 * n right? cannot prove but it seems impossible

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

    Yes

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

    yes It is possible in 2*n order of operations is 1 1 1 1 2 2 1 on row/col applied 1 2 3 4 1 2 1

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

    i tried it for 30 min but i thought it was impossible.

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

      every time use same permutation 1, 2, ..., n
      use operation 1,2 and select i = n, n-1, ..., 2, 1

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

        does this shape have a formula to calculate its sum ?

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

          sum from 1 to n where ith term is i*(2*i-1)

          hence sum = (n* (n + 1) *( 4*n -1))/6

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

    submission_C I tried the implementing the same. can someone help me understand ? what's the correct approach to maximize sum in this

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

    You can see that you have $$$4$$$ at the end of each column and row, hence, probably, you should start from them. Replace first row with $$$4$$$, $$$3$$$, $$$2$$$, $$$1$$$, after that replace first column with same permutation, now replace second row with this permutation, after that replace second column and so on. You will get this:

    4 4 4 4
4 3 3 3
4 3 2 2
4 3 2 1

    But it is the same.

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

    the idea is always chose the line/column that contains the 1 to put the permutation, then construct the algorithm is not that hard.

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

I don't really know why C took so long to solve for me... Actually, solved D much faster, lol.

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

Really great contest, I especially liked problem D. Unfortunately I couldn't code it up in time.

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

    Me too. I came up with a solution but missed it by 2 minutes. Will validate my solution after system testing is over.

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

    Not sure why people are liking problem D, but the brute force with bitmask was very intuitive and very well fitting the complexity given the constraints.

    Usually D is harder than normal brute force, or did I miss something?

    https://codeforces.net/contest/1956/submission/256577486 (Although I couldn't make it up on time for contest because of one bug), but here in brute force I just tried all possible masks and chose the one with best ans & least changes.

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

      I you only care about the answer, you can solve it in $$$\mathcal{O}(n^2)$$$ time complexity with a really cool observation, which is the reason why many people like it I guess. The reason why problem author set $$$n \le 18$$$ is because there could be $$$2^n$$$ steps in the construction.

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

        Can you share how to find the answer in O(n^2).

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

          By noticing for every subsequence of length $$$L$$$ you can turn it to $$$L,L,\cdots,L$$$.

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

            Thanks for the reply.

            I also made an observation during the contest and it got AC but am unable to prove it-

            if f(l,r) denoted the ans for subarray a[l,r] then

            f(l,r)=max((r-l+1)^2,f(l,i-1)+a[i]+f(i+1,r))

            where i is the index of the maximum value in the subarray. Can you help prove it or find a conuterexample.

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

              It's easy to prove. First you need to observe that you only need to prove the case that all elements are 0.

              And then you can do it recursively, assume you can set the $$$a_i$$$ to $$$i-1$$$. If you want to set $$$a_{i+1}$$$ to $$$i$$$, all you need is to first let $$$a_i = i-1$$$, then $$$a_{i-1} = i - 2$$$, $$$\dots$$$, $$$a_1 = 0$$$. Now you can operate on $$$[1,i+1]$$$, and $$$a_{i+1}$$$ is $$$i$$$ now.

              So at the end, you can set every $$$a_i$$$ to $$$i-1$$$, and operate one more step $$$[1,L]$$$, you can set every element to $$$L$$$.

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

                I wasnt asking about that actually i wanted to prove or disprove the observation that i mentioned in my prvious reply that its always optimal to either make the whole array eqaul to r-l+1 or partition the array around the maximium of the array that is leave the maximum of the array as it is and maximise the answer for the subarray that is to the left of the maximum element and also the subarray that is to the right.

                refer to my previous reply for the transition im talking about

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

                  I don't know what is needed to be proved.

                  Because looking at every longest subsequence that is being operated, the maximum value that every value could be is the length of the subsequence, so if you want to operate something, the optimal way is to do this.

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

        you can solve it in O(nlogn) time

        dp[i] = max(dp[i — 1] + a[i], dp[j] + (i — j)^2)

        You can use Convex Hull trick to handle the second transition

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

very bad C, and nice D

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

Pretty good contest!

I liked D so much (the limit on the number of operations is chosen carefully!).

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

don't let these authors make contest Mike.

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

For my 1st contest i only managed to get A and B right lol

Can someone give me an hint for E1 pls ? It kept reaching the time limit on pretest 11 and I had no idea on how to reduce the time complexity. https://codeforces.net/contest/1956/submission/256528779

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

    My guess is that pretest 11 being something like this:

    1
200000
1 200000 0 1 200000 0 1 200000 0 ...
    → Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Think about a sequence of 4 that looks like this: 0 1 100000 0. On this case you can just put the 3rd number on 0 and move forward saving a lot of time.

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

C is really great, it took me so much time tho, but I love this one.

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

10**100 is quite ridiculous.
Interesting problem description.

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

    10^100 means it'll probably give the same answer as "infinity". It made that task fun, for me

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

    It's just to avoid explaining "what infinite turns of operations means"

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

A: If number of players is not greater than a[1], the game is end, otherwise it will continue. Then the answer is min(n, a[1]-1).

B: Assume we have t pairs and n-2*t single cards, then the opponent will also have n-2*t single cards, and then, they have (n-(n-2*t))/2 = t pairs. Since we can always get t points from pairs, and we can only get other n-2*t points if we play these single cards after opponent plays the corresponding cards, we need to play pairs first and single cards later. So for the first 2*t turns both players will play all pairs, and then we can't get any point because the opponent will play the card we've played last turn. So the answer is t.

C: From the example for n=2 we can see we can't get {{2, 2}, {2, 2}}. In fact, for any n and pairs (i1, i2) and (j1, j2) with i1<i2, j1<j2, we can't make numbers on the 2x2 submatrix determined by row i1, i2 and colomn j1, j2 be the same. So there can be at most 2*n-1 occurences of n (they can occupy a row and a column), and for the remained n-1 rows and columns, there can be at most 2*(n-1)-1 occurences of n-1 and so on... Therefore, the maximum sum we can get is sum(i=1...n)(i*(2*i-1)=i*(i+1)*(4*i-1)/6. To achieve this value, we can make operation on the i-th row and column, from i=n to i=1, with p[j]=j.

D: Let f(L, R) means we want to make a[L]=0, a[L+1]=1, ..., a[R]=R-L. If L==R, we can achieve this by do operation on [L, L] if a[L]>0. Otherwise, we can first do f(L+1, R), then do operation on [L+1, R] to make a[R]=R-L, then do f(L, R-1). Therefore, for any range [L, R] we can make the sum on this range be (R-L+1)^2 by operations, which is also the maximum possible value if every element on [L, R] have been modified. So we can solve the problem by dp.

E1: Assume i-th to (i+2)-th monster survived for T turns. If in the last turn (i+2)-th monster takes D damage, then at j turns before, it takes at least D+j damage, so the total damage it take will be at least D+(D+1)+...+(D+T-1) >= T*(T+1)/2, which means T*(T+1)/2 <= a[i+2]. Therefore, if we let A=max(ai), then after O(sqrt(A)) turns, there will be no more than 2 consecutive alive monsters, then for any pair of adjacent alive monsters, the left will be alive the the right will die. So we can brute solve the problem by brute force.

E2: Similar with E1, there will be no more than 3 consecutive alive monsters after O(A^(1/3)) turns, but we need to calculate the total damage of the second monster, in order to determine whether the third monster alive for consecutive 3 monsters.

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

    typo in solution for D, if L!=R, first do f(L+1,R) then f(R,R), not f(L+1,R) again.

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

    For problem D, why we do we even need DP (we can) but isn't easier to brute force on all possible masks?

    (I just want to understand I'm not missing something because of weak test cases, because I did this using normal brute force & everyone else seems to be doing DP)

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

    In the D problem, when we realize that a segment of k elements can be filled with all value k, the problem is much easier. But I think it's quite hard to realize it, can you share your thinking flow to come up with it. Thank you

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

    in E2 . what are u doing in this line of code.

    how u derive the formula of dmg variable 

       ll p=a[i];
							ll q=a[j];
							ll r=a[j1];
							ll t=q/p;
							ll dmg=(q>p)?(2*q-(t+1)*p)*t/2:0;
							a[j]=0;
							if(dmg>=r) a[j1]=0;

    ``

    upd :- understood . but my code is giving tle on tc 54. :( . anyone tell me what bug is there

    https://codeforces.net/contest/1956/submission/256603484

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

    In problem E1, how do you prove that we need O(sqrt(A)) turns ? I was able to come up with the idea but i couldn't figure out how many times i should run the simulation

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

Only needed 3 point for EXPERT but here C depressed me with 6 WA and will now get a negative delta :), my bad luck is really good :)

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

In problem c didn't we had to make matrix as

Spoiler

For that first we will fill rows 1 to n with Permutation 1 2...n and then set n=n/2 and do the same with columns This was my approach why did it fail

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

    Matrix should be:

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

    your matrix is correct. you probably did something wrong with your construction of matrix. you can always go in either descending order or ascending order with descending permutation.

    Here's how it would be constructed

    0 0 0 1

    0 0 0 2

    0 0 0 3

    1 2 3 4

    Next Step:

    0 0 1 1

    0 0 2 2

    1 2 3 4

    1 2 4 4

    and so on.

    so use a $$$ lastRow $$$ and $$$ lastColumn $$$ and solve this with decrementing both of them.

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

Very nice problems. I am waiting to see the pretest number 21 on E2 :D. Maybe 15 more minutes would have been nice but maybe its just me that i am slow at finding solutions for problems like C.

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

very good round,make me back to expert AGAIN!

I love yuzusoft ans it's fans,because of u my friend.

Ciallo～(∠・ω< )⌒★

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

couldn't solve C 💩 bye bye rating

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

Not Gona Lie , Problem C really Sucked

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

C is beautiful, was stack for whole contest because was trying to construct

1 2 3 4
2 2 3 4
3 3 3 4
4 4 4 4

instead of

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

    It's also easy to construct. Just use:

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

    both can be constructed easily.

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

It would have been neater if C only outputted $$$\sum a_{i,j}$$$, and if D were given as $$$a_i\le n$$$. Personally, I found it a bit cumbersome to write unnecessary subroutines.

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

    I think the hardest part of C was figuring out what operations it took to get to the intended sum, so it would've been way easier if we just wanted the intended sum.

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

    so basically you want guessforces; printing that the sum was n(n+1)(4n-1)/6 and was doable in 2n operations is something that could be guessed without needing an actual solution.

    Coming up with a construction is what makes the problem a C problem and not a B problem

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

    I thought it wouldn't be easy to guess just the value n(n+1)(4n-1)/6 without any specific process.. I see.

    By the way I thought there would be some consensus on my opinions on C and D, but there are only downvotes lol

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

      People can accidentally stumble into it if they go for the bad and non-generalizable method for $$$n=3$$$ and assume there must be a way to do it for $$$n \geq 4$$$ (the bad process being do all rows to set all rows to 123, do 1st and 2nd column setting those to 123, and then finally fix the top row again setting it to 123).

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

The C is too difficult for me to come up with the correct construction of the matrix. Huge thinking traps！ I determined to use the permutation to fill the matrix in the first n steps and all my attempts were on modification in the rest of n steps, which meant I will never get the correct answer!

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

    Seeing the terrible rank and the very few people solving D I was regret giving up C at first,but regret giving up C too late after I know the solution. It's just impossible to think of this strategy if you start in a totally wrong way.

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

      totally right, If you see my submission, I was making a WA attempts and realizing my mistakes, I solved the problem in a feedback loop of what I am doing currently wrong and before 5-10 min of contest realized what author wants

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

    had exactly same thought from the constraint 2 * n, since n + n / 2 + n / 4 ... + 1 < 2 * n so it MUST has something to do apply operation n times on row, n / 2 times on col and so on. kek

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

    same happened w me, i also used my first n steps in filling the matrix and ended up being stuck in a matrix

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

    Can anyone explain how you came up with the correct approach for the problem C ?? My strategy was like first, apply first operation in all n rows. Now starting from first column check if the sum of the column is less than "n*(n+1)/2". If it is then the second operation should be applied. So the total number of operations applied were "n + cnt_col". But when the contest was over and I saw the further testcases then I realised the correct way to maximise the sum. So my question is, how did you come up with the correct solution in the first place ??

    Because seeing this type of solutions now I've started fearing and getting anxious that would I even be able to come with such smart and clever solutions ever ??

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

Brick on random C again. Now you are my new nightmare photo boy.

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

When a person has a anime girl DP, Run as fast as possible XD

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

TLE on A on system tests. Nice Update: WA on E1 on system tests. Range of emotions throughout the contest xD

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

I sense weak pretests

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

Weak pretests for E2

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

What an excellent contest — well done!

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

TLE systest on A just for using maps instead of linear soln?

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

    The intended solution is O(1) for each query

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

D is a really cool problem!

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

The lesson you should learn from problem C: Don't touch your f*cking keyboard if you're not 100% sure about your solution.

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

Newbies After Solving A & B :')

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

Lengthy statements even for A, B. Weak-pretests for literally every problem on the contest (A, B, D, E1, E2)

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

    what does weak pretests mean

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

      When you submit a code during a contest It does not get tested on the full tests instead some of them which are called pretests (This saves some time so that submissions don't get stuck in queue for a long time). After the contest the submission gets re-evaluated on the full tests.

      Some times the pretests lack an important test case that a lot of people may fail because of it, Thats' why some people call them weak pretests.

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

where is the rating update -_-

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

rating changes when? 2 contests have pending changes

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

    look upd

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

    edu rating change should be right after this round.. but still no updates. . tsk tsk tsk

    ...

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

My D received runtime error in the System test. I submitted it using C++17 (GCC 7-32). After system test, I submitted the same code using C++20 (GCC 13-64), and it was accepted.

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

Whe the rating changes for Educational Codeforces Round 164 will be applied after this round?

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

Leaving aside the weak pretest of E, it's a very good contest!

Ciallo～(∠・ω< )⌒★

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

    what does weak pretests mean

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

      During the competition, only the results of pretests will be displayed, and not all the tests will be displayed. However, the pretest for problem E in this contest is not comprehensive enough. That's what weak means.

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

    it didnt work in O(n2) , i dont think it has weak pretests :/

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

what is the meaning of last announcment about rejudging ?

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

C is a beautiful problem with a simple solution. I have to accept that I am simply not good enough to solve these at my current level. One day hope to be able to solve problems like these fast.

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

    Yes bro, Like it is very simple but we need make observation then it is very easy. I also not able to solve this.

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

Finally CM, thank you all!

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

those who solved C be like

``

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

I believe my solution idea 256566371 to E2 can be adjusted for much higher values of a_i, tho it's not too different then what seems intended by other comments (also my submission is current fastest btw).

As others, I use it will take A^(1/k) rounds for there to be at most k in a row. However, I can also solve for small k in a row in O(k^3 * lg(A)) time. To do this, I found formula for how much each previous value will change current one after exactly x turns (just analyze pattern by keeping values as variables). Now you just use binary search for how many turns rounds until they one becomes 0.

Now just find optimal k where brute forcing initial rounds is as fast as solving remaining small sequences, and using wolfram it seems that for n=2e5 A=1e18 having k = 8 will solve in reasonable time.

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

My solution for D (which I believe is intended) reminds me a lot of the tower of hanoi, which can be solved using a similar recursive idea.

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

    Yeah, exactly my thoughts after reading the solution of YocyCraft. I thought it was some dumb bruteforce/bitmask dp and got stuck on that idea for a while, but that observation was beautiful.

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

Were the pretests for problem E1 and E2 purposefully made weak, to stop people from guessing the solution?

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

    Well, I wrote the same solutions as intended. However, I got 2 FSTs in both E1 ($$$\mathcal{O}(nV^{\frac{1}{2}}$$$, TLE on 24) and E2 ($$$\mathcal{O}(nV^{\frac{1}{3}}$$$, TLE on 54) ...

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

      Is this your submission for E1? 256524095 So you are sure the set does not add another log factor? (Didn't look too closely at the code). Even if it were true, sets are known for quite a big constant factor.

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

Is it intended that people who became orange from the edu round had the contest rated for them? Of course, I'm only asking because I did poorly ;)

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

Editorial?

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

Why weak pretest?? I made a very stupid mistake on D,but it still pass the pretest???

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

Codeforces Hot News! Wow! Coder bro_jie competed in Codeforces Round 939 (Div. 2) and gained ??? rating points taking place 1,151!!!!

WDF D>>>>>>>>>>C

Stuck on Div.2C for the first time ever!

good contest it is,nooooooooooob I am!

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

    Why so many downvotes? I couldn't understand lol

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

How to solve D ? Can someone explain in simple words ?

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

what's the point making the limit of problem F so tight

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

Auto comment: topic has been updated by Otomachi_Una (previous revision, new revision, compare).

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

Auto comment: topic has been updated by Otomachi_Una (previous revision, new revision, compare).

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

There's a typo in the hyperlink for the editorial. it says codeforc.es instead of codeforces

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

correct editorial Link: https://codeforces.net/blog/entry/128426

there is a little typo in hyper link

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

My favourite contest so far. Unfortunately, I was not able to participate during the contest itself :(

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

Auto comment: topic has been updated by Otomachi_Una (previous revision, new revision, compare).

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

I have a rather off-the-topic question.

I am fairly new to codeforces, having given only 4 contests so far. From what I read about the rating system, pupil ends at 1199 and apprentice begins at 1200. My rating after this contest got to 1200. Why am I still a pupil and not an apprentice? Apologies in advance for the question not being related to the contest.

I took the reference for the ratings from this blog: https://codeforces.net/blog/entry/68288

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

    ig it was old rating system. now it is

    Newbie < 1200

    Pupil 1200 <= rating < 1400

    and the other ones are mostly same.

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

very badly worded problems.

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

The contest was good even though I didn't rank high

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

Ciallo～(∠・ω< )⌒☆

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

As a grade 10 student, I must said that you are really talented. The best student in my school (my classmate) only reach master.

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

Can anyone explain how you came up with the correct approach for the problem C ?? My strategy was like first, apply first operation in all n rows. Now starting from first column check if the sum of the column is less than "n*(n+1)/2". If it is then the second operation should be applied. So the total number of operations applied were "n + cnt_col". But when the contest was over and I saw the further testcases then I realised the correct way to maximise the sum. So my question is, how did you come up with the correct solution in the first place ??

Because seeing this type of solutions now I've started fearing and getting anxious that would I even be able to come with such smart and clever solutions ever ??

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

    Authors did correct thing only including $$$n = 1, 2$$$ testcases. I am sure, that there are two ways how to come up with the solution. $$$1.$$$ I tried to solve $$$n = 3$$$ case and after getting one non-trivial result i sent it and get AC. The second way is try to prove bounds, but it's not necessary during contest

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

      I agree with solving for higher n like 3,4. But even when solving for n>=3, I would have followed the same pattern as n = 2. So I don't think I'd have come up with the correct approach anyway. So I am more interested in the idea itself, and you being a master what do you think is it due to my lack of knowledge about different concepts, or due to lack of problem solving skills and observation skills like I should have observed this pattern? I really really want to improve but problems like this just exhaust me completely and this feeling is worst.

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

my account is public so that my code is accessible to everyone. It's not fault. Please save me for this time. It will occur again in the future

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

Upsolved E2, shouldn't it be "Meguru VS. Monsters"?

That way C can be renamed as "Touko's favorite cake". So where can Tsumugi and Wakana show up?

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

well I got to %%%

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

I think it's super mentality

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

Wish I started at his age, wow

→ Reply