# Time Limit Exceeded in SJ1 Even after Fast I/O

My solution - https://www.codechef.com/viewsolution/24041293

Updated Solution Without WA and 1 based indexing - https://www.codechef.com/viewsolution/24048002
(Still not working)

I am not able to get why my solution is giving TLE for all cases except 2 cases.
I have commented the relevant part of my code.

My approach -
Storing graph as Adjacency List (Undirected). Storing v_i and m_i for each node in array p of Pair class where p[i].first represents v_i and p[i].second represents m_i.

I have traversed the using DFS from root by passing v_{root} and checked if the current node curr is leaf node or not.
For checking if it is leaf node I have checked if the size of adjacency list of curr node \leq 1.

If it is leaf node then I will calculate the g_{rl} = gcd (gcdtillnow, v_{curr})

where gcdtillnow was passed at every step of DFS.

Then again g_{m} = gcd(g_{rl}, m_{l_i}) and subtracting this value from m_{l_{i}}, then I have added this result with the leafno l_i in TreeMap. In c++ terms I think it is sorted_map.

If the curr node is not dfs then send the value gcd_{rc} = gcd(gcdtillnow, v_i)

Why I am getting TLE. Can anyone help me out.
If any clarification require in my explanation then please mention.

Thank You

Note that You are getting a WA too,try to get that first.

As far as your code goes â€¦I can see you are obtaining a DFS from root to one of the leaf nodeâ€¦and then for rest of the not visited leaf nodes again you are starting from root.
Imagine a tree with n nodes be like 1----2----3-----4------5-----6----- upto n/2 i.e a straight depth of n/2 and then the last n/2 th node has n/2 childs (In total n nodes).
If you get to one of the leaf using DFSâ€¦(i.e recursively to a depth of n/2)â€¦ for the rest n/2 -1 nodes if you start from root again the depth you traverse is n/2.

In General the time complexity for one node is O(n/2) therefore for n/2 leaf node it is (n/2) * (n/2) i.e (n^2/4). .Basically O(n^2).I suppose thatâ€™s the reason why you are getting a TLE.

Hope this helpsâ€¦Do let me know if there are further queries OR I didnâ€™t get your approach rightâ€¦

1 Like

My bad I have interchanged a root with node thatâ€™s why you got confused. I am sorry. Now I have corrected my approach. Please have a look at it again.

I am doing DFS on whole tree only once by calling it on root once, then I am calling recursion of DFS on its adjacency list if the node is not visited. And For skew tree I have corrected my solution (for the case where only leaf node is root itself) and hence one more test case got accepted. But still there is TLE. I have updated my answer for new Solution.

My DFS will start from 1 then when it reach the 4 the base case will hit and it returns to 3 and then it will DFS into 5^{th} node and so on. It will not come back to 1 untill and unless all nodes are traversed.

use the code for fast input output and then submit

I have already used the code for fast I/O

I would suggest you to optimize your code in the TreeMap partâ€¦Every time you add an element it takes time to keep element in sorted orderâ€¦

As you are calculating GCD recursively for every node in O(nlog(max)) time â€¦store GCD for every node in a global array(say A[n+1])â€¦For every node(say x) that is leaf print its corresponding GCD(A[x],m[x])â€¦This will save the extra log(n) part used in adding elements in the TreeMap every time you find a leaf.

1 Like

There are some tweaks I made.
I was using linked list for adjacency list and get(i) is costly so I replaced with Arraylist.
Yes TreeSet was expensive so I made a pair array <Boolean (isLeafNode), Long (gcdFinalcal)>.

The last thing I didnâ€™t understand is that
https://www.codechef.com/viewsolution/24071791 is accepted solution and
this is not
https://www.codechef.com/submit/complete/24071806

I have just replace the

            long[] temp1 = IOUtils.readLongArray(in, n + 1);
long[] temp2 = IOUtils.readLongArray(in, n + 1);
//accepted solution


with

            long[] temp1 = new long[n + 1];
for (int i = 1; i <= n; ++i) {
}

long[] temp2 = new long[n + 1];

for (int i = 1; i <= n; ++i) {