CHEFGRPH - editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Ilya Malinovsky
Tester: Pushkar Mishra
Editorialist: Florin Chirica

DIFFICULTY

medium

PREREQUISITES

dynamic programming, graph theory

PROBLEM

You’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 EXPLANATION

Let’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.

EXPLANATION

No 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 A-B-C-D. 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 D-A. 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

  1. Go by a “special” edge. In this way, ways[layer][pos] is sum of ways[edge0][edge1], such as edge2 = layer and edge3 = pos.

  2. Don’t go from a special edge. In this way, we have to arrive from the previous layer. Since between (layer - 1, x) and (layer, pos), there is always one edge, we can add to ways[layer][pos] sum of ways[layer - 1][x], for each x between 0 and m-1.

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

  1. Use special edges

    Then, we add to sumLayer(x) all values ways[a][b] such as we have in input a special edge a b x y. This can be done in parallel with computing ways[x][y].

  2. Do not use special edges

    Then, I claim that sumLayer(x) += sumLayer(x’) * power(M, x - x’). From each of layers x’ + 1, x’ + 2, …, x we can choose exactly one vertex. For each layer, we can make m choices, so by the rule of product we can arrive from x’ to x in power(M, x - x’). Also, this can be done for each path which arrives in x’, namely sumLayer(x’). Function pow(A, B) can be calculated in O(log2(B)) using binary exponentiation.

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:

Tester’s solution

Setter’s solution

2

There must be something wrong with subtask #9 data… is there a way to get the data or check it complies to constrains?

1 Like
3

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…

4

Was I the only one to calculate the entire polynomial expression in m, and then calculate its value :stuck_out_tongue:
Got TLE for the last case
http://www.codechef.com/viewsolution/6273343

5

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.

6

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

7

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.

8

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.

9

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???

10

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][m-1] for all i

k=1;

for(i=2;i<=n;i++){

  for(j=0;j<=m-1;j++){  
         dp[i][j]=cnt[i-1];
         while(k<=sizeof edge array && i==destination layer && j==destination vertex)
             dp[i][j]=dp[i][j]+dp[source layer][source vertex];
         cnt[i]=cnt[i]+dp[i][j];
   }
}

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?

`

11

without any constraints on the solution,how you have applied DP?
it is counting problem
Regards
Samuel