Author: Roman Furko
Tester: Sergey Kulik
Editorialist: Praveen Reddy Vaka
basic dp, sliding window minimum
This can be modelled as a graph problem where each street a node and edged denoting the streets which can take as given in the problem. For N = 8 and K = 3 the following diagram depicts such a graph.
In the graph the weight of each edge is the weight of the node to which it is directing to. The first street is always takesn so we have to account for w in all our answers. All you need to do is find the minimum cost path from the first node to the last node, where cost of the path is the product of all the weights of the edges on its path.
If the cost was just sum then we can find simply use Dijkstra’s shortest path algorithm to do this. We can convert the product to sum by just using log values of the weights. Since log is a monotonically increasing function we have w1 > w2 iff lof(w1) > log(w2). So in the modified graph using the log values if find the path with minimum cost we can compute the products of actual weight modulo 1000000007 and output it as answer. The value of N can be at maximum of 10^5 so we can only solve subtask1 using this. We will now look at a simple solution which uses the properties of the graph.
Note that in the graph the edges only go forward so there are no chances of having a cycle in this graph. For a given node all the incoming edges have the same cost hence the minimum cost path to reach a node is just the minimum cost path value among all its predecessors (all nodes which have edges to this node) multiplied by the weight of current node.
If we just have an array min of length n. min[i] will store the minimum value to reach node i. The answer will be min[n-1].
We will fill this array by traversing from left to right. Since we start on first street we set min = w.
For an index i we look back K positions before (since these are the only possible predesecorrs) and find the index j which has the minimum value. Now we set min[i] = min[j]*w[i]
The problem with this approach is the values of products can quickly get beyond 64-bit integer range the maximum native integer support provided by most programming languages. If you are using languages like python or Java which have big integer support or have your own implementation of big integer you can directly code this. Refer editorialist’s solution for a Java implementation.
You overcome this by simply using logvalues, min[i] will store the log of the min value and we will store another array ans where ans[i] will store the min value modulo 1000000007.
set min = log(w) and ans = w
For an index i we look back K positions before and find the index j which has the minimum value. Now we set min[i] = min[j]+ log(w[i]) and ans[i] = (ans[j] * w[i]) % 1000000007
But this solution has a time complexity of O(NK) and hence can’t be used to solve subtask2
We can slightly modify the previous algorithm to solve this subtask. At an index i we need to find the minimum value stored in the previous K indices i.e. (i-K, i-1), at index i+1 we need the minimum in range (i-K+1, i), So going forward we we would never need the value at i-K. All we need to do is somehow maintain the minimum value in the sliding window of length K. We provide one way of doing this.
Have a Priority Queue of a Pair, the pair has two parameters logValue and index. We will define the priorityqueue ordering based on logvalue and use index for eviction of pairs from the priority queue.
set ans = w
add <log(w), 0> to the priority queue.
While processing any index i we do the following.
-let j be the index of the top item in the priority queue
-while the value of (i-j) > K delete the top value in the priorityqueue and keep udating j
-set ans[i] = (ans[j] * w[i]) % 1000000007 and add <pq.top().logValue + Math.log(a[i]), i> to the priority queue
This algorithm will always give the sliding minimum we needed and hence the right answer. Because of the deletions this also might look like a O(NK) algorithm. But if you look carefully there are exactly N items added to the priority queue hence at max N items be deleted, so giving an amortized cost of O(1) for the deletions.
You can use other techniques for computing this sliding minimum like using a segment tree since the the window is nothing but a range and we have to find range minimum. But this might be an overkill.
Setter’s Solution: CHRL4.cpp
Tester’s Solution: CHRL4.cpp
Editorialist’s Solution: CHRL4.java