PROBLEM LINK:Author: Ilya Malinovsky DIFFICULTYmedium PREREQUISITESdynamic programming, graph theory PROBLEMYou're given a graph with vertices defined by 2 numbers (a, b), where a is the layer and b is the position in the layer. There is always an edge between (a, x) and (a+1, y), for every a, for each x and y. Also there are given some additional edges in the input. How many paths are from (1, 0) to (n+1, 0)? QUICK EXPLANATIONLet's start by a simple DP. One can notice the graph is a directed acyclic one, so one can apply this standard DP for counting number of paths: dp[a][b] = in how many ways can we arrive into (a, b). The trick is to speed it up by considering only states (a, b) that appear at least once in an additional edge. We sort all those pairs (a, b) in increasing order by layer and at equality, in increasing order of position in the layer. When you are at a layer a, the only information that really matters is in how many ways can you reach (a  1, x), for each x. With careful calculation, this can be computed. EXPLANATIONNo cycles Let's start by studying the properties of the given graph. One may notice the graph is a directed acyclic one (noted DAG). Why? A directed edge increases either the layer or the position in the current layer (because all edges are directed from left to right). Suppose we get a cycle ABCD. Layer of D will be greater than layer of A or position of D will be greater than position of A in the same layer. However, as we get a cycle, it means we also have an edge DA. This contradicts our previously stated fact, so no cycle can exist. Hence, the given graph is a DAG. Count number of paths in a DAG For now, let's assume the limits are small enough to simply iterate over all vertexes. Then the problem is solved by dynamic programming. Let ways[layer][pos] = in how many ways can we reach vertex defined by (layer, pos). We have two choices
In the end, the answer is given in ways[n + 1][0]. This approach is way too slow, but hopefully we can optimize it. Speeding it up The trick to optimize our solution is to notice only pairs (x, y) such as at least one edge0 = x and edge1 = y or edge2 = x and edge3 = y are actually the ones needed to iterate. Suppose we consider a pair (x', y') such as it's not in the set of pairs (x, y) mentioned above. Then, ways[x'][y'] is always equal to ways[x'  1][0] + ways[x'  1][1] + ... + ways[x'  1][m  1]. Let's have all unique pairs (x, y) sorted in increasing order by x and at equality, in increasing order of y. We can calculate ways[x][y] easily if we have sumLayer(x  1), which means ways[x  1][0] + ways[x  1][1] + ... + ways[x  1][m  1]. The task is reduced to quickly calculate sumLayer(x). If we can do this, the whole task can be solved. Let's assume that x is the layer of the current vertex and x' is the layer of previous vertex. Suppose sumLayer(x') is calculated and now we want to calculate sumLayer(x). Once again, sumLayer(x) can be obtained in two ways
There is one detail left  how to handle pairs like (a, b), where both a and b can have large values. For C++ programmers, we can use a container like map. Other approach might be to simply sort the array and refer to a pair as its index in sorted sequence. This way, no map is required at all, but the code becomes more complex. Time Complexity We iterate over all M edges. Each step, our most expensive operation is doing binary exponentiation and the exponent is up to N. So our complexity is $O(M * \log(M))$. AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 09 Feb '15, 19:54

There must be something wrong with subtask #9 data... is there a way to get the data or check it complies to constrains? answered 17 Feb '15, 01:14
You can write your own check using assert statement, just read all input and output some value. If there is constraint problem, you will have SIGABRT, WA otherwise...
(17 Feb '15, 01:20)
I also had the same problem on case #9, I think it has something to do with the inbuilt sort function, as it uses quick sort, when i used std:stable_sort() which uses merge sort it passed the time limit quite easily.
(17 Feb '15, 18:02)

Was I the only one to calculate the entire polynomial expression in m, and then calculate its value :P Got TLE for the last case http://www.codechef.com/viewsolution/6273343 answered 17 Feb '15, 05:20

I think I am missing something here. Lets say you have new edge 0 0 1 0, then another edge 3 0 4 0. Doesn't the sumLayer(3) has to count for the effect of the added edge 0 0 1 0 ? As I understand from the editorial, the sumLayer(3) will still be ways[2][0] + ways[2][1] + ... + ways[2][m] as if the edge 0 0 1 0 had no effect on them (we don't modify ways[2][0..m]...) But what I see is that with the new edge 0 0 1 0, the number of ways to reach layer 2 is greater than without this edge. However in this solution I don't see this effect taking place. answered 17 Feb '15, 11:14

An easy implementation can be done by Hashing all calculated layers , so it can be reuse. How ? when calculating all path by edge A>B we pick all path from source(0th level) to A from the hash . time : sorting O(KlogK), solving O(K) {if no collision} so overall O(KlogK) source : link text answered 17 Feb '15, 13:06

I used a linear dp with binary search. I am not able to figure out which test cases it failed. Here is the link to my solution http://www.codechef.com/viewsolution/6295573 I will be really glad if somebody could tell me the mistake. answered 17 Feb '15, 13:24

Go by a "special" edge. In this way, ways[layer][pos] is sum of ways[edge0][edge1], such as edge2 = layer and edge3 = pos. please explain??? answered 19 Feb '15, 22:09

This is the logic I used: while taking input of the edges, if the newly added edge belongs to adjacent layers, I discard it. I sort the edges with increasing destination layers and if the destination layers are same, sort it by vertex. I maintain a cnt[] such that cnt[i]=dp[i][0]+....+dp[i][m1] for all i k=1; for(i=2;i<=n;i++){
but it gives WA is some cases of subtasks 1 and 2 full code is given here http://www.codechef.com/viewsolution/6322419 Can you please tell me for which test cases is it giving the wrong answer? `
link
This answer is marked "community wiki".
answered 20 Feb '15, 18:10

without any constraints on the solution,how you have applied DP? it is counting problem Regards Samuel answered 25 Feb '15, 11:00
