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:

- Aleks5d for coordinating the round and translating the statements into Russian,
- svince, tankman890, SoCloseButStillSoFar, shiviDON, abhigyan10, and pulkit_jain for discussing problems and coming up with problem ideas that didn't make it to the final problem set,
- KAN, satyam343, GoatTamer, physics0523, MasterRayuga, Blitztage, weakestOsuPlayer_244, Gaurav3478, 18o3, jainmilind, Milind_Sharma, DragoPhoenix, Nitin1605, AloneMusk, master._.mind, TarunAga, gaurav1910, imObscure, 4qqqq, LoLZeS666, PHOENIX_RISER, WORTH, Athern, sleepinGiant, and C-3PO for testing the problems and providing invaluable feedback, and
- MikeMirzayanov for the great platforms Codeforces and Polygon.

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.

ᓚᘏᗢ

ʘ‿ʘ

look to my name

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!

yay

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

how did you become a tester?

Have fun guys :)

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

As a setter ,i want contribution.

you edited your comment and still fucked up grammar

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

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

DragoPhoenix orz

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

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

Good luck to everyone participating!

..

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

Wish you all positive delta.

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

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

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

It was fun testing this (yes, my first) round!! All the best everyone Have Fun!!

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

Have fun!

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. ＼(≧∇≦)／

Good luck to everyone participating, Have FUN !!

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

As a participant, Can I get upvote?

omg green round

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

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

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

I am not expecting it to be very good round.

Yes, KAN turned indian.

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

None of the Indian rounds I have taken is good, especially those recommended by Indian testers.

based

Arisu_SakayanagiHmm... A great predictor...

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

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.

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

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!

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

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

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

Best of Luck everyone.(~.~)

very good

omg indian round

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

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

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

Top 200 Indian school/college students will be considered for the onsite round (cut-off rank can fluctuate depending on the response) :)

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

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?

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

How to participate in IUPC?

You can just fill out the google form (linked in our instagram page temporarily) we will contact you from that !!

Done, Thanks!

yes!

Hoping for

+Delta.I hope it will be good contest.

Score or penalty? Good luck everyone!

Done :)

Thx for notifying, good luck

Both :)

lol

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

Hope to perform better

Upvote this comment for good luck!

I am about to start testing! Wish me luck!

I hope today my delta will go positive :( I got -2 in yesterday div#3 contest o.O

the only enigma is why this website full of russians is still up and running ......

All the Best to Every One.

I hope to become a specialist today...

Good luck everyone :)

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

am i trusted?

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

scripted :)

owoovo.shih orz

Your problems are interesting, but too difficult.

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

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

Note tourist solved it in 3 mins.

they are quite easy in fact. if you find these kinds of problems to be hard, perhaps you should exercise some more. cheers

Why the huge difficulty gap between B and C?

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

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.

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.

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

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

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

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

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!

Even E was more straightforward than C.

The edge case of n = 3 and a[0] and a[2] < max(arr) was especially annoying.

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

most people figuring out doesn't make sample better :)

