crimsonred's blog

Codeforces Round #840 (Div. 2) and Enigma 2022 — Cybros LNMIIT
By crimsonred, 23 months ago, In English

Hello, Codeforces!

Cybros, the competitive programming club of LNMIIT Jaipur, is happy to invite you to participate in Codeforces Round 840 (Div. 2) and Enigma 2022 - Cybros LNMIIT which will be held on Dec/19/2022 17:35 (Moscow time).

You will be given 6 problems and 2 hours to solve them. The round will be rated for participants with rating strictly less than 2100. Division 1 participants can also participate unofficially in the round.

The problems were prepared by me, DreadArceus, ...nvm, warks, .utk., and og_. We would like to thank:

Good luck and have fun!

UPD1: Score distribution is 500 — 1000 — 1500 — 2000 — 2000 — 3000

UPD2: Congratulations to the winners!
Overall:
1. tourist
2. Um_nik
3. gyh20
4. neal
5. noimi

Div. 2:
1. apei
2. yyyz04
3. bobbilyking
4. rainboy
5. RNS_JK

UPD3: The editorial has been published.

About Enigma

Enigma is a part of Plinth 2023, LNMIIT Jaipur's tech fest. If you are an Indian school/college student, we will also hold an onsite round of Enigma from 27 to 29 January, 2023. You can register for the onsite round by filling the google form on our Instagram page.

As a part of Plinth, we will also conduct IUPC (Inter University Programming Contest), which is an ICPC-like contest for teams of three people. This contest is good practice for the real ICPC rounds. Both Enigma onsite and IUPC will have cash prizes and goodies.

  • Vote: I like it
  • -283
  • Vote: I do not like it

Comments Comments (328)
| Write comment?
»
23 months ago, # |
  Vote: I like it +32 Vote: I do not like it

ᓚᘏᗢ

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

As a setter, I request contribution since crimsonred butchered my vacation for it (but totally worth it as the contest is going to be awesome)!

All the best to everyone participating. Have fun!

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

yay

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

As a tester, I am about to start testing! Wish me luck!

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

Have fun guys :)

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

As a tester, I enjoyed the round and hope the same for you. All the best !!

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

As a setter ,i want contribution.

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

As a tester, I tasted the problems and can testify that they are delicious!

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

As a tester, the problem set is very good 🤩 you all should participate

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

As a tester, I found the problems unique and interesting!

Good luck to everyone participating!

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

.cat_fear.

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

As a tester, the problems are great and I recommend you to try all the problems.

Wish you all positive delta.

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

As a tester, I found the problems interesting and would recommend reading all the problems.

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

As a testor i have tested and after testing i have concluded that the first contest i have tested which is also tested by other skilled testors and all testors unanimously said it was fun to test it.....Best of Luck and I hope you get positive delta

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

As a tester I find writing a comment absolutely necessary, so "a comment". all the best to everyone participating and have fun!!

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

As a setter, I recommend you to read all the problems.

Have fun!

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

As a non tester, I found the problems interesting and I would encourage everyone to participate in the round!

P.S. — May Miku Bless you all with a +ve rating. ＼(≧∇≦)／

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

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

Good luck to everyone participating, Have FUN !!

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

As a would-be contestant (hopefully), there is a surprising lack of comments from other would-be contestants.

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

As a participant, Can I get upvote?

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

omg green round

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

Salute to Codeforces for organizing 5 contest in a row !!. Thanks for such a lovely Christmas gift.

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

As a tester, I expect this comment to receive many downvotes.

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

All Indians round with every setter's rating < 1900 and all testers also Indians???

I am not expecting it to be very good round.

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

    Yes, KAN turned indian.

    Why do you even care, it's not even rated for you?

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

    Really? How about CodeCraft by IIIT Hyderabad? Pretty nice problems with excellent editorial, along with video explanation too.

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

      Also last Indian round, was one of the most well received rounds by testers and participants. Irony is that, Even he has participated in the round. And also, It's clear that he is just talking trash about Indians without actually caring about problems or round quality.

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

        Most received? What can you prove that? I think it is a bad round

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

          It was a bit harder than usual rounds, but the problems were so enjoyable and interesting to solve for me and a lot of my friends and also testers (you can check their comments). I don't know how you judge a round or why would you call it a bad round!

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

    I found your prediction true, at least for me though.

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

    I suppose u got a point there about setters' ratings, but... is there really anything to do with nationality??? (Just asking qwq)

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

It's an amazing experience for participating in 5 contests in 1 week. Hoping for a good round. All the best for the setters and testers :)

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

Best of Luck everyone.(~.~)

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

very good

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

omg indian round

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

As a participant I hope for high rating increase 🤩 and will love solving the problems

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

it's cool !! it's is very good !! Thanks for Contest

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

crimsonred what will be the criteria for getting shortlisted for onsite round

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

