sigma_g's blog

By sigma_g, 4 years ago, In English

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!

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

| Write comment?
»
4 years ago, # |
  Vote: I like it +70 Vote: I do not like 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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it -19 Vote: I do not like it

    No, this is not fft and Science is not required for naming an institution lol.

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Looking forward to a fun contest!!!

»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Will there be a CodeForces contest as part of Threads this year ?

»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

»
4 years ago, # |
Rev. 3   Vote: I like it +11 Vote: I do not like it

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?

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

    100000 0
    Its fills visited for each vertex in $$$\mathcal{O}(n)$$$

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Thanks for your feedback! :) We will surely be coming up with another contest next year.

»
4 years ago, # |
  Vote: I like it +25 Vote: I do not like it

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 $$$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

  • 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 $$$\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 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

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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)

    hack
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

why does this give partial score? For task B.

Snippet
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi, it gets time limit exceeded.

    test case

    Your approach is in the right direction, but it had to be like this.

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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)