Time Limit Exceeded in SJ1 Even after Fast I/O

Problem Link - https://www.codechef.com/problems/SJ1
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.

In your given example


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

I have just replace the

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


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

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

            for (int i = 1; i <= n; ++i) {
                temp2[i] = in.readLong();
           //TLE solution

readLongArray is basically doing same thing but why it is TLE in second case?

Bro there is a very simple way to do all this. You are complicating stuff :slight_smile:

Ha ha. I got it. BTW thanks. :smile: