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

Автор 0doO, история, 7 месяцев назад, По-английски

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.

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

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

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

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

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

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

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.

  • »
    »
    7 месяцев назад, # ^ |
      Проголосовать: нравится +120 Проголосовать: не нравится
    As a tester and schoolmate of Otomachi_Una...
  • »
    »
    7 месяцев назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    super DNA :)

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

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

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

    But why one auther comes from Japen?

    Or it just a joke?

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

    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.

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

    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.

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

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

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

    Chinese is not smart, such as me.

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

    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.

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

As a tester,Otomachi_Una is very cute :)

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

As an author, give me Contribution!

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

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.

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

Ciallo~(∠・ω< )⌒★

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

qrz

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

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

UWU

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

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

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

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

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

Yu...Yuzu soft fan?

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

Wish everything goes well!

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

Wish everyone gain more ratings, and me too :)

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

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

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

Cute pfp so I'll take a chance ^^

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

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

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

Hi! From Vietnam with love <3

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

i need to study more

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

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

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

OMG! Unrated tester yurongyi0504

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

As a tester, I hope everyone enjoys the contest!

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

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

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

Otomachi_Una round. les go

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

Ciallo~(∠・ω< )⌒★

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

yuzusoft round(

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

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

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

It seems to be the same account.

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

Please I need cm :)

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

Ciallo~(∠・ω< )⌒★

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

OMG Huafu jvxue!

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

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

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

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

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

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

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

Who is this anime cartoon characters?

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

Ciallo~(∠・ω< )⌒★

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

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

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

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?

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

Ciallo~(∠・ω< )⌒☆

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

score distribution?

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

Ciallo~(∠・ω< )⌒

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

wow

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

It is getting late to publish score distribution!

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

upvote!!

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

I hope the problem statements are short and clear.

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

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

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

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

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

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

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

cute/qq

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

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

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

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

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

operationforces

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

Constructiveforces.

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

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 ?

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

C is not a good problem.

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

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

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

      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.

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

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

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

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

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

the worst C i have ever seen

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

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

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

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

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

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

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

      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

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

        Generate all subsets of what?

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

          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

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

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

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

        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

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

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

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

problem C in a nutshell : Wrong answer on pretest 2

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

ok, what was the edge case for C?

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

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

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

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

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

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!

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

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

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

    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.

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

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

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

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

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

    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

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

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.

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

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

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

      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.

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

      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.

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

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

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

    Exactly!

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

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

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

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

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

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

.

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

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

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

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

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

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

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

        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.

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

        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.

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

      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?

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

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

        Example for 4
»
7 месяцев назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

0 hack attempts among 20k+ people :(

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

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

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

    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?

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

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

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

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

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

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

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

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

    Yes

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

    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

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

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

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

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

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

        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
        
        • »
          »
          »
          »
          »
          7 месяцев назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

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

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

    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.

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

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

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

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

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

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

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

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

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

    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.

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

      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.

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

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

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

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

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

            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.

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

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

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

                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

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

                  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.

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

        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

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

very bad C, and nice D

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

Pretty good contest!

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

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

don't let these authors make contest Mike.

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

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

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

    My guess is that pretest 11 being something like this:

    1
    200000
    1 200000 0 1 200000 0 1 200000 0 ...
    
  • »
    »
    7 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

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

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

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

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

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

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

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

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

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

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.

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

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

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

    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)

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

    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

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

    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

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

    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

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

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

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

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

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

    Matrix should be:

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

    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.

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

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.

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

very good round,make me back to expert AGAIN!

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

Ciallo~(∠・ω< )⌒★

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

couldn't solve C 💩 bye bye rating

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

Not Gona Lie , Problem C really Sucked

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

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

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.

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

    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.

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

    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

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

    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

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

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

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

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!

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

    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.

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

      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

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

    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

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

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

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

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

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

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

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

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

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

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

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

I sense weak pretests

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

Weak pretests for E2

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

What an excellent contest — well done!

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

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

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

D is a really cool problem!

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

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

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

Newbies After Solving A & B :')

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

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

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

    what does weak pretests mean

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

      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.

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

where is the rating update -_-

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

rating changes when? 2 contests have pending changes

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

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.

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

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

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

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

Ciallo~(∠・ω< )⌒★

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

    what does weak pretests mean

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

      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.

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

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

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

what is the meaning of last announcment about rejudging ?

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

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.

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

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

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

Finally CM, thank you all!

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

those who solved C be like

``

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

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.

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

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.

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

    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.

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

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

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

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

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

      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.

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

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

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

Editorial?

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

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

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

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!

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

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

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

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

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

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

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

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

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

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

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

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

there is a little typo in hyper link

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

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

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

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

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

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

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

    ig it was old rating system. now it is

    Newbie < 1200

    Pupil 1200 <= rating < 1400

    and the other ones are mostly same.

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

very badly worded problems.

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

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

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

Ciallo~(∠・ω< )⌒☆

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

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

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

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

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

    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

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

      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.

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

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

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

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?

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

well I got to %%%

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

I think it's super mentality

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

Wish I started at his age, wow