Can someone please share some hint for DINCPATH
DP on edges. DP[i] should be the answer to “what is the longest doubly increasing path that starts at edge i”
Well, I applied Topological sorting here. First of all I will create a directed graph where only those edges u->v will exist where a[u]>a[v]. So, definitely there will not be any loops,self loop. Now, apply topological sorting. and in that order, accumulate new answer for all the children. You will need sorting and prefix max array. Refer to this solution 
https://www.codechef.com/viewsolution/24067255
2 Likes
You didn’t need to explicitly perform topological sorting… you can just compute in increasing order of a[i], since edges always lead from smaller to larger. 
1 Like
Yes, Indeed. Thanks for pointing it out.
Sorry but i didn’t get it…can you please explain why top sort is required and what to after that?
See, for each node i, I am storing what will be the value of longest path if previous difference is P. So, first I should visit all the nodes which are ancestor of this node. So, I applied topological sort to automatically visit those nodes before.
1 Like
I don’t get what would happen if a node has more than 1 parent? I mean if there are two or more vertices pointing at the current vertex. It is a possibility since we are working on a DAG.
You don’t DP on nodes, you DP on edges.
Can u give the link to your solution, I don’t understand how to apply dp here.
A more Simpler version of this problem
Editorial is also quite simple to understand.
Just make a few changes and you can go with this problem.
2 Likes