PROBLEM LINKSAuthor: Roman Furko DIFFICULTY:easymedium PREREQUISITES:basic dp, sliding window minimum EXPLANATIONThis 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[0] 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. subtask1: 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[n1]. We will fill this array by traversing from left to right. Since we start on first street we set min[0] = w[0]. 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 64bit 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[0] = log(w[0]) and ans[0] = w[0] 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 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. (iK, i1), at index i+1 we need the minimum in range (iK+1, i), So going forward we we would never need the value at iK. 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[0] = w[0] add <log(w\[0\]), 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 (ij) > 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. SOLUTIONSSetter's Solution: CHRL4.cpp
This question is marked "community wiki".
asked 26 Jan '14, 14:11

Using logarithm technique is completely wrong here.
The correct answer for both tests is (2^{84} − 1) mod (10^{9} + 7) = 946258190. The idea of these tests is two construct two sequences with almost equal products. I found that 2^{84} − 1 has a good factorization, while 2^{84} obviously has it too. Then the task of constructing tests was pretty straightforward. Searching for large numbers of the form a^{n} − 1 with maximum prime factor under 10^{5} leads to the large list, that could be used to construct the big pool of tricky tests. Some examples are: answered 26 Jan '14, 16:31
2
I was thinking when I submitted: "hm, maybe there are some good tests and I'll fail". First submission AC, 100 pts. Luck is a factor, that's for sure :D Then again, Codechef doesn't really try to make strong test cases. Just one acronym: SEAGRP.
(26 Jan '14, 18:59)
Codechef never minds changing the test case at the last moment , no matter how much the contestants get screwed ..Still , it's good to do something than nothing
(25 Oct '15, 23:00)

Can Someone Plz Explain The Solution for Subtask Two in a Bit More Easy Language ?? answered 17 Jan '15, 23:08

My code is giving the correct answer for both the test cases but after submitting it is telling wrong answer. answered 29 Aug '15, 21:26

The logarithm technique is good, this answer on Quora explains why: https://www.quora.com/HowcanIcalculatetheshortestpathifthepathlengthsarenotsummedbutmultiplied The editorial is very good, thanks for writing it. There is one mistake at the end, the amortized cost of deletions from the priority queue is not O(1) but instead O(log K) as there are at most 2K elements in the priority queue. answered 01 Nov '15, 04:18

for subtask2: set ans[i] = (ans[j] * w[i]) % 1000000007 is WRONG. think about the case for k==2, the array is: 1, b, c, d, e ans[0] == 1, ans[2] == b, ans[3] == c, ans[4] == min(b, c) * d assuming min(b,c) = k if k * d % 1000000007 < c but k * d > c, then under subtask2's analysis: ans[5] == c * e, but in subtask1's analysis: ans[5] == k * e answered 07 Nov '15, 13:28

i have done it like this....... include <iostream>using namespace std; int main(int argc, char* argv) { long long int n,k,prod=1,i; int ar[10000]; cin>>n>>k; for(i=0;i<n;i++) cin="">>ar[i]; for(i=n;i>0;i=ik) { prod=i; } cout<<prod; return="" 0;="" }="" but="" the="" oj="" is="" saying="" wrong="" answer<="" p=""> answered 11 Dec '15, 20:41

I tried to solve this problem using backtracing. I think conclusion here can be use dp whenever possible. Using larger array space is better than filling up your recursive stack. And of course you save the repetitive calculation. My wrong solution link : https://www.codechef.com/viewsolution/9182878 One of the good solution I find here is not even a dp. https://www.codechef.com/viewsolution/9163977 I think I should stop looking everything as a decision problem. Some can be solved mathematically as well. Thank for setting this up ! Cheers ! answered 16 Jan '16, 18:37

**A short note on when to delete elements from PQ correctly : valid window indexes are from ik to i  1 for position i. The minimum log value and it's index will come from this range ( ik, i1 ) both inclusive. we use a priority queue to store log values and it's indexes. at any position i, we need our PQ to give the minimum log value's index. This index must be from the valid range as stated above. The so not obvious thing is how to correctly delete elements from PQ so that at any moment , at position i , it contains minimum index only from the range [ik, i1]. let's look at it mathematically. our PQ contains ( logvalue, index) as one "element". let r denote indexes from PQ. ( r can take any value of PQ's second element ). Since our range is [ik, i1]. we want elements from PQ to be deleted for all r such that r < i  k.( all r outside our valid range and below i  k ). This implies r + k < i. or k + r < i. so for all r in PQ's second element, keep deleting from PQ while ( k + r < i ). This is the condition for deleting elements from PQ, used in Editorial but not so explained. answered 21 Jan '16, 18:10

Can anyone please suggest a data structure other than priority queue to solve this question and why would it be better than it.
link
This answer is marked "community wiki".
answered 21 Jan '16, 22:23

Can I get some testcases to check my answer? @furko answered 28 Jan '16, 16:03

The difficulty of this problem is very high for a beginner's practice problem. answered 30 Jan '16, 07:39

want to know if the minimum product value be of streets visited with maximum allowable step size thats K. so number of steps will be i=N/K1. And the product array goes like PA=[N,NK,N2K .......iK] answered 08 Feb '16, 23:34

can somebody tell me why this easy approach is failing in codechef : http://ideone.com/JwC46i answered 01 Jun '16, 17:31

I have been trying this problem for more than 2 weeks now. Getting WA all the time for all the test cases. Have posted in the forums twice. No reply that helped. Some help https://discuss.codechef.com/questions/81935/someonepleasehelpmewiththisquestionstuckwithitforweeksnow answered 04 Jun '16, 15:10

Which case am i missing?? My wrong solution link: https://www.codechef.com/viewsolution/10521857 Any help will be appreciated. answered 08 Jul '16, 11:47

Can someone help me and tell me what's wrong with any of the answers for this solution? I tried with my own random test cases against the solved ones but it shows WA everytime. answered 05 Oct '17, 00:46

i thought you can visit y from x if the difference between their special numbers were <=k ,and found a soln , and got wa on all cases. Now,that i read the question properly its the yx<=k condition _ . Spent more than 2 hours for nothing . answered 25 May '18, 20:11

The problem states that "you can move from the Xth street to the Yth street if and only if 1 <= Y  X <= K" but the Editorialist's Solution (Java code) accepts the follow instance: N=4, K=2, A = {3, 9, 11, 13} and gives the result 351. If I understood the problem well, this instance should not produce results. Is there something I'm misunderstanding? answered 17 Feb, 03:27

answered 09 Mar, 18:11

answered 09 Mar, 18:11

why this problem is in beginner section??