Hello Codeforces !!
Aparoksha is back with the second edition of the flagship-event CodeRed.
Last year's CodeRed 2018 was a great success with over 900 teams registering for it.
If you have the appetite for algorithmic problem solving, then don't miss it out!
It will be a 4.5 hour long team event with a maximum size of the team being 3 members.
The participants need not be from the same college/institution/organization.
The preliminary round will be held on Codechef, and the onsite round will be held during Aparoksha.
The total prize money is worth INR 125,000 (Including goodies for all teams selected for onsite round, travel expenses* and cash prizes worth INR 50,000).
The best 40 teams will make it to the onsite round.
Also, top 3 teams in the online round will get INR 4500, 2500 and 1500 respectively, along with Codechef Laddus.
All teams making it to the onsite round will get CodeRed T-shirts.
Contest link is here — CodeRed 2019.
The problem set comprises 7 problems of varying difficulty level.
So be ready to have a nail-biting experience on March 2, 2019 at 21:00 IST.
The problems have been set and tested by Shivam Garg (shivamg_isc), Ankit Rao (hybrid), Sahil Prakash (prakashs99), Vaibhav Srivastava (dbest077), Saurabh Kumar (shauryakr) and Mohammad Aquib (aquib786).
Special Thanks to Teja (tejavojjala) and Sacheendra (sacheendra9044) for their valuable input.
Facebook Page — CodeRed Facebook Page
Some of our previous contests —CodeRed 2018, Alkhwarizm 2017 and HumbleFool Cup 2016.
See you in the ENDGAME :D !!
Upd 1:- Contest is about to begin in almost 1 hour. Best of luck :)
Upd 2:- The contest is over, and was a great success with a mammoth 1271 teams registering for the contest.
Thanks for the overwhelming response. :D
Congratulations to the top 5 winners :D
- farhodkerimtemurbek — Kerim.K, Farhod
- 1e9+7 Bugs Per Second — Ashishgup, Slow_But_Determined, vntshh
- PaduKeDeewane — hitman623, Enigma27, _shanky
- Ryuzaki — Hiren.Vaghela, Learner99
- fast_coders — acraider, nitixkrai, fsociety00
Top 3 teams will get cash prizes of INR 4500, 2500 and 1500 respectively, along with Codechef Laddus. :)
Feedback of the contest in the comments will be highly appreciated :D
The detailed editorials will be posted on Monday.
For now, I am posting the hints.
CR191It was a digit DP problem. The states of the dp could be dp[index][previous][size - of - current - sequence][constraint][increasing / decreasing][mask].
Index — This shows the length of the number formed.
previous — This is used to store the last digit used.
size - of - current - sequence — This shows the size of the current sequence. It has to be less than K.
constraint — This shows whether the current number formed is constrained or not.
increasing / decreasing — This is used to know whether we are currently making an increasing or decreasing sequence.
mask — This is used to take care of the condition that given M digits occur at least once in the number.
CR192This is a geometry problem which can be solved using rotating line sweep algorithm. We iterate over all the lines(targets) and for each end of that line we will calculate and store the angle of all the other endpoints of the (n - 1) other targets.
And we will sort these values according to the angle. Then we will rotate the line passing through P by iterating over the other points, in slope order (We have already sorted it in slope order). If we encounter the first end of some target then we will add the length of that target to our current point and as we reach the other end we will subtract the length of that line from our current point. We have to perform the same for all the n given targets. We have to perform the same and take the maximum also we have add 1 when we reach the first end of some target to count the number of targets and as we reach the other end subtract 1 and in this way we can count the number of targets required to be destroyed to get current points.
The time complexity would be O(n * n * log(n)). The first n comes from iterating over all the n targets and the n * log(n) factor comes from storing the angle and sorting it.
CR193The problem can be broken down into the following formulae which can be pre computed. (C(a, i) * C(b, j)) * (2c - 1)), j < i
where, xCy represents x!/((x-y)!*y!) x^y represents x raised to the power y.
Complexity -- O(t*a*b) where t, a, b are test case, value of A, value of B respectively.
CR195It was based on Matrix Exponentiation. The initial matrix to be formed will be a 64 * 64 matrix, where we store the number of ways to go from a 4 letter state to another 4 letter state, keeping in mind all the restrictions.
However, this matrix with 104 test cases will lead to TLE, with total operations being 104 * (643log n).
Hence, with the solutions to initial values, one can solve the linear equations using any method say Gauss Elimination, and obtain a much smaller 3 * 3 matrix, thereby reducing the number of operations to 104 * (33log n)
