amul_agrawal's blog

Invitation to DeCode 2022 from Felicity Threads IIIT-H
By amul_agrawal, history, 3 years ago, In English

Ever thought that all the countless hours you spent debugging your friend's programs were in vain? Don't worry, we have a contest for you, where you can use all the debugging experience that you gained! This contest turns the usual format on its head. You'll be given problems and their buggy code submissions. Your job will be to determine a test case where the buggy solution fails.

We are proud to invite you to DeCode 2022, as a part of Threads, Felicity IIIT Hyderabad! We have prizes for the top three Global, Indian and IIITH participants.

Date and Time: March 12th, 2100-2300 IST
Contest Link: CodeChef DECO2022
Registration for prizes: Fill the google form

You will have nine 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. You can try the previous year's Decode contest here.

The rules and prizes have been announced on the contest page.

Problems of this contest are prepared by fangahawk, akcube, JadeReaper, aj_uba and me. We would like to thank codelegend, aditya.verma, keyurchd_11, menavlikar.rutvij, GenghizKhan and AbhijnanVegi for testing the round and mhardik003 for designing the poster.

We'll post an editorial after the contest is over. We hope you'll enjoy it!

Winners (In case a person is winning in two categories, he/she is given the award with higher prize money).

Global
1. geothermal
2. tranxuanbach
3. bench0310

National
1. anshugarg12
2. iceknight1093
3. shlokg329

IIITH
1. dheeraja7252
2. shivensinha4
3. sigma_g

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

Comments Comments (22)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by amul_agrawal (previous revision, new revision, compare).

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by amul_agrawal (previous revision, new revision, compare).

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

As a tester, I would encourage all of you to take part in the contest :) The problems are very interesting!

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

    Seconded. Fun problems and a unique contest type, definitely worth trying!

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

As a tester, I enjoyed solving the problems. The bugs in the codes are pretty subtle. I hope to see comments from many satisfied contestants post contest.

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

Will the format be similar to April Fools Contest?

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

    No, I think the format's different.

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

    No. Take this problem as an example, https://www.codechef.com/DGTC2021/problems/AVGNUMBS

    The solution for this problem is as follows
    → Reply
»
3 years ago, # |
  Vote: I like it +33 Vote: I do not like it

A very entertaining event, has been fun over the past 2 years, will surely recommend to join!

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

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

Thanks to the authors for the contest! My solutions:

Kalakshetra:

The solution divides by $$$k$$$; therefore, the solution RTEs when we take $$$k = 0$$$.

Princess and Deja Vu:

In the a == 0 case, one of the conditionals reads b = 3 rather than b == 3. This statement always evaluates to true, so we can force a WA by ensuring that a = 0 and b equals none of $$$0$$$, $$$2$$$, or $$$3$$$. One way to do this is to force $$$n_inv$$$ to be $$$6$$$, which occurs when $$$n = 91$$$.

A Simple Problem:

The given solution stores len as a char, leading to overflow when its value is large. Thus, generating a string of 500 a's breaks the solution.

Logistics Work:

The code uses binary search to find $$$\sqrt{x}$$$ but assumes $$$\sqrt{x} < x$$$. Thus, it will incorrectly determine the side-length of a frame whose length is less than $$$1$$$. For example, taking a single frame with area $$$0.25$$$ gives the desired error, since the program prints a perimeter of $$$1$$$ while the true perimeter is $$$2$$$.

Inaugural Dances:

The given solution performs only a single DFS, starting at index $$$0$$$, rather than a separate DFS for every connected component. As such, if the graph is disconnected, the solution will assign every vertex outside the component of vertex $$$0$$$ to team B.

Thus, we can break the solution by creating a graph with multiple connected components, including some edges outside the component of vertex $$$0$$$. For example, taking the array $$${1, 3, 2 }$$$ breaks the solution because the last two dancers will both be assigned to team B, which is invalid.

Class Monitor:

The greedy approach implemented in the given solution is incorrect. One counterexample is to take the array $$${p, q, pq, p^3 },$$$ where $$$p$$$ and $$$q$$$ are primes such that $$$p^3 > pq.$$$ Then, the program will generate three lines: $$${p, pq }, {q },$$$ and $$${p^3 }.$$$ However, it is possible to use two lines: $$${p, p^3 }$$$ and $$${q, pq }.$$$

Vindhya Troubles:

The given solution does not consider all possible edges in the graph. For example, consider the case $$${3, 2, 2, 2, 6 }.$$$ The given solution will find edges between the $$$2$$$'s and from the $$$6$$$ to the rightmost $$$2$$$, but it does not consider the edge from the $$$6$$$ to the $$$3$$$. Submitting this case for a sufficiently large $$$k$$$ hacks the given solution.

Spoiled for Choice:

The given solution takes the modular inverse of $$$dp[i]$$$, but $$$dp[i]$$$ may be $$$0$$$ mod $$$10^9 + 7$$$. For example, consider the array $$${1000000000, 7 },$$$ with one student. The answer is then $$$10^9$$$, as there are $$$10^9$$$ choices at the first stall and $$$10^9 + 7$$$ choices at the second. However, because product is set to zero, this solution prints zero.

QIF in OBH:

The given solution's implementation of the articulation point finding algorithm is incorrect. Rather than setting low[i][j] = min(low[i][j], low[ni][nj]), if is_child is false, we must set low[i][j] = min(low[i][j], disc[ni][nj]). This error sometimes causes the given solution to determine there are no articulation points when one exists.

My countercase is as follows:


7 6
..###.
..#.##
######
#.#.##
###.##
....##
....##

The given solution prints 2, but in fact, the third point in the third row is an articulation point.

Incidentally, if anyone has an explanation of the intuition underlying why this breaks the solution, I'd love to hear it. I was able to follow the general logic well enough to construct a countercase by building the below graph and then figuring out a way to embed it in a grid, but I don't have a great intuitive sense of why it works.

Fun fact: I had to resubmit my solution to CEOI 2019 Problem 1 in the middle of the contest to confirm that using low instead of disc actually breaks the articulation point algorithm, since that's the last contest I can remember in which I had to find articulation points :)

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

    (QIF in OBH) Don't know if this adds anything new, but here is my intuition for the mistake in computing articulation nodes:

    $$$low_u$$$ is the lowest node (by discovery time $$$disc$$$) that you can reach if you take one back-edge from $$$u$$$.

    But using $$$low_u \leftarrow \min(low_u, low_v)$$$, where $$$v$$$ is an ancestor of $$$u$$$, you effectively compute the lowest node you can reach taking any number of back-edges. And you may end up not detecting an articulation node, because you skip over it with multiple jumps.

    So for the problem, you need to construct a graph where the articulation node $$$u$$$ has a back-edge (to some ancestor), and it has a descendent which has a back-edge to $$$u$$$.

    The mistake itself is somewhat similar in spirit to updating knapsack in forward and reverse.

    // (1)
for (int s = N - 1; s >= x; s--)
  dp[s] += dp[s - x];

// (2)
for (int s = x; s < N; s++)
  dp[s] += dp[s - x];

    (1) computes the number of ways to form a sum $$$s$$$ using $$$x$$$ at most once, and (2) computes the ways to form $$$s$$$ using $$$x$$$ any number of times.

    The same way we fix the knapsack DP by reversing iteration order, we can fix the DFS as:

    void dfs(int u, int p) {
  disc[u] = low[u] = ++timer;
  for (int v: adj[u]) {
    if (v != p && !disc[v])
      dfs(v);
  }
  for (int v: adj[u]) {
    if (v != p)
      low[u] = min(low[u], low[v]);
  }
}

    Computes $$$low$$$ in post-order instead of live updating in-order. Additionally, we can get rid of $$$disc$$$ here.

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

The problems were amazing!!

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

Spoiled for Choice was really awesome and thanks a lot for the contest enjoyed a lot.

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

In the problem "spoiled for choice", I think the following is also a hack test:

1
4 3

The given solution prints 11 (I think) but the answer is of course 7. However, I received a WA verdict.

Also, I was little confused about the problem statement itself. The students being different doesn't seem to be accounted for in the sample. If the final group order is given as a set of (student, variety) pairs, then the sample has a few more cases (first student never ordered from the 3rd shop). Could someone please clear it up for me?

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

    Thanks for pointing this out!

    Initially, we had a problem statement for which the code matched correctly. However, upon testing, we received feedback that the statement was hard to decipher, hence we tried to come up with a similar and easier to read statement that would have the same solution. Unfortunately, we failed to notice the fact that in the new problem there would be over-counting, as well as the need to account for the uniqueness of the students.

    We've rejudged all the Wrong Answer submissions, and sincerely apologize for the inconvenience caused and for overlooking these errors.

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

      Cool! In a way I did fail to find the error mentioned by Geothermal above that lead to all this overthinking lol. Really smart tasks! I would've missed the char len one had I not started to copy down the code (´-﹏-`;)

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

Thanks for the contest, it was awesome! What I liked the most was that all problem statements were quite clear and the code was crisp clean to read, which made finding the hack case much easier.

I especially liked Logistics and the Simple Problem because they had simple but cute bugs, which I may do in real-life code too.

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

We had a couple of issues with some of the problems. The issues are as follows:

  1. OBHQIF: There was a mistake in the problem statement which was fixed during the contest. Penalties for all the submissions which got affected due to this will be removed.

  2. CLASSMONITOR: There was a minor typo in the problem statement which was fixed during the contest. Penalties for all the submissions which got affected due to this will be removed.

  3. LOGISTICS: The given code had one more error that we didn't spot during testing. We have corrected the checker and rejudged all the submissions.

  4. SPLDCHC: There was a mistake in the problem statement. We have rejudged all the submissions.

We sincerely apologise for all the inconvenience it caused. We hope you liked the problems and the contest format. 

Editorials can be found here:

KALAKSHETRA: https://discuss.codechef.com/t/kalakshetra-editorial/99916

SIMPLEPROB: https://discuss.codechef.com/t/simpleprob-editorial/99912

PRINCSDJVU: https://discuss.codechef.com/t/princsdjvu-editorial/99913 

LOGISTICS: https://discuss.codechef.com/t/logistics-editorial/99911 

INAUGDNCE: https://discuss.codechef.com/t/inaugdnce-editorial/99914 

VINTRBL: https://discuss.codechef.com/t/vintrbl-editorial/99915 

CLASSMONITOR: https://discuss.codechef.com/t/classmonitor-editorial/99910  

SPLDCHC: https://discuss.codechef.com/t/spldchc-editorial/99917 

OBHQIF: https://discuss.codechef.com/t/obhqif-editorial/99918 

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

Why didn't codechef all contests have any information about this event?

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

    There is a small toggle to show all contests on top right.

    → Reply