sigma_g's blog

Invitation to DeCode 2021 from Felicity Threads IIIT-H
By sigma_g, history, 4 years ago, In English

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!

  • Vote: I like it
  • +189
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +50 Vote: I do not like it

As a tester, I can say that it is an absolutely brilliant contest prepared by these guys. A must-give!

→ Reply
»
4 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Wow, such a unique format! it's like testing the stress tester XD

→ Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Why are you giving code as images :(

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

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

    → Reply
»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Looking forward to an awesome contest!!

→ Reply
»
4 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Reminder: contest starts in 1.5hrs! (9pm IST)
We have Global as well as India-level prizes, so be sure to participate!

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +27 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +148 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    What would be the correct approach for problem ENCCIRC?

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +42 Vote: I do not like it

    Thanks for the appreciation, it means a lot to us! :D

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +13 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +20 Vote: I do not like it

      You're right. We noted this in our editorial. It was not the intended bug though :P

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      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.

      → Reply
»
4 years ago, # |
  Vote: I like it +51 Vote: I do not like it

Had of lot of fun doing the contest. Was a really good problemset

→ Reply
»
4 years ago, # |
  Vote: I like it +41 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it +46 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +40 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +27 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Can anyone share the right approach to solve the problem ENCCIRC as greedy approach clearly fails?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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.

    → Reply