As a tester, don't quit earning more score until the last second to win an onsite round.

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

    onsite round is of icpc format that is 3 members, right??... Edit: got it for onsite enigma they will select from this contest, but where is the form for IUPC?

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

      yes! :) we have 2 onsite contest Enigma which is solo other is IUPC (icpc style)

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

Hoping for +Delta.

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

Score or penalty? Good luck everyone!

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

lol

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

please tell me this round will not speedforces, i will be very happy.

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

Hope to perform better

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

Upvote this comment for good luck!

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

I hope to become a specialist today...

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

Good luck everyone :)

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

As an experiment, I turned on the standings setting to show only trusted participants. Like we do in Div3.

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

We have a 3 minute AC on D, this has to be a record right?

→ Reply
»
23 months ago, # |
← Rev. 6   Vote: I like it -10 Vote: I do not like it

owoovo_shih orz

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

Your problems are interesting, but too difficult.

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

    Agreed, the time for the round should have been 2:30 hrs as D has painful implementation and maths.

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

      If U uses dp, you won't need maths :)

      Note tourist solved it in 3 mins.

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

Why the huge difficulty gap between B and C?

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

    Isn't C rather simple? Just a simple observation.

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

      Problems like this are very subjective. If you miss the observation you're fucked, but if you see it good for you. From the solves distribution I would assume that the "simple observation" wasn't obvious to most people.

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

        To some extent yes, but there is also a method to get these observations. Like here, you first see that no element can go more than max($$$a_i$$$). Now, you ask if you can make all elements equal to max($$$a_i$$$). To do that, you realise that you need to make certain elements 0 and then those between 0 and max($$$a_i$$$) will become equal to max($$$a_i$$$). Hence, you try and make the first and last elements 0. I might have called it an observation, but actually that only comes about when you follow a process, which I felt in this case was not very difficult, hence called it a simple observation. I didn't have enough time to solve D because I messed up B for long. But, I don't feel it was too difficult either.

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

You can tell this contest is bad by the fact that I got expert performance by solving only 2 problems.

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

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

