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
- Bug: extra semicolon in front of outer for loop.
- solution : just remove the semicolon
- hack case : any whole number greater than 1 and less than equal to 1000.
Simple dilemna
The given buggy solution failed because it was outputting x,y
values larger than 109, for a,b=108. Note that in the question it was specified that x,y must be less than 109
.
To fix this, you may output 0
and ceil(sqrt(abs(a−b)2)). You may verify the conditions are satisfied. Other solutions also exist, like searching for the closest perfect square to abs(a−b). The search loop will not TLE because the gap between two consecutive perfect squares in that region is around 104 ((n+1)2−n2=2n+1
).
Alice and her Best Number
- Bug: If the number of numbers which are twice greater than or equal to all numbers or twice of a number is less than all numbers are both one each.
- solution : change line number 34 to “if (count+count3==1)”
- hack case : 40 10 10 1
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 of strlen(s) is linear in length of string. This function is called once per character of the string. Therefore, the complexity of the for loop on line 11 is O(n2)
. Therefore, to hack this code, you can output any string of length 105
. To fix this, just store the result of strlen(s) in a separate variable outside the for 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 is 100000 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)
- In the
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: Graphing Calculator