but the fact that very less did :(

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.

Speedforces :(

Relatable

*tourist after 28 mins

he is the real goat

Cuz he had places to visit

Genosdied as i gave up on solving BSaitama will help him!

Saitamadidn’t help as he was bored..At some moment it looked like this

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

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

Very good problems, but not a good round.

What should we do, to be better next time?

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.

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

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.

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

I too did that I too min health as a weakest person and it wasted me like 6 minutes and 1 wrong submission

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.

This round is as good as your name :P

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

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.

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

C was fucking conditioning

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

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

LMFAO

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

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

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

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!

I think the contest is now unrated

How to solve Problem C ?

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

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

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.

Understood! I should have noticed that :(

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

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.

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

hihiyou can make all the elements equal to maximum element.

for 2 and 3 .. bruteforce

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.

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

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

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

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

I believe that we will get answer as 400.

and sum comes out to be 400

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

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

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

bro I wasn't able to implement can you help in B problem

nice problems, thanks

Hope to become pupil this time

Congrats!

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

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!

Same thing, it should have been bolded out or something

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.

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

i missed ac because of this :')

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.

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.

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

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

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.

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.

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.

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

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.

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

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

how to do B ? I used priority queue.

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

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.

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

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.

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

temp can be negative

`> 0`

is missing, probablyI changed while(temp && i<n) to while(temp>0 & i<n) and it worked! thanks

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

it is the present k value right? that's what i did

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

thanks a lot.

Watch this, if you are comfortable in Hinglish

how to solve B what's the idea

Watch this it is in hinglish

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

4 wrong submissions for me because of that...

Congrats for Specialist

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

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

how to solve a? b is more easier than a

Bitwise OR of all elements — Bitwise AND of all elements

we have to use |(or) and &(and) to maximize and minimimze the maxm respectively .

True Same I think.Not able to think That ans will be bitwiseor(array)-bitwiseand(array)

Watch this, if you are comfortable in hinglish

omg, I just read the problem again because I didn't understand the solution, I misunderstood the problem, thanks to everyone

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.

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

Ah got it, Thank you! :)

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

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

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

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

Hintans=max(a)*n when n>=4 for n==2 || n==3 it's a bit harder but solvable

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

Hard but amazing! Thank you to hold this round!

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

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

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

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.

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

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

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

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.

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

It felt like div 1.5 contest.

SAME :)

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

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

well there are many problems with it, but first one is : n = 1 , k = 5 h = 6 p = 1 it will stuck in infinite loop. (have not checked myself so if this not the case then sorry) the issue is that you are not updating it in this case. Well even if you update your solution is not correct in my opinion.

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

Yes I got my silly mistake. Thanks

I won't trust testers in comments anymore

Difficulty of questions are too unbalanced

18o3 kya tester bnega re tu

Laughing emoji where

This comment has been deleted.

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

bruteforces :/

upload images

Disappointed because of B! Getting Time limit exceeded because timelimit is 1 second, my solution was just O(t*k) which is just 10^7, was using py-py and i know that some py-py users passed but considering different level of experience is also an important thing, i also saw some c++ solutions failing on system testing, blog--.

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.

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?

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.

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

To be fair

I can understand why authors judged C to be C

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

Can Anyone Explain to me the simpler approach to B?

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

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

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:

Won't this give a TLE?

Seems like not TLE, I got AC

$$$T\le 100$$$

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

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

And even harder to debug. xp

did it using binary search my solution

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

Segment tree??? Just use a priority queue

Sort according to Health

Then Minimum Prefix Array from Behind

SPEEDFORCES ⬆️

Execution time on C was misleading :)

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

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

Even Testcase with equal values is misleading

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.

Which casework did you find annoying?

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

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.

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)

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

Round Was Amazing

Worst contest experience of my life

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

didn't read C. getting -150 :")

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.

In B

Sort according to Health

Take a minimum prefix array from behind

O(n) solution

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

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

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

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.

Codelol

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

same here!!!! but was using binary search from the beginning and was making a small mistake there :(

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

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

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

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.

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

For other div2 contest I would be ranked 1000+

great brother!

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

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

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

Submissions are exactly the same

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:

`before i`

and`after j`

in $$${x - 1 \choose i - 1}$$$ ways;`between i and j`

or`after j`

;See 186016207.

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?

https://codeforces.com/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

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

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.

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

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

I just realised this now after the contest...

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?

we need to subtract the lower power at every attack. hence in order to know the least available power we sort it by power,health.

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 theleast powerof an alive monster, since that is what determines the decrease of $$$k$$$.I solved it by sorting [health, power].

Though it was a pain to implement and it cost me 3 penalties :(

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

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

Damn yes. Realised just now.

A CM realised this post the contest — definitely makes me feel better :P

I didn't even think about brute force being possible...

Idk why but I assumed that k was 1e9 without reading the problem statement correctly and then got 8 wa's before my BS solution was accepted.

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.Why do you say that the constraint on k was hidden?

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?

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!

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

This round was challenging as well as tricky!!

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

Losing my mind here

Omg K is <10^5 what the f

Would still appreciate the help lol

Take a look at Ticket 16578 from

CF Stressfor a counter example.Got it! Thank you so much~

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

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

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

$$$O(N^2)$$$ is much cleaner and simpler to implement.

You can check out tourist's submission

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

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.

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

u probably didnt even read the ques properly.