uh why did the authors put 3 div2D in a contest "o.o

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

    We are sorry for that. In our opinion, C is not hard so much(

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

      i understand, C is just a simple observation, but what REALLY is annoying is the edge cases when n = 3, i wasted a whole contest doing that ;-;

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

        You can write a brute force for n = 3. Also, without it, the task will be too easy in my opinion.

        Sorry one more time. I hope you will enjoy next contests!

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

        Even E was more straightforward than C.
        The edge case of n = 3 and a[0] and a[2] < max(arr) was especially annoying.

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

      imo in C if sample test was better more people would have figured it out

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

        Placing a case with n > 3 in the samples would have made things too obvious.
        Instead of 600 solves, maybe we'd have had 6000.
        Both situations are bad.

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

Speedforces :(

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

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

Genos died as i gave up on solving B

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

At some moment it looked like this

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

Nice contest! Problems required careful casework. Although the edge case in problem D was super annoying.

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

    I missed the memo on $$$2 \leq k \leq n-1$$$ for D

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

Very good problems, but not a good round.

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

    What should we do, to be better next time?

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

      Seems like you underestimated the difficulty of the problems. Take a quick look at the number of solves, the gap between B and C is extremely high. I know C is an ad-hoc problem, so the number of solves may vary, but the gap shouldn't be this big.

      For me, this round would be perfect if we added 1 more problem between B and C, or lowered the difficulty of C.

      After all, I really enjoyed solving the problems, but I think not everyone liked it.

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

        Thanks a lot! We will invite more testers next time, to check the difficulty of problems more carefully. This time they told, that it's ok :(

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

I'm kinda mad honestly...

I made a stupid mistake in B (I had the order of some operations the wrong way around) and thus got -50 for an incorrect submission. It took me around 7 minutes to fix it (an extra -28 from time loss), and that total -78 dropped my ranking by almost 500.

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

    The difficulty of problem $$$C$$$ is unfair for people who normally solve $$$C$$$ like experts, this made pupil = specialist = expert :(

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

Thank you for your trash problems,trash examples and trash statements.It's the worst round I have ever participated in. I have never been so angry about a codeforces round,but today I think I wasted 2 hours,and and got an experience worse than EATING SHIT.

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

    This round is as good as your name :P

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

    I could not solve many problems, but I think the problem statements were sufficiently explanatory. Which question did you find hard to understand?

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

      I misread the problem B for many times(Even refered to the example explanation).And the example explanation of problem E made me became more confused about the problem.May be that was because my poor English,but it is the first time I cannot read a statement correctly until the contest ends.

      BTW,Why problem D's examples seems to be strong,but in fact it approximately equals to 0?I found at least 3 bugs but it was still Wrong Answer.

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

        I think the examples were weak in all the questions, but I think that's fine if protests are strong.

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

    you not being able to solve B doesnt make this contest bad...

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

      Yes U r right,but at least in my eye the round is really bad in various of senses,weak examples,bad statements and even a classic algorithm problem F...

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

    LMFAO

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

      I’m happy that I brought you much happiness :)

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

    more than the contest I am intrigued about the circumstances that lead you to have an experience that involved EATING SHIT.

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

      When I thought I could solve 4 but only got 1;When I found lots of bugs and felt a bit annoyed about why it could pass the example;When I found it was still wrong after fixing;When my friend told me D could be easily solved in high complexity DP,and I came up with $$$O(n)$$$ solution immediately but didn't pass until the contest ends...

      Of course that was also because my low CP-level,but I still felt very sad the next day.I also felt sorry about my impulsive comment yesterday,as it was the first time I solved 1 problem on codeforces round since 2020,56 contests XD

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

        I am glad we were able to challenge you, I hope you upsolve all the problems and you'd smth to learn :) all the best!

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

    I think the contest is now unrated

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

How to solve Problem C ?

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

    For n>=4 you can always get max(a)*n as answer. For n < 4 brute force.

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

      can you tell how can we get max(a)*n always when n>4?

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

        select any two consequtive element (left end or right end).. you can make these two element equal to 0 if you make the opeation 2 times... then operation with the maximum elemet and 0 make all the element equal to maximum.

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

          Understood! I should have noticed that :(

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

          "you can make these two element equal to 0 if you make the operation 2 times" Ahhhhh

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

        The idea is to create zeros in the array, in order to transfer the max element there.

        Let's say that X is the max in our array. You can do the following construction:
        1) [a,X,b,c] -> run the operation twice on the last 2 elements. Notice that this will make them equal to zero.
        2) [a,X,0,0] -> run the operation on the segment from X to the end, this will make all the elements in the last 3 positions equal to X.
        3) [a,X,X,X] -> similarly to (1), run the operation on the first 2 indexes twice, this will make the first 2 elements 0.
        4) [0,0,X,X] -> similarly to (2), run the operation between the first indexes up to X, this will make all the elements equal to X.
        5) [X,X,X,X] -> ans = X*n. It can be proven that this construction will work on any array of sizes larger than 4.

        Also notice that this doesn't work on arrays of size < 4, because it is not guaranteed that there are 2 elements in the beginning or the end that can be modified to 0.

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

    think about what happend when n>= 4...

    hihi

    for 2 and 3 .. bruteforce

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

    You can separate in some cases. Let mx be the maximum element of the array, then:

    • If $$$n >= 4$$$, the answer is $$$mx * n$$$. Make some elements $$$0$$$ and then apply the operation with $$$mx$$$.

    • If $$$n = 2$$$, just print $$$max (a[1] + a[2], 2 * abs (a[2] - a[1]))$$$.

    • If $$$n - 3$$$ I don't know a simple formula, but you can brute the operations by hand and get the maximum.

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

    Answer:

    $$$n\ge 4 \rightarrow n\times \max a_i$$$

    $$$n=3 \rightarrow \max [a_1+a_2+a_3,3\times a_1,3\times a_3,3\times (a_2-a_1),3\times (a_2-a_3)]$$$

    $$$n=2 \rightarrow \max [a_1+a_2,2\times|a_2-a_1|]$$$

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

      how can this test be $$$400$$$? Shouldn't it be $$$380$$$? 

      1
4
1 1 100 10
      → Reply
      • »
        »
        »
        »
        23 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        1 1 100 10 -> ... -> 100 100 100 10 -> ... -> 100 100 100 100

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

        make $$$a_1=100$$$ by performing $$$(1,2)$$$ twice and then $$$(1,3)$$$, make $$$a_4=0$$$ by performing $$$(3,4)$$$ twice, and finally perform $$$(1,4)$$$

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

        I believe that we will get answer as 400.

        1. We apply the operation twice on index 0 and 1. the array is = 0 0 100 10
        2. We apply the operation on index 0 and 2 the array becomes = 100 100 100 10
        3. we apply the operation twice on index 2 and 3 the array becomes = 100 100 0 0
        4. finally we apply the operation on the index 1 and 3 the array becomes = 100 100 100 100

        and sum comes out to be 400

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

      I failed to find the formulae for n == 3 during the round, so I just bruteforced all sequences of up to 4 operations on the array

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

WHATEVER I HAD GAINED IN LAST 3 CONTEST == LOST IN THIS ONE ... lol

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

the most efficient way to solve Problem B was to call saitama for help

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

nice problems, thanks

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

30 minutes debugging on problem D, until i noticed the maximum element cant be on the first, or last place by definition... a little hidden constraint

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

    Yeah that was the annoying edge case! Even I was wondering what's wrong with my formula when I was getting WA on pretest 2!

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

      Same thing, it should have been bolded out or something

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

    It seems the term "bitonic sequence" has some inconsistent usage (1383D - Rearrange). It would have been appreciated to have included a sample case that differentiated between these two definitions.

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

      +1, I didn’t even read the definition of bitonic because I’ve seen the same version, which considers monotonic sequences to be bitonic, so many times (similarly to how I don’t read the definition of “permutation” every time it appears in a problem statement). Ultimately, I had no idea why my solution was wrong, decided I must be too tired to be programming, and quit the contest :)

      Maybe the definition used in the problem statement is more common than I thought, but given that there’s a prevalent alternative definition, I think a note (possibly bolded) stating that monotnoic sequences are not bitonic would have improved the problem.

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

    i missed ac because of this :')

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

    I made the same mistake. And I thought I am not able to fix this small bug during the contest, because actually I thought the monotonic sequence also meet the definition in the statement.

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

