Hello Codeforces !!
I, on behalf of the InfInITy Team, would like to invite you to take part in the 5th edition of IIIT Pune's flagship coding event InfInITy 2k21, a rated contest hosted by CodeChef IIITP Chapter, which will take place on Wednesday, December 22, 2021, at 20:00 ISTUTC+5.5. It is a 3 hr long contest.
The contest is Rated for Div. 2 and Div. 3 on Codechef, but Div. 1 coders are encouraged to participate unofficially as there are prizes for top participants in combined(Div. 1 + Div. 2) ranklist. We'd be offering you 8 problems in Div 2 and 7 problems in Div 3 with varying difficulties.
CASH PRIZES :
- Top 3 performers (Div1 + Div 2 combined) will be awarded cash prize of INR 10000, 7000 & 3000 respectively. Top performer of Div3 will be awarded INR 2000.
- Top 2 Indian participants will be rewarded INR 4000 & 2000 respectively(for Div1 + Div2 participants).
- Prizes worth INR 10000 specially for IIIT Pune students.
Contest Link : www.codechef.com/INFI2021
Contest Timing : 20:00 to 23:00 IST
Registration For Prizes : Infinity Website or Google Form
I would really like to thank:
evilbuggy for providing great feedback on the problem set.
silentone, still_me, ay21, satty26, reyaan44 for setting & testing the problems with me.
abhi2402, darshancool25, iscsi, arpan491, DeadlyVelocity for testing the problems and giving valualable feedback.
The web development team(rakshitjain13, rushitote) for building an awesome website for the contest.
Codechef for sponsoring the event, their invaluable help and great platform.
BiT Legion for making this contest possible.
For any queries contact: bitlegion@iiitp.ac.in
Editorials for all the questions will be posted shortly after the contest ends!.
Past problem sets for the event: 2020, 2019
I hope you will enjoy solving the problems. Please give your feedback on the problem set in the comments below, after the contest.
UPD: Congratulations to the winners.
Div 1 + 2:
Div 3:
hit6646
taoran_chen
piccacu
All editorials have been published on codechef discuss.
How do prizes for top 3 in "div1+2" work if the divisions have separate contests on CodeChef? Will the problems be identical so you can manually merge the rankings?
Yes, div1 and div2 will have the same problems and the winners will be decided after merging the rank lists
what is meant by the top 2 Indian participants in : "Top 2 Indian participants will be rewarded INR 4000 & 2000 respectively."? because the questions will be different for div1/div2 from div3..
The only prize for div 3 participants is the overall Div 3 winner. All other prizes are for Div1 + Div2 participants. Updated the blog as well. Apologies for the confusion.
Reminder: The contest begins in 10 minutes. Join Here
Cheating has been started, just look how fast number of successful submission is increasing for "Marbles" problem in div.3. Please do something about it.
This part of the MARBLE problem statement was likely intended as a joke, but there's a grain of truth in every joke:
Nice problems. Thanks for the contest. :)
Too Hard For me to solve even B
5 seconds late to figure out the frustrating edge case of Ddakji. :(
I think the solution to this problem has to have a greedy approach, and lots of things to do with GCD. or, Maybe I'm completely wrong.
You are right. If there are only 1 positive or negative number, it would've made things a little trickier since they can't be reduced.
For problem hopscotch, it makes no sense why the answer for the first testcase of the sample is $$$0$$$. Do you think that $$$(0!)=0$$$? We can literally count $$$1$$$ way in the problem to assign things.
I am sorry, I should have taken care of this. I made an error.
When will problems be available for practice?I need to check my code to the last problem which I missed submitting by a few seconds
Already available for practice, I guess.
They were added to practice just now.My code passed
It was a nice contest. But I really hated solving
Dalgona TreatI felt this contest to be on the tougher side. It would have been a very good Div1.5 round.
What will be the answer for Ddakji for the case {1, 2, -3}? Accepted codes show 2 which I cant seem to get to :(
{1,2,-3} -> {1,1,-3} -> {1,0,-3} -> {1,-1,-3} -> {1,-1,-2} -> {1,-1,-1} -> {1,-1,0}
I totally forgot zeroes could be used as i lol :(
That was a really nice problems.
Found the problems pretty interesting. I was only able to solve Marbles and Tug of War. Could you guys please discuss your solutions for Dalgona treat, Hopscotch and Ddakji?
Hopscotch :
Inclusion-exclusion
Dalgona Treat :
$$$(x+y)*(x-y) + y^{2}$$$
$$$x-y=1$$$ and $$$x+y=n-1$$$
add three to both sides and then merge 4 ones to 1 two
Ddakji :
I got WA but i think it has something to with gcd.
For hopscotch, u can use inclusion-exclusion. First find out the the common elements between the indices that are 0 and indices that are assigned. Now we want to calculate number of ways to permute such that exactly 0 elements match their positions.
Now find the number of ways such that at least 0 elements match their positions. Then subtract the number of ways such that at least 1 element match their positions. Now the number of ways such that at least two elements match has been subtracted twice. So you add it. Similarily we just have to add for even numbers and subtract for odd numbers. Code
I'm having trouble understanding what you mean by "at least 0 elements match their positions". Could you please explain that a little?
That's actually the total number of permutations. You can look at this [Link] for more clarity. Our problem was just a more generalised case.(https://math.stackexchange.com/questions/929005/derivation-of-derangement-with-inclusion-exclusion)
Thanks!
I found Hopscotch problem to be very similar to E — Rook Path from the recent AtCoder ABC contest and this helped. Both problems are counting the number of ways to do something and both can be solved by a recursive DP.
In Hopscotch there are two types of undecided players: (1) not targeted by anyone and (2) targeted by someone else. When counting the number of possible ways to target somebody, an undecided guy of type1 can't target himself directly (this is forbidden by the problem statement). But an undecided guy of type2 can target the start of a chain pointing back to himself. The final answer is calculated by a function with two parameters: the number of guys of type1 and the number of guys of type2. They guys of type1 can be converted into type2 by being targeted. The DP state is a 2D array. A link to my submission (a small and simple function "solve" does the job): https://www.codechef.com/viewsolution/55291341
I solved the problem Hopscotch using dp. If anyone is interested, you can refer to my submission:- Link:- https://www.codechef.com/viewsolution/55287667
Please explain your approach
What I did was that I separated the elements into two groups. Group 1:- contains those elements which don't have their mannequins and they are also not part of someone else's mannequin. Group 2:- Contains those elements which don't have their mannequins but are part of someone else's mannequin.
For example for this testcase:- 3 6 1 0 0 0 Grp 1:-
4 5(mannequin)
4 5(element)
Grp2:- 2(mannequin) 6(element)
Now, let's say there are i elements in total who don't have their mannequins. And same elemets which belong to grp 1 and diff(i-same) elements which belong to group 2.->refer to my code .
le's define dp[i][same]->answer in which there are i elements who dont have mannequins out of which same elements belong to grp1. now,we can make transitions like dp[i][same]=dp[i-1][same-2]*(same-1)(case in which an element of grp 1 is paired with an element of grp1 only)+dp[i-1[same-1]*(diff or (i-same))(case in which an element of grp 1 is paired with an element of grp2). There are some minor implementation details(for handling edge cases). You can refer to gfg blog finding derrangements using dp for better understanding. Link:- https://www.geeksforgeeks.org/count-derangements-permutation-such-that-no-element-appears-in-its-original-position/
I enjoyed the contest and problems, other than the prizes were not for top5. :'(
Thats great to hear. With each passing year he contest is growing a lot. We will try to get in more sponsors, to offer even better range of prizes for our participants :)
I don't see rating changes for me, but there are other people in the rank list whose ratings are changed basically I see there are few people who are 3 stars but then rating on the right side is 2 stars.
It happens when they are updating the ratings. Check after 40-50 minutes, everything will be correct.
Time limit for TUG OF WAR (TOW) was very tight. My solution without using decreasing stack didn't pass as it had vectors and maps even though my solution was correct, but when I optimized it with stack and removed a vector which kept track of removed elements of b and the suffix max vector, it passed.
I think Authors should have kept $$$ N,M <= 5e5 $$$ so that such solution's can easily pass
Tle
AC with decreasing stack
Yeah it was a good lesson for me that sometimes using more vectors can cause TLE, but as it was div2 they should have lowered the constraints. Other than that the problems were interesting.
I think the lesson here is more about unordered_maps being sometimes slower than sorting. Yes O(n) is better than O(n*log(n)) but there are big constants. And look at quick solutions ~0.30sec. They just sorted array of B. Even python solution with sorting B are getting accepted in 0.8sec
I used unordered_map mentioned by neal in this blog which is optimized in case of many collisions
And I never faced any issue of TLE when using this unordered_map as they are better than ordinary map
And my point is that the main overhead was because of vectors that I used for keeping track of suffix maximum and the arr2 which stored the removed elements. And generally for a div2 problem C it should not be forced to use only one vector, they should allow to pass different implementations
I maybe wrong but that's what I have observed from the time I started CP
Auto comment: topic has been updated by nishit.sharma (previous revision, new revision, compare).