INOI 2020 Discussion

general
,
67

Can anyone who is in class X and above and who got 100 abv tell me since when they r into competitive programming??

68

I got 132 and started a month ago.

1 Like
69

Got 132 and doing since 1.5 years :joy:

70

Any idea when the results will be declared?

2 Likes
71

Uhhhhh, wait what??

If you did not clear it, you get a TLE? That’s messed up :joy:

But no, I did clear all my adjacency lists and even reset my global variables. I wouldn’t have got an AC on all other tests cases.

My code wasn’t wrong, I checked by downloading the zip file and running all test cases. We are talking about why several of us faced TLE’s in our code despite coding the inherently same logic. We aren’t concerned with those that got WA(s).

72

Please send the rewritten code here. I’m willing to try to find the issue

73

  1. INOI marks are out, they’ve been mailed to us.
    According to the mail, tentative cutoff is 200 for X and above and 132 for IX and below.

  2. We can access our exam accounts now so @tush_chen send your code, I’m curious to see what the problem may have been.

74

Even I had the same problem

Here is my code : #include <bits/stdc++.h>using namespace std;#define fastio ios_base::sync_wi - Pastebin.com

Can someone pls tell me why I was getting TLE
Thanks :slight_smile:

75

And here I was thinking people talking about 200 cutoffs are being funny…

1 Like
76

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.

77

@islingr, Well here is my code: CodeChef: Practical coding for everyone

78

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
80

Your memset function was slowing down your code astronomically, just a little modification in the markNodes( ) function and your code works fine.

https://www.codechef.com/viewsolution/29045325

1 Like
81

Oh my god, don’t do this to me :sob: I cannot believe that I forgot that the levels array handles itself and that I didn’t need to reset the variables each time :exploding_head:

@islingr, thanks for the debugging help!

Well in the end, the fault always lies with the coder, not the system. Lesson has been learnt.

82

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
83

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.

84

@tush_chen As I said to you. I am happy you understood the fact.

85

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?

86

Yes @tush_chen
Even I did this and got TLE
Now changed it and got AC :frowning:

1 Like
87

We aren’t allowed to access the code, submit it on INOIPRAC with your normal account and then send the link.