I appreciate your effort in the contest (actually many questions are interesting), but I think the difficulty of the contest overall is not suitable for Div2.

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

    It is more like they missed some problem between B and C

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

      I do not know. Even putting C as D will still be considered difficult.

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

        I am not sure. C felt really impossible at first to me as well. However, after solving I am scratching my head over how everyone all at once found it difficult. The only observation is operating on same subarray twice makes it all 0. I feel like many problems routinely have much harder observations.

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

          I tried it for some time then decided to leave it for D, that is when I got lost in the edge cases. But I agree with you C with the right observations can be easily solved.

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

          After seeing the solution to C, I realized how stupid I actually am. I managed to realize that if we can get a zero somewhere, we can operate on the subarray [max_value, 0] and make all of those equal to max_value, but I somehow missed that operating twice on ANY subarray will make them all zero...

          I just gave up at some point, probably the worst desicion I've made in a contest this far.

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

          I think if the constraints were 0 <= a_i <= 10^9, the problem would have had way more solves :P.

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

      C is an easy problem, if you make the right observation (solution is n*maxElement for all n>3). Took me some time as well. Not the biggest fan of these tasks either.

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

        Interesting! I will have another look at the problems after the system judging but yeah solving them in the contest was quite challenging.

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

    Actually, after looking at C again, I think it is not that bad. Maybe I should have given it more time and concentration.

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

how to do B ? I used priority queue.

https://codeforces.net/contest/1763/submission/186007315 my submission

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

    Each monster will lose k HP by attack every round.

    Perhaps your mistake is due to your misunderstanding of the meaning of the question.

    Just sort it is enough.

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

      can you tell what's wrong in my solution https://codeforces.net/contest/1763/submission/185981968

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

        You sort the array by p,but monsters died by h.

        My solution is sort the array by h,and kill monsters by the minimum of p prefixs.

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

          His approach is also valid. It has the same complexity.

          while (temp && i<n)
...
temp-=p[i].first;

          temp can be negative > 0 is missing, probably

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

            Yes, thank you for your correction. I'm sorry for my careless judgment.

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

    if you want a solution of B with priority queue .You may refer to my solution of B , i solved it using priority queue.

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

    Watch this, if you are comfortable in Hinglish

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

how to solve B what's the idea

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

Misread B to assume k decreases by the power of the minimum health (alive) monster and wasted 30 minutes fixing my correct solution.

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

Amazing round, I loved the ways the questions made me think! Was a really fun way to end the recent streak of contests :)

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

what a bad contest, wish I didn't waste my time

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

how to solve a? b is more easier than a

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

Did anyone else get failed pretest 11 for problem E? I used a dp where the main idea was to look for triangular numbers less than p (of the form $$$\frac{t(t+1)}{2})$$$ which can be represented minimally with $$$t+1$$$ nodes.

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

    Yeah, it doesn't work for p = 12 for example

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

    i've also tried that, but finally did it with simple dp(n * sqrt(n)). Not sure if it won't FST...

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

    Me too, all my solutions (with different approaches even :D) got WA test 11. Anyone has counter-case?

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

D is not too hard but coding it's solution need to be VERRRRRRY CAREFUL

I could have solved it but it's out of time

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

    Also solution of C is incredibly trivial for n>=4

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

    Also, some discussion for B:

    The change of attack k depends only on min{pi| monster i is alive}, so at this moment monsters who has higher power p can be regarded as not exist. Therefore we can sort monsters by their power, and imagine we are beating them one by one, but whenever a new monster appear, we reduce it's health by (the amount of damage we have dealt before). Result of each battle can be calculated by quadratic inequality, but even if we simulate it step by step(for each step k-=min{pi| monster i is alive}, (the amount of damage we have dealt before)+=k), the time limit is enough, because for every step k decreased by at least 1, and when k<=0 we can end the simulation and see whether all monsters are defeated. Thus overall time complexity is O(n+k).

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

Hard but amazing! Thank you to hold this round!

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

Huge difficulty gap between B and C :( But problems are of real quality :) Enjoyed the problems and the contest overall :) Could not solve C but solved E somehow. HuiHuiHui

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

