the problem with your code is that during your BFS call you are initialising the distance array and visited array which results in a O(N^2) running time.
You are setting the entirety of the levels array to 0 for each component which goes to \mathcal{O}(n^2) when you get a graph with no edges. (Specifically lines 99 and 107 are at fault)
Same error in @sudheerays123’s code.
1 Like
Your memset function was slowing down your code astronomically, just a little modification in the markNodes( ) function and your code works fine.
1 Like
Oh my god, don’t do this to me 
I cannot believe that I forgot that the levels array handles itself and that I didn’t need to reset the variables each time 
@islingr, thanks for the debugging help!
Well in the end, the fault always lies with the coder, not the system. Lesson has been learnt.
No, if the graph has c connected components your code takes \mathcal{O}(cn) time which should TLE even if there are many more edges.
You don’t have to set the levels array to 0 before each dfs call simply setting it to 0 at the start of the test case suffices which gives an \mathcal{O}(n) time complexity.
1 Like
Yep that’s right, or you could you pass the parent’s level itself as a parameter and not worry about explicitly storing the levels.
I too got TLE for the graph problem.
Here’s my CPP code : CodeChef: Practical coding for everyone
What went wrong? Was it something language specific?
We aren’t allowed to access the code, submit it on INOIPRAC with your normal account and then send the link.
Oh thanks! I have updated the link.
Again it’s the same error as @tush_chen and @sudheerays123.
The lines from 64-74 have complexity \mathcal{O}(c n) where c is the number of connected components this is because you set the entirety of the visited array to false for each component.
Oh argh. Thanks for the help!
results are out
Congrats to you and everyone else who qualified! 
Congratulations to all who got selected and to all who didn’t as they atleast reached INOI(including myself).
2 Likes
Yup, congrats everyone! Honestly INOI is big enough for small coders like me 
(For the whole of this post, I have assumed that the removed corner in the case of dp2 is in the upper right corner , i.e. it is in the first of the 3 rows and nth of the n columns)
I have a question.
While making the recurrence relation for dp2,
First you put 2 3x1 blocks below the removed corner and then put a 3x1 block above those two and to the left of the removed corner to get dp2[i-3]. I understood that part.
For the second case, you put a 2x2 block below the removed corner and then got dp3[i-1]. Is there a specific reason why you didn’t put a 3x1 block above that 2x2 block and to the left of the removed corner ( as that is the only block that can go there) to form a different dp3?
I am finding it hard to implement dp3 that way. Has someone else done it that way?
Also how do you go about finding the base cases for such a problem?
I hope you get what I am trying to say.