CHEFGRPH FEB15

How precisely can we boil down the time complexity to O(k log k)

There is not mentioned much in the editorial

How is it we are doing??

Someone please explain

1 Like

My approach may be different from the editorial (I have not read the editorial).

The underlying principle in my approach is that each newly added edge affects the final answer

So the main focus is to be on the newly added edges rather than the original ones.

Now for each newly added edge it will propagate the changes from it’s ending node.

Now what I did was :

First let us forget about the newly added edges.

Let us pick ith node in the jth layer.

To calculate the number of ways to reach from it to the last layer we must know the same answer for each node in the next layer.

So dp[j][i] = sum of (dp[j+1][k]) where 0<=k<m

If you calculate it for smaller values you will notice a pattern.

dp[j][i] = m^(n-j)

Now taking the newly added edges into consideration we can know that the final answer would be m^n + the value change brought by the new edges.

Now talking about the newly added edges ,

As you can see k <=10^5 so you can see at max a O(k log k) algorithm would work.

Now sort all the edges according to the ending layer and if clashes occur then use ending pt .

What the above statement means is that first sort in the decreasing order of end points then in case of clashes sort according to node number within the layer.

(A)Now this sorting works because a edge(e) can affect another edge(f) only if e’s starting layer is comes after f’s ending edge.(Try to visualize or make a graph on paper and test it out )

After this concept is understood the only challenge is to code it.

So what I did in my code was(one with 50 pts) I saved the change each edge caused. So when considering a new edge I know all edges coming after it have been handled , I use their changes to calculate the change of the current edge being considered.

So for each new edge I am considering I first loop through all the edges I have considered and follow the necessary condition(A).

After that only thing that remains is the original ways to reach the last layer from the ending pt of the new edge.Add it and effect of the current edge on the answer is calculated.

Save it and move to the next edge.

It takes O(k^2). First code it, if it works (gets you 50 pts) then I will tell you the O(k logk) aprroach.

This approach I have described may appear as vague but if you have spent enough time on the question you will understand it.

The O(k logk) approach

Now if we store the edges in a extra array(B) and sort them according to the starting point it will help in reducing the complexity.

Now for ith edge all the edges before it would have ending point in the same layer or in a layer with number greater than the edge being considered.

So keep a ptr through the newly sorted array B to keep track of already added edge’s changes.(Keep it in a temporary variable).

Whenever a new edge is being considered just add the new values to the temporary variable.

What the new values will be is the edges whose starting pt lies b/w the ending pt of the current edge being considered and the prev edge for which the value was created.

Now the corner cases are :

If a edge starts at the same layer as the current edge you would have to ignore it unless and until it starts at the same pt where the current edge ends©.

If next edge also ends at the same layer then just add C.

A fix is that whenever a edge ending at a new layer appears just keep a new temporary value for the current layer because of the sorting when all the edges ending at same layer are done then you would have to just add this value.(See my code for better understanding).

2 Likes

Got the 50
What about 100?

I will edit the answer.