YANSPP - Editorial

editorial
, , , , , ,
1

PROBLEM LINK:

Contest - Division 3
Contest - Division 2
Contest - Division 1

DIFFICULTY:

MEDIUM-HARD

PREREQUISITES:

0-1 BFS, All Pairs Shortest Path, Modular Exponentiation

PROBLEM:

Given an integer K and a graph of P nodes, where P is prime. For each vertex u, there exists a directed edge from u to (K\cdot u+i)\mod P with weight i, for all 0\le i\le K-1.

You are given Q queries, each asking the length of the shortest path between two nodes, if a path exists.

EXPLANATION:

We first solve the trivial case where K\equiv 0\mod P.

Solution

The i weighted edge from node u goes to node (K\cdot u+i\mod P) = (i \mod P), for all u. Thus, the weight of every outgoing edge to node v is v (if there are multiple directed edges between two nodes, only consider the least weighted one).

As there exists a directed edge between all pairs of nodes (since K\ge P), it is always possible to travel from X\to Y, with cost Y. Since all edges to node Y have weight Y, the least cost to travel from X\to Y is Y.

We now only consider K\not\equiv 0 \mod P.

Let G denote the graph formed by removing all edges with non-zero weight from the original graph. What interesting properties can we find in G?

Pictorial Intuition

Given below is G, constructed from the initial graph with K=8,P=13.

We can see two interesting properties here:

  • The graph is composed of several cyclic components.
  • The length of each cyclic component is the same (excluding the component whose sole constituent is node 0).

The proofs of these observations are given below (while the implications of these properties may not seem evident, they constitute a crucial part of the solution!)

Claim: The graph G comprises of (possibly many) directed circular subgraphs, and the length of each cycle is the same (the subgraph whose only member is node 0 being the exception).

Proof

It is easy to deduce that, in graph G, there exists no incoming/outgoing edge to/from node 0.

For all other nodes u, the only outgoing edge from node u goes to node (K\cdot u\mod P). Then, the nodes in G are chained as follows:

u\to (K\cdot u\mod P)\to (K^2\cdot u\mod P)\to \dots

Since K and P are co-prime, the laws of modular exponentiation tells us that the values in the above equation are cyclic. It is easy to see that the length of the cycle is equivalent to the smallest positive integer R such that:

K^R\cdot u\equiv u\mod P\implies K^R\equiv 1\mod P

Thus, each node u\ (u\ne 0) belongs to a circular subgraph of length R.

Recap: Let R be the length of the circular subgraphs of G. Then K^R\equiv 1\mod P.

We come back to the original graph.

Claim: The shortest path between any two nodes can be achieved by travelling through 0 and 1 weighted edges only.

Proof

For any edge u\to (K\cdot u+i\mod P), we show that it is possible to travel from node u to (K\cdot u+i\mod P) using only 0 and 1 weighted edges, with the same total cost i.

Consider an array of non-negative integers \{a_1, a_2, \dots, a_i\} such that, starting from node u,

  • travel through the outgoing 1-weighted edge once, then travel through the outgoing 0-weighted edge a_1 times,
  • travel through the outgoing 1-weighted edge once, then travel through the outgoing 0-weighted edge a_2 times,
  • and so on (for a total of i iterations).

The total cost of travelling in this fashion is equal to i. The final node can be described by the equation:

K^{a_i}(\dots(K^{a_2+1}(K^{a_1+1}(K\cdot u+1)+1)+1)\dots+1)\mod P

All that remains is to find suitable a_i such that we end up at node (K\cdot u+i\mod P). It can be verified trivially that setting a_x=R-1\ (x<i) and a_i=R makes the above equation equal to K\cdot u+i.

Thus, any shortest path using an i weighted edge can be replaced with a sequence of 0 and 1 weighted edges only, without affecting the total cost.

The problem is greatly simplified now, bringing down the total number of edges that we have to consider in the graph to 2\times P. However, calculating the shortest paths between any two nodes is still infeasible, due to the large number of nodes.

This is where we use the properties of G we described initially!

Case 1:

If the number of cycles (which is equal to \frac{P-1}{R}) in G is small, we can merge all nodes in the original graph that belong to the same circular subgraph in G, into a single node (since we can travel between these nodes using only 0 weighted edges).

Then, run Floyd Warshall on this compressed graph to get the shortest distance between any two components (which can be used to find the shortest distance between any two nodes of the original graph).

This approach works well when \frac{P-1}{R} \le 500. The total time complexity of this approach is:

O\big(P+\bigg(\frac{P-1}{R}\bigg)^3\big)

per test case.

Case 2:

When the number of cycles in G is large, the compressed graph (as described in the previous case) still has too many nodes to compute the APSP of the graph, within the time limit. Clearly, we need a different approach.

Notation: Let d(x,y) denote the length of the shortest path from node x to y.

Notation: Let Z_X denote the set of all nodes in G that belong to the same circular subgraph node X belongs to. That is, Z_X=\{K^i\cdot X\mod P\ \forall\ i\in\N\}.

Claim: d(X,Y)=\min_{X'\in Z_X} d(0,(Y-X' \mod P))

Proof

Define f(u, s) as the end node of the path:

  • starting at node u,
  • of length equal to the length of the (binary) string s,
  • where the i^{th}\ (1\le i\le |s|) edge in the path has weight s_i.
Explanation

Consider the graph where K=8,P=13. Let u=2,s=1001. Then, the sequence of nodes visited in the path looks as follows:

2\to_{1} 4\to_{0} 6\to_{0} 9\to_{1} 8

where \to_{i} represents an edge of weight i.
So f(u,s)=8.

We show that for any S, f(X, S)=Y if and only if f(0,S)=(Y-X'\mod P), for some X'\in Z_X. Proving this is equivalent to proving the original claim.

How does it prove the original claim?

Assume the above claim is true.

Then, if s is the sequence of moves of some shortest path from X to Y, it is also a sequence of moves that takes us from node 0 to (Y-X'\mod P) for some X'.

Since the cost of the path is solely dependent on s (sum of the elements of s to be exact), the above statement implies:

d(X,Y)\ge d(0,(Y-X'\mod P))

for some X'\in Z_X.

Similarly, the converse of the statement implies:

d(0,Y-X')\ge d(X,Y)

for all X'\in Z_X.

The two statements combined gives us:

d(X,Y)=\min_{X'\in Z_X} d(0,(Y-X' \mod P))

thereby proving the original claim.

It is easy to see that f(u,s)=K^\alpha\cdot u+\beta\mod P, for some constants \alpha,\beta determined solely by s. Therefore,

f(X,S) = K^\alpha\cdot X+\beta\equiv Y\mod P\\ \implies X'+\beta\equiv Y\mod P\\ \implies \beta\equiv Y-X'\mod P

Then,

f(0,S)=K^\alpha\cdot 0+\beta = \beta\\ \implies f(0,S) = Y-X'\mod P

The converse of the claim can be proved similarly.

Armed with this crucial property, we can solve the problem as follows -

  • First, compute the length of the shortest path from node 0 to all other nodes in linear time.

  • Then, to find the length of the shortest path from X\to Y, compute \min_{X'\in Z_X} d(0,(Y-X'\mod P)) by iterating over the R possible values of X'.

The time complexity of this approach (over all queries) is

O(P+Q\cdot R)

per test case.

SOLUTIONS:

Editorialist’s solution can be found here.

Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

  • 1
  • 2
  • 3
  • 4
  • 5

0 voters

1 Like