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, mePrakhar, 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.
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!!
As a setter, I recommend you to read all the problems.
Have fun!
As a
nontester, 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
Hmm... 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
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!
Hoping for +Delta.
Score or penalty? Good luck everyone!
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 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.
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.
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
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
Cuz he had places to visit
Genos died as i gave up on solving B
Saitama will help him!
Saitama didn’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 :(
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.
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...
you 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
nice problems, thanks
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://mirror.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://mirror.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
> 0is missing, probablyYes, thank you for your correction. I'm sorry for my careless judgment.
if you want a solution of B with priority queue .You may refer to my solution of B , i solved it using priority queue.
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...
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
Watch this, if you are comfortable in hinglish
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
ans=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.
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://mirror.codeforces.com/contest/1763/submission/185981968
while(i){} executes even if i is negative. while (temp>0 && i<n) will work
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
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
I even tried to solve the problem with calculus. Just didn't think simulating it would actually work.
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.
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.
lol
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
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+
Why is Kotlin 1.7 slower than 1.6? My submission for B
Kotlin 1.7 TLE (1s) https://mirror.codeforces.com/contest/1763/submission/185971554
Kotlin 1.6 (AC 546ms) https://mirror.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 iandafter jin $$${x - 1 \choose i - 1}$$$ ways;between i and jorafter 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://mirror.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?
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$$$.
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.
I didn't even think about brute force being possible...
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 Stress for 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.
Huh. Why is this downvoted so heavily?
people who get -ve delta r downvoting blogs these days.
everyone gets -ve delta. depends how they get it.
problem B gives TLE in PyPy-3 but the same code is Accepted in Python-3. why ???
Ratings updated preliminary, it will be recalculated after removing the cheaters.
I found the contest in the unrated list in my account
Is it just while cheaters are removed or it became unrated ?
For problem B. Incinerate, what's wrong with my logic
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.
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.
if in the end the health>0, then I print "NO" else "Yes"
Not even wrong. Your answer didn't used health (expect the max health). But it's obvious that every monster's health does matter.
Problem E1763E - Node Pairs is just a Coin Change dp.
Could you check out my wrong answer for problem B, test set 2, token 27 https://mirror.codeforces.com/contest/1763/submission/185996790
Thanks
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.
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 !
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.
Для человека, который переводил заявления с английского на русский: перевод идеальный, спасибо за старания! Никогда не видел таких лаконичных смс!
For the person who translated the statements from English to Russian: the translation is perfect, thank you for your efforts! I've never seen such concise texts!
Если это сарказм — я бы с радостью послушал, что можно сделать лучше, чтобы не допускать ошибок впредь. В любом случае — спасибо!
Лол. Ну типа на нейтив спикере можно было и без машинного перевода обойтись. Спалился фразой "Давайте назовем", на нормальном русском let не переводят.
И я даже не о несогласованности форм слов. Фразы "элементы сначала увеличиваются, а затем уменьшайте" или "дан неориентированных, связный граф", хотя и не соответствуют правилам русского языка, не влияют на понимание задачи. Очевидно, в какой форме на самом деле должно быть слово.
Но что гораздо хуже — так это то, что из-за машинного перевода меняется смысл слов, и в этом контесте это не вычитывали (или вычитывали, но не до конца). Например, в задаче F — "между одной парой вершин проведено не более одного ребра". Серьёзно, перевести any в данном контексте как "одной"? Это в корне меняет смысл предложения. Конечно, это задача F, и большая часть людей, которые до неё доберутся, поймут, что тут вместо "одной" на самом деле "каждой" или "любой". Но всё равно — смысл у фразы стал совсем другой, и вот это уже сильно влияет на понимание условия.
Я использовал машинный перевод, чтобы переводить условия на английский в своих раундах. Конечно, я исправлял неточности, которые получались, но в целом это гораздо удобнее, чем переводить с нуля.
Глянул условия 741 — не похоже на машинный перевод. Значит, их очень хорошо проверили и вычитали.
Для меня гораздо проще наоборот. Мне удобнее минут за 10-15 перевести самому, чем сэкономить время на перевод, но после этого пару часов выискивать, а где же ещё этот кремниевый мешок написал "график" вместо "граф". Возможно, всё ещё сильно зависит от конкретного переводчика, но ни один из тех, которые использовал я, не выдавал приемлемые результаты.
Я использую deepl.com
В целом его приходится вычитывать, конечно, но он делает не так много ошибок.
The most unbalanced and unprincipled round I've ever seen, change my mind...
Problem B was a really good greedy problem. Thanks a lot to the authors.
although i failed miserably in this contest but problem was not tough in my opinions and overall I liked the problems very much
A good contest with good problems :D Can't understand why people are downvoting badly like this!
The test samples of problem C are really weak!!
Test samples cannot be weak. Test samples are not supposed to protect against anything other than misunderstanding of the problem
♦
Same to you
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!
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!
$$$E$$$ can be solved using Oesis.
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.
It was intentional as writing a case for $$$n > 3$$$ would give away the solution.
Div.2 winners are apei, yyyyz04, bobbilyking, NoPotato and rainboy.
Finally,I went to green.:)
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.
Maybe the difficulty distribution is ABDDDE.
For me myself D may be too traditional and easy for this position.
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.
Yeah, I overkilled it and wrote 150+ lines with WA! :(
The difficulty of the questions is too unbalanced.. but the question is good and needs allot of logic to get to the easy solution...
Where did my contest score go???
Does anyone have an idea why CF took back this contest rating??
It'll be back after removing cheaters.
there's no rating rolled back notification like usual tho?
were rating changes reverted?
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??
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.
https://mirror.codeforces.com/contest/1763/submission/185993790 can any one tell me where i am wrong
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?
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).
In my experience, 1e7 operations are pretty safe as far as TLE is concerned.
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.
Has the ratings rolled back??
Yes, they will be back once the cheaters are removed.
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.
can anyone tell me how can I remove TLE for 186082353 for problem b
Are the ratings gonna be rolled back or what ?
Why ratings of the contest has been revoked :"( ?
f
"same boiler-plate code"
I didn't get why this blog has so much downvotes?
When you realise all consecutive contests are over and you again missed your chance to gain any significant delta
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?
Many people lost their rating
.
this is the kind of contest that is especially for beginners, right?
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
Can anyone explain how for N = 4.
the answer is 5, 6
cant the graph be like this:
which gives answer as 4, 0
When will the finalists be announced so that we can book tickets accordingly?