Worst CF Round Ever. Worst Difficulty Transition. Misleading Statements And Worst Samples.

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

    Tell us what can we do to be better next time, please?

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

      The sample test cases for C is great, it eluded me from the intended solution.

      The sample test cases for D should have been affected by the $$$2 \leq k \leq n-1$$$ constraint.

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

        Thanks a lot! We will take into account your comments and do codeforces better!

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

          Your eager to improve is quite respectable. Thanks for fast System Tests + Rating Change at least!

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

        But if the intended solution is simple, it should not be hinted by examples directly

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

    Misleading statements? Which statement did u find misleading? Worst Samples? Really? You want samples to cover up edge cases and stuff too? Samples should not be strong and just be enough to "understand" the meaning of problem statement imho. Although I agree difficulty was weird for many.

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

    In fact, I liked the samples for C. They explained the problem well enough without giving any hints to the algorithm.

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

why downvote? I agree that the problems are more difficult than usual, but they were enjoyable to solve (and to upsolve).

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

CAN ANYONE TELL WHY MY SUBMIISSION IS WRONG FOR PROBLEM B https://codeforces.net/contest/1763/submission/185981968

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

    while(i){} executes even if i is negative. while (temp>0 && i<n) will work

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

I won't trust testers in comments anymore

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

Difficulty of questions are too unbalanced

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

18o3 kya tester bnega re tu

→ Reply
»
23 months ago, # |
← Rev. 4   Vote: I like it -13 Vote: I do not like it

This comment has been deleted.

Just don't want to get more down votes:(

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

bruteforces :/

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

e67de25646622e5963e12fd63a2190f2d17a5e3b
upload images

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

I didn't find any reason to downvote this contest. The problems are not toooooo difficult, but they are interesting. You have at least something to think about for the whole two hours.

I believe that solving 3/4 of the problems in an hour and then giving up is not more beneficial than solving no problems but making you think for two hours.

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

    that's a stupid take. why would any one enjoy thinking for two hours to solving 3/4 problems in an hour, and giving up?

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

      He clearly said beneficial, not enjoyable. And he is also right; thinking for two hours means you've been challenged, solving quickly then stopping achieves nothing in helping you forward.

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

    I thought I could solve at least 4 but finally I got 1!

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

To be fair

I can understand why authors judged C to be C

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

    Same experience. Could not solve it during the contest. But once I figured out the key observation, felt ashamed of myself :_:

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

Can Anyone Explain to me the simpler approach to B?

I know segment tree and Sqrt decomposition are not the intended ones.

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

    k <= 1e5, so we can iterate over monsters sorted by power, decreasing k and increasing damage every time where damage is less than monster's health

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

      If we are iteratively decreasing k, then won't the time complexity be O(T * K) where T is the number of test cases.

      Let's take this test case:

      200000
1 100000
1000000000
1
The above test case repeated a lot of times

      Won't this give a TLE?

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

        Seems like not TLE, I got AC

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

        $$$T\le 100$$$

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

          Oh damn I missed this detail. Thanks for pointing it out.

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

          I was trying Binary Search but it was very difficult to implement.

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

            And even harder to debug. xp

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

            I even tried to solve the problem with calculus. Just didn't think simulating it would actually work.

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

    Sort according to Health

    Then Minimum Prefix Array from Behind

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

SPEEDFORCES ⬆️

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

Execution time on C was misleading :)

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

    My solution wouldn't pass with much lower timelimit, so I'm glad it is the way it is

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

      I don't mean time limit, I mean the time it took for most of the competitors code to get accepted.

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

Despite opinions, I liked round overall, maybe if you ask for future advice, I would recommend less annoying casework, but this is pretty much all.

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

    Which casework did you find annoying?

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

      Problem C n==3 case, took me A LOT of time to figure out all possible cases (yes, I know brute force could be done too, but that's overkill imo)

      Problem D, I didn't try to solve it, but have seen some comments about casework for D

      Problem E was great, have nothing to complain. Only thing, have seen somewhere above a comment about "artificial complication" of problem with second value to print. Can agree with this one, because once you realize solution (and fact that it must be not Greedy, but DP), second value you get along with first value, so seemed pretty useless for problem, though, still not such a big problem, I can't complain :)

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

        For C, you could reduce the case work using this.

        For D, if($$$x < y$$$), you could just reverse the permutation and you'll get $$$x>y$$$. That reduces it to just the 2 cases — that aren't repetitive as such.

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

          I did this, but also it was the case with applying op's like [0,1] [1,2] [1,2] [0,2], so that the answer would be 3*(abs(a[0]-a[1]) or 3*(abs(a[1]-a[2])

          For D, once again, I didn't solve it, I just referenced to opinions from comments (though, ok, those aren't trusted source xd)

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

The second number that was asked for in E is highly artificial; getting the first is clearly the bulk of the problem, I feel like the 2nd number was there to increase artificial difficulty (annoyance), e.g. to introduce more terms such as the "unidirectional" when the entire problem could just have been "Find minimal number of nodes such that there is exactly $$$p$$$ reachable pairs".

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

Round Was Amazing

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

Worst contest experience of my life

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

    Same. I was frightened in the first 1,5 hours because of -120 predict. Solved C and it became +6.

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

