Anupam and Raja
Problem Setter: Soham Mukherjee
Problem Tester: Taranpreet Singh
Editorialist: Taranpreet Singh
Problem:
Given a graph with N vertices and E edges, with each vertex holding a value, initially zero. We are required to print these values at vertices MOD 1e9+9, where each query is described as:
- Given two integers u and k, add dist(u,vertex) + F(k) to all vertices, dist(u,v) is the smallest distance between u and v.
- Function F(K) is defined as: Number of was of selecting subset of points such that no two selected points are consecutive. First and last points are also considered consecutive.
Solution:
This problem can be solved using two insights:
- That F(K) is entirely independent of graph edges and values, and thus, can be calculated separately.
- Now, Since there is no modification query on graph, dist(u, v) remains same, and thus, can be calculated in advance. Also, N is set to max 300, which allow use to make a dist[N][N] array, storing pairwise distances.
Now, the problem is solved in two parts:
Getting the value of F(K) in O(logK) time (Since K <= 1e9 for worst case).
This part can be solved using matrix Exponentation.
If you are good at combinatorics, and had recognized the pattern, feel free to skip following para.
A good approach to solve such pattern problems is to make a guaranteed correct solution (usually slower for constraints, like bitmask, sub-linear or N^2 solution, depending upon problem). Then trying to recognize the recurrence, the relation between consecutive (or alternate) terms. This solves most of the series problems.
For F(k), We can build a bitmask solution to determine F(K) for smaller values.
By our slower solution, we will see the sequence, starting from F(1), as
2 3 4 7 11 18 29 47
If we ignore the first term of this sequence, we have a fibonacci sequence with first term 3 and 4.
F(1) was an edge case, because We can select out of 1 elements, two subsets, {} and {1}, hence F(1) = 2. But it does not satisfy the above fibonacci sequence. So, we handle K == 1 separately and for rest values, calculate F(K) using matrix exponentation (Same way as that for finonacci sequence). Refer this for details on matrix exponentation and this discuss in details various ways of calculating fibonacci numbers. I am leaving implementation upon you.
Creating Dist array and handling queries.
For pairwise distance grid, FLoyd warshall’s All Pairs shortest path problem in runtime O(N^3). Test cases were set to fail repeated dijkstra and Bellman ford algorithms for each nodes. Details about Floyd warshall can be read here.
So we have the dist array, we run each query as, calculate value of F(K) once, run loop on each vertex, adding value + dist[u][i] to ith node.
Print answer mod (1e9+9). Notice different mod used here. Can result in WA, if problems statement not read carefully.