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

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

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

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.

Will the format be similar to April Fools Contest?

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

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

The problems were amazing!!

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

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?

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.

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 

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