Is it just me or was B much harder than C. Required me to write segment tree so that I can forget about subtracting previous damage. Otherwise it's just painful to write. On the other hand C can be solved for all n but 3 easily. With n = 3 there isn't much you can do, and the bruteforce is easy-to-write.

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

    In B

    Sort according to Health

    Take a minimum prefix array from behind

    O(n) solution

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

    I solved B at 00:15, didn't even think about using segtree And solved C only at 01:25

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

    Btw, it is probably obvious but if you're considering using segtree in a Div2B problem then you're not after the intended solution

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

      I used it only as a secondary tool, I tried solving it without segtree, didn't manage to however.

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

    For n = 3 as well you could simplify the casework. When the max element is not in the middle, you could get 3*max. Otherwise, notice that operation (1,3) wont benefit. Hence, either you perform (1,2) or (2,3) or do nothing. If you perform either of the 2 operations, then you now have the max element at the edge and you could now solve it.

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

lol

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

For B I wasted 30 mins thinking I can't simulate this as health of monster <= 10^9. Later I realized k goes to zero in at most 10^5 attacks

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

    Even with k up to 10^9 it can be proven that the number of attacks will always be less then 2 * sqrt(max(health))

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

      Oh Yeah!

      Sum of numbers from 1 to number of attacks goes to max health within time limit. Don't know what I'm thinking during contest :(

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

    Lmao I didn't even consider any TLE or constraints.

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

It's after the fact, but I can't see anything in B that would've made me think I needed to reorder events (and allow for saved/cached debuff effects to hit after death??) and yet that's the route I went to make my dumb (TLE) sim better match sample descriptions. WA, reread, headdesk, damn.

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

Solved just A-C with time penalty 1.5+ hour and I'm ranked Top300?

For other div2 contest I would be ranked 1000+

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

Why is Kotlin 1.7 slower than 1.6? My submission for B

Kotlin 1.7 TLE (1s) https://codeforces.net/contest/1763/submission/185971554

Kotlin 1.6 (AC 546ms) https://codeforces.net/contest/1763/submission/186014735

Submissions are exactly the same

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

There is a somewhat closed-form solution to D. Without loss of generality, assume $$$x < y$$$ (otherwise reverse).

Essentially, it's formulated as $$$2^{n-y-1}\binom{x-1}{i-1}\left[\binom{y-x-1}{y-j-x+i}+\binom{y-x-1}{n-j-x+i}\right]$$$, but you need to subtract $$$1$$$ if $$$i=x$$$ and $$$j=y$$$.

Brief explanation:

  • You need to distribute elements that are lower than $$$x$$$ between before i and after j in $$${x - 1 \choose i - 1}$$$ ways;
  • You need to distribute elements greater than $$$y$$$ in bitonic way in $$$2^{n-y-1}$$$ ways;
  • You need to place all elements that are greater than $$$y$$$ either between i and j or after j;
  • Depending on that, you know how to distribute $$$y-x-1$$$ elements between $$$x$$$ and $$$y$$$;
  • Subtract $$$1$$$ if $$$x=i$$$ and $$$y=j$$$, because it would also count strictly increasing permutation;

See 186016207.

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

What was the idea for D? I figured out the case where x = n or y = n,and then I thought I should iterate over all positions different from 1,n,x,y and see in how many cases can the peak is there. I figured out the case where the peak is smaller than i or greater than j,but not for when it was in between. Help for this case,please?

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

    https://codeforces.net/contest/1763/submission/186015049. My fundamental observation is that bitonic permutation can be made by placing each number sequentially either as the leftmost or the rightmost element of an ever-decreasing segment

    Then I did DP with 3 dimensions

    • i — all numbers placed until i
    • j — position of left edge of segment (right edge position can be determined by i)
    • k — is this number placed on the left or the right of this segment?

    Finally watch out for monotonic edge cases.

    There was probably an O(n) solution with combinatorics somehow but I used the "programmer's method" as opposed to nCr's

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

      We don't need so many dimensions in the DP. We only need to maintain the starting index of the bitonic sequence as we extend it, leading to a DP with more straightforward transitions: 186035350.

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

Round was amazing !!! Missed E by a silly mistake of mine but the problems were good.

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

So, in problem B, the initial attack $$$k$$$ is up to $$$10^5$$$, whereas both $$$h_i$$$ and (perhaps more surprisingly $$$p_i$$$) are up to $$$10^9$$$. Are the setters deliberately trying to throw off people who misread statements?

Not to mention that probably a lot of the unsolves of problem D were people that were missing that monotonic arrays are not bitonic here for some reason...

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

    I just realised this now after the contest...

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

For question B, why do we sort by [power, health] and not [health, power]? Would'nt it be better to try and greedily remove the monster with the lowest health first?

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

    On every attack, $$$k$$$ health is removed from every monster, not just a single one. We sort the monsters by [power, health] in order to know the the least power of an alive monster, since that is what determines the decrease of $$$k$$$.

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

    Yeah, sorting [health, power] seemed more intuitive to me as well.185977402

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

anyone else who thought brute force would have given TLE for B? so kept trying other methods ?

→ Reply
»
23 months ago, # |
← Rev. 5   Vote: I like it +9 Vote: I do not like it

My opinion on Problem B: I think it is not a good idea to hide the constraint for k as it was hidden in the problem statement (Some may disagree. It is fine.) . That is the absurd way for making the problem hard (statement parsing wise) especially for problem at index B. For example, it makes more sense to say that sum of k over all test cases won't exceed 1e5. Or keep k as 1e9 and move the problem to higher spot, rather than participant figure out t * k < 1e7. For problem B, I generally look at problem only once and move to the editor. This is exaggerated more by the fact that constraints on n was shown clearly and constraints on k was hidden in a notorious fashion.

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

    Why do you say that the constraint on k was hidden?

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

      It became more of statement parsing after seeing the constraints on n and k. Many contestants ended up misreading and implemented BS on k which was harder to debug and pass. Also highlighting, if you switch the constraints statement on n and k, it won't make the difference complexity wise. Why they had different type of statement for these two variable? They could keep it same. right?

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

    I too solved the problem for k <= 1e9 using binary search and then after the contest my friends told me that simple a brute force would have worked because k was <= 1e5 not 1e9! Ruined the whole contest for me!

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

C is that type of problems, when you either noticed one simple thing or you didn't. It's really fun (when you have enough time) and beautiful, but also it's pretty random. I like this type of problems, but I'm not sure that they can be well balanced

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

This round was challenging as well as tricky!!

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

I hate to do this, but would really appreciate if someone could point out my mistake in B — 186014174

Losing my mind here

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

Why constraint of problem D is too small? I solved it in O(n) complexity. submission link

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

    There are test cases, and n=100 allows calculating C(n,k) in O(n)

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

    They set $$$n = 100$$$ to allow the $$$O(n^2)$$$ DP solution.

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

    $$$O(N^2)$$$ is much cleaner and simpler to implement.
    You can check out tourist's submission

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

    Sometimes small constraint misleads to think about "the complexity of this problem must be at least O(n^3) or something"

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

As a tester, it's very hard to predict the difficulty of C and E because of the not complex final solutions(I felt the gap between AB is larger than BC and D took more time than E when I was testing).
I want to say 500 — 1000 — 1500 — 2000 — 2000 — 3000 is the safest score value as a result, but if you are frustrating the gap between B and C, sorry for it.

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

They have vibes of JEE Advanced paper while making this contest (subjective & Hard).

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

Huh. Why is this downvoted so heavily?

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

problem B gives TLE in PyPy-3 but the same code is Accepted in Python-3. why ???

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

Ratings updated preliminary, it will be recalculated after removing the cheaters.

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

    I found the contest in the unrated list in my account

    Is it just while cheaters are removed or it became unrated ?

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

For problem B. Incinerate, what's wrong with my logic

  1. I am picking a monster with the max health and reducing its health with each attack. Since the rest of the monsters have lesser health, their health will reduce automatically.

  2. In the problem it is mentioned that first Genos deals k damage and after the damage, the damage is reduced by the power of the weakest. So I traverse through the complete power of the monsters and reduce the health of the strongest monster.

  3. if in the end the health>0, then I print "NO" else "Yes"

t = int(input())
for _ in range(t):
    n,k = map(int, input().split())
    lst = list(map(int, input().split()))
    lst1 = list(map(int, input().split()))
    lst1.sort()
    arr=[k]
    val=max(lst)
    if min(lst1)>k and val>min(lst1):
        print('NO')
    else:
        for i in lst1:
            if arr[-1]>=i:
                arr.append(arr[-1]-i)
        x=val
        #print(arr)
        for i in arr:
            val-=i
        #print(val,arr,lst1)
        if val>0:
            print('NO')
        else:
            print('YES')
→ Reply
  • »
    »
    23 months ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    Not even wrong. Your answer didn't used health (expect the max health). But it's obvious that every monster's health does matter.

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

Problem E1763E - Node Pairs is just a Coin Change dp.

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

Could you check out my wrong answer for problem B, test set 2, token 27 https://codeforces.net/contest/1763/submission/185996790

Thanks

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

    k+=(k-p) means your total damage is almost doubled every time, which contradicts that you attack is decreased. You should replace it with attack-=p, k+=attack where attack=k initially.

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

      It seems but it’s not like that. K+=k-p , assume first time you attack with K and K decrease by Pmin, p here. So it means for second smallest p you are decreasing k + k-p, right? I think my logic is correct. It passed too many test cases, i guess there is some special cases i did not see.

      11 5 2 1 K 6 means second monster killed at round 1 and first monster at round 2 , so for the first monster i used k 6 and again k 5 means in total k + k-p, 11 !

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

        Assuming all monsters have power p:

        1st attack: deal k damage. Then attack decreased to k-p

        2st attack: deal k-p damage. Then attack decreased to k-2p. Now total damage is 2k-p.

        3rd attack: deal k-2p damage. Total damage is 3k-3p.

        But in your code by executing k+=k-p, k becomes 2k-p, then becomes (2k-p)+(2k-2p)=4k-3p, there's no place for 3k-3p.

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

The most unbalanced and unprincipled round I've ever seen, change my mind...

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

Problem B was a really good greedy problem. Thanks a lot to the authors.

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

although i failed miserably in this contest but problem was not tough in my opinions and overall I liked the problems very much

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

A good contest with good problems :D Can't understand why people are downvoting badly like this!

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

The test samples of problem C are really weak!!

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

    Test samples cannot be weak. Test samples are not supposed to protect against anything other than misunderstanding of the problem

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

♦

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

Pretty cool problems. C had a nifty observation, it's one of those hit-or-miss problems, but I liked it nevertheless. E was a bit standard in my opinion, though. Perhaps D and E could have been swapped (and D's constraints changed to allow only O(N) solution to make it suitable for E).

