Invitation to DeCode, Felicity Threads IIIT-H

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 Monday, February 10, 2020 at 20:30UTC+5.5. 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 7 stars to 1 star , but of course, we welcome everyone to participate!

Registration link . Please register as a participant. Be sure to read the rules. The rules, scoring distribution, etc. have been announced on the group blog, please check it out!

Thanks to the setters: sigma_g, animesh1309, destiny_son, arpan_dg, ishita3110, saxenapragun, and me, tanuj208 and the testers: dk502, kanish_anand, akshat_goyal, manish_1729, and b00merang.

We’ll post an editorial in this thread after the contest is over. We hope you’ll enjoy it!

5 Likes

Reminder: the contest starts in twenty minutes. Don’t forget to read the rules here.

1 Like

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

  1. #define INF 1e9 . This should be a bigger number (like 1e18). (answer can be larger than 1e9)
  2. 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: https://www.desmos.com/calculator/wn5sappygr

2 Likes