Tired of ACing problems? Bored of seeing green Accepted all over your submissions page? Want something more adventurous?
What if we gave you the complete solution, and challenged you to then get an AC? Confused? We are proud to invite you to DeCode 2020, as a part of Threads, Felicity IIIT Hyderabad! The contest will be held on [contest_time:268401]. We will have prizes for top three Indian participants.
You'll be given problems and their buggy solutions. Your job will be to figure out on what test cases the buggy solution fails, and also fix the buggy solution itself. The solutions are exclusively written in C++.
You will have eight problems and two hours to solve them. The problems are a good mix for participants from international masters to pupil, but of course, we welcome everyone to participate!
Registration link. Please register as a participant. The rules, scoring distribution, etc. have been announced on the group blog, please check it out!
Thanks to the setters: night_fury208, AnimeshSinha1309, madlad, Arpanet, firebolt, pragunsaxena, and me, sigma_g and the testers: dixitgarg, ninja_28, akshat_goyal, Horcrux1729, and b00merang. Special thanks to MikeMirzayanov for the wonderful Codeforces and Polygon systems for making this contest possible!
We'll post an editorial in this thread after the contest is over. We hope you'll enjoy it!
TIL there exist IIT Hyderabad and IIIT Hyderabad and they are not the same place :O
One day, science will find a way to create IIIIT Hyderabad.
No, this is not fft and Science is not required for naming an institution lol.
Looking forward to a fun contest!!!
Will there be a CodeForces contest as part of Threads this year ?
Ya we are preparing a contest . Hope you soon find it on CodeForces.
When is it ?
Reminder: the contest starts in twenty minutes. Don't forget to read the rules here.
Nice round I enjoyed ACing Buggy solns. Make More :). What was the test-case when the diameter of the tree is incorrect in Task-E?
100000 0
Its fills
visited
for each vertex in $$$\mathcal{O}(n)$$$Thanks for your feedback! :) We will surely be coming up with another contest next year.
Thanks for participating in the contest! We hope you enjoyed it! We are sorry for the rejudging in two problems. We will announce the winners soon in this thread. Here's the editorial:
Pattern maker
Simple dilemna
The given buggy solution failed because it was outputting $$$x, y$$$ values larger than $$$10^9$$$, for $$$a,b=10^8$$$. Note that in the question it was specified that $$$x,y$$$ must be less than $$$10^9$$$.
To fix this, you may output $$$0$$$ and $$$\text{ceil}(\text{sqrt}(\text{abs}(a-b)^2))$$$. You may verify the conditions are satisfied. Other solutions also exist, like searching for the closest perfect square to $$$\text{abs}(a-b)$$$. The search loop will not TLE because the gap between two consecutive perfect squares in that region is around $$$10^4$$$ ($$$(n+1)^2 - n^2 = 2n+1$$$).
Alice and her Best Number
Trouble in the valley
Many participants tried to find logical errors. Actually, the code is logically correct, and the only mistake in this code is the
strlen(s)
call inside the for loop. The complexity ofstrlen(s)
is linear in length of string. This function is called once per character of the string. Therefore, the complexity of thefor
loop on line 11 is $$$\mathcal{O}(n^2)$$$. Therefore, to hack this code, you can output any string of length $$$10^5$$$. To fix this, just store the result ofstrlen(s)
in a separate variable outside thefor
loop.Disastrous diameter
When there are two or more very large components in the forest,
fill()
call will TLE since it fills the whole vector of size $$$n$$$ every time the dfs call is executed. Therefore, the simplest hack case to this problem is100000 0
(all nodes disjoint).There are multiple ways to fix this, including using a stack to keep track of all nodes that were visited so far. Or since the graph was only a tree, you could use the standard tree dfs (
int curr, int prev
) to traverse the forest.Number Play
There are 2 bugs here
#define INF 1e9
. This should be a bigger number (like 1e18). (answer can be larger than 1e9)get_occurrences()
function,X*=tmp
line will cause overflow at some point. If that is causing overflow, you can just exit from while loop.So hack case would be any big test case, for eg
1000000000000000000 97
Sort the suffixes
We hope you will be familiar with Suffix arrays, and that is the entire solution to the original problem. The problem with the buggy code is that in the string passed to the suffix array should have had a
$
at the end. Otherwise, without a terminal character, the second counting sort will mess up the results of the first. Therefore, some case like cccc with the same 2 letters somewhere in the middle consecutively will hack the solution.Australian Bushfires
Our incorrect solution, the DSU tracks if there is a cycle formed, and counts the number of times the curve intersects the y-axis, and if that's even, it contains the origin, if odd then not. The DSU fails if the inserted edge is makes the number of intersections even, but one of those intersections is not a part of the cycle.
The solution image is here: https://www.desmos.com/calculator/wn5sappygr
For the suffix array problem, there are some cases for which there should be UB (out-of-bounds index access), but such hack gives 0 points because it runs correctly on CF :(
I use debug flags so I found the case almost instantly (didn't notice the $ though)
You are right, sorry about that! Our code should have had the vectors of size 2*n (lines 16 and 17), instead we had taken n only.
why does this give partial score? For task B.
Hi, it gets time limit exceeded.
2 98549055 20920647
Your approach is in the right direction, but it had to be like this.
Thanks to everyone who participated.
Congratulations to the winners
Rank 1 : codelegend (with 10650 points)
Rank 2 : Rahul (with 8150 points and 7 penalties)
Rank 3 : atrophy98 (with 8150 points and 10 penalties)