Tired of writing AC solutions? We've got you covered! This contest turns the usual format on its head. You'll be given problems and their buggy code submissions. Your job will be to figure out a test case where the buggy solution fails.
We are proud to invite you to DeCode 2021, as a part of Threads, Felicity IIIT Hyderabad! We have prizes for top three GLOBAL as well as top three INDIAN participants.
Date and Time: March 1st, 2100-2300 IST
Contest Link: CodeChef DGTC2021
Registration for prizes: Feliciy website (during registration, enter team name as your codechef username)
You will have eight problems and two hours to solve them. The problems are a good mix for all difficulty levels, from grandmasters to pupil. We have some hard problems, and some very easy too, and everything in between.
The rules and prizes have been announced on the contest page.
There's a good mix of logically enthralling bugs, and bugs that make you go "Dude just how? :O", so you'll have tons of entertainment throughout the contest.
Thanks to the setters: ltc.groverkss, amul_agrawal, kjain1810, fangahawk, akcube, and myself for setting amazing problems. And thanks to the testers: madlad, aditya.verma, ninja_28, akshat_goyal, Zshan and oreos, for debugging our contest in beta stage (inception?!).
We'll post an editorial after the contest is over. We hope you'll enjoy it!
As a tester, I can say that it is an absolutely brilliant contest prepared by these guys. A must-give!
Wow, such a unique format! it's like testing the stress tester XD
Why are you giving code as images :(
We are giving images of codes because we want you to read the code and understand it. Most of the questions have logical/easy to understand bugs, so you'll really not need the plain text source code :)
Looking forward to an awesome contest!!
Reminder: contest starts in 1.5hrs! (9pm IST)
We have Global as well as India-level prizes, so be sure to participate!
The contest is now over. We hope you enjoyed it! We will be releasing the editorial soon (at max 30min). We also have a bonus problem!
Do give us feedback on how we can improve and thank you for participating!
Edit: Fixed a typo
I was impressed by the quality of this round--the problems were all well-prepared and clearly stated, and the incorrect code was fairly easy to follow. Thanks to the authors for preparing the contest!
My solutions to the problems are as follows:
AVGNUMBS: The error is that the code uses integer division when dividing the sum by n before converting it to a double. Thus, any input with a non-integer average will break the code.
PRINSEC: The error is that the code prints "YEZ", rather than "YES", when x = 2 and y = 11. It remains to construct a valid r that will give these values of x and y. From a AND b = 2, we find that r's binary representation must contain 1 but not 2, and from c OR d = 11, we find that r's binary representation must contain both 16 and 8. Thus, we must have r = 16 + 8 + 1 = 25 in order to hack the solution.
STUDCOMP: The error is that apps is a set, rather than a multiset, meaning that it will only store appreciation values that appear multiple times in the input once. Thus, the code will fail on any test case where an optimal solution must use two equivalent appreciation values. I took N = 3, M = [1, 2, 3], and A = [2, 2, 3], forcing the program to print [-1, -1, -1] rather than [-1, -1, 2].
PROJOVER: The binary search implementation in this solution is incorrect. Since I didn't feel like finding the exact error and a test that causes the problem, I typed up the code from the image and then stress tested it against a version with the binary search corrected, submitting the test case generated as a result.
ENCCIRC: This solution's core logic involves removing every circle that fully contains another circle. This intuition is appealing, but it turns out to be incorrect. As a counterexample, we take two circles that intersect but do not fully overlap and a circle that is fully contained in their intersection. Then, the optimal solution is to remove the smaller circle, rather than the two larger circles. My countercase involved a circle of radius 1 centered at the origin and two circles of radius 4 centered at (1, 0) and (-1, 0).
MAXWND: The error is that the solution immediately returns without reading the arrays A and B if it finds that M > N. The issue with this is that A and B are then treated as the second test case's input. To hack the solution, I submitted an input with two test cases. The first had N = 2 and M = 3, causing it to break immediately. Then, I took A to be the array [1, 2] and B to be an arbitrary decreasing array, and I used the given sample input as the second case. Since M > N, 0 is immediately printed for the first test case, and 1 and 2 are read as N and M for the second case, so 0 is printed again.
VINMAZE: The error is that the implementation of Dijkstra's algorithm does not ensure that each vertex is visited only once. In other words, if the distance to a given vertex is decreased k times, then that vertex will be visited (and we'll iterate through its edges) k times. In the worst possible case, this leads to an O(N^2) solution. One construction is to connect vertices i and i+1 with an edge of length 1 to connect vertex i and vertex N with an edge of length 10^9 — 2i, for all valid i. Then, each of the first N-1 vertices will allow us to decrease the distance to vertex N slightly, meaning that we visit vertex N a total of N-1 times. However, each time, we iterate through this vertex's N-1 edges, resulting in O(N^2) complexity.
BUGINDP: The error is that when 1 is added to the answer on the final line, the result is not taken modulo 1879048192. Therefore, when the correct answer is congruent to zero modulo 1879048192, the program prints 1879048192, rather than zero. Then, it remains to find a case where the correct answer is congruent to zero mod 1879048192. We find that 1879048192 = 2^28 * 7, so we construct a countercase by taking six large values (any two of which have a sum greater than M) and 28 small values (such that we can take any subset of them in conjunction with one large value while keeping the total sum below M). Then, there are seven ways to either pick a large value or to use no large value in our subset and 2^28 ways to pick a subset of the small values to use, so the answer for this case is 2^28 * 7, which is zero mod 1879048192, as desired.
What would be the correct approach for problem ENCCIRC?
Thanks for the appreciation, it means a lot to us! :D
+1, thanks for the contest!
In VINMAZE, there is also an overflow on line on line 55 and 56 (If the nodes are unreachable, the values will stay LLONG_MAX), which I exploited to make this hack:
4 2
1 4 8
2 3 10
You're right. We noted this in our editorial. It was not the intended bug though :P
In PROJOVER, i guess you can just print the recursion assuming all the mid values as true and then you will end up with 5 never checked in the binary search and then we just have to make a case where answer is exactly 5.
Had of lot of fun doing the contest. Was a really good problemset
The contest was really great, and i get that it would have taken a lot of efforts to hide the bug in an almost AC code.
Really fun contest! The choice of bugs was quite nice and very well disguised. Also bonus points for the easter eggs in the problem statements (like typo/"bug" in IIIT) :P
Editorials:
AVGNUMBS: https://discuss.codechef.com/t/avgnumbs-editorial/86330/2
STUDCOMP: https://discuss.codechef.com/t/studcomp-editorial/86326
MAXWND: https://discuss.codechef.com/t/maxwnd-editorial/86327
PROJOVER: https://discuss.codechef.com/t/projover-editorial/86329
PRINSEC: https://discuss.codechef.com/t/prinsec-editorial/86324
VINMAZE: https://discuss.codechef.com/t/vinmaze-editorial/86328
ENCCIRC: https://discuss.codechef.com/t/enccirc-editorial/86325/2
BUGINDP: https://discuss.codechef.com/t/bugindp-editorial/86323
I have to say this was the most fun contest I have given in a long time. My sincere thanks to the whole team who created the contest.
Can anyone share the right approach to solve the problem ENCCIRC as greedy approach clearly fails?
Let's create a directed graph where an edge goes from node A to node B when circle A is totally enclosed by circle B. It is easy to see that this graph will be a DAG Now, the problem is to find the longest anti-chain in this DAG. This can be done using Dilworth's theorem.