Looking forward to attending the tech fest in LNMIIT!

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

Not too bad. C is interesting indeed, I like this problem but as other comments said, it might be a little bit hard to put on the place of C. D might be a little bit traditional but it's difficulty is suitable. E is constructive but a little easy for it's place. F, I can't solve it, but it made me think a lot. Probably the main problem of this contest is the difficulty of CDE, which may cause many Specialist to Expert participants feel bad when they can't solve C or D. Anyway, wish you guys can have a better contest next time!

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

$$$E$$$ can be solved using Oesis.

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

Why setting the samples of C all corner cases?

These $$$n=2,3$$$ corner cases may be even ad hoc I think.

Anyway it may be harder than the average.

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

    It was intentional as writing a case for $$$n > 3$$$ would give away the solution.

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

Div.2 winners are apei, yyyyz04, bobbilyking, NoPotato and rainboy.

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

Finally,I went to green.:)

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

C is not a good problem at this position for its observation. One may waste too much time if their intuition is incorrect.

D is a bit harder but E is much too easy.

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

    Maybe the difficulty distribution is ABDDDE.

    For me myself D may be too traditional and easy for this position.

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

    After seeing the solution, I thought that C would have more solves. I didn't get the observation, but I thought after seeing it that more people would've gotten it since it didn't seem too difficult. It just seems hit or miss whether you get the observation.

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

    Yeah, I overkilled it and wrote 150+ lines with WA! :(

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

The difficulty of the questions is too unbalanced.. but the question is good and needs allot of logic to get to the easy solution...

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

Where did my contest score go???

Does anyone have an idea why CF took back this contest rating??

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

    It'll be back after removing cheaters.

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

      there's no rating rolled back notification like usual tho?

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

were rating changes reverted?

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

can anyone please explain me why in B pretest 2 16 test 2 7
6 8
1 8
the correct ans is no and not yes, why??

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

    At first, 6->0 and 8->1. So the monster with health 6 will be dead and there is only 1 monster left with health 1 and power 8. Now this monster will reduce k=7 to 0. Hence genos cannot kill the last monster and the answer is NO.

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

https://codeforces.net/contest/1763/submission/185993790 can any one tell me where i am wrong

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

I have meet the problem is that: I have already registered, but when I finished my code on problem A, and click the "submit code" link, it tells me something like "only registered users can submit code", so I submited my code at the time when the contest begins 10 minutes, because after that I can extra register. Is there everyone meet the same problem?

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

I think solution to problem B was kind of a brute force solution and does not have much logic. Time complexity for some cases could be O(T*k) which would be ~1e7 operations which many thought would give TLE and struggled for logic(including me).

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

    In my experience, 1e7 operations are pretty safe as far as TLE is concerned.

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

    The trick is that K can only decrease by 10^5 times. Since the minimum power is 1 and k is 10^5, therefore you would have to loop at most k + n times at worst case. Therefore you don't nearly need 1e7 operations.

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

Has the ratings rolled back??

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

    Yes, they will be back once the cheaters are removed.

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

I don't think the difficulty gap between problem C and B is that wide as many suggests to be. The only reason I couldn't solve it in contest time was because I freaked out and thought this would be too hard. Spent the rest of the contest trying to solve D (because combinatorics, and I thought I could do it in time) and ended up getting none of them right in time.

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

can anyone tell me how can I remove TLE for 186082353 for problem b

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

Are the ratings gonna be rolled back or what ?

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

Why ratings of the contest has been revoked :"( ?

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

f

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

I didn't get why this blog has so much downvotes?

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

When you realise all consecutive contests are over and you again missed your chance to gain any significant delta

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

Note: I didn't participate in the contest, just saw the problems later.

Why did this contest get so many downvotes, I don't see a reason for -300?

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

.

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

this is the kind of contest that is especially for beginners, right?

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

    This one particularly is not. If you are completely new to competitive programming, then yoy should try div4, div3. If you are just new to codeforces, then it's better to solve div3, div2

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

Can anyone explain how for N = 4.

the answer is 5, 6

cant the graph be like this:

which gives answer as 4, 0

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

When will the finalists be announced so that we can book tickets accordingly?

→ Reply