×

# CHRL4 - Editorial

Author: Roman Furko
Tester: Sergey Kulik
Editorialist: Praveen Reddy Vaka

easy-medium

# PREREQUISITES:

basic dp, sliding window minimum

# EXPLANATION

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[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[n-1].

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 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[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. (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[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 (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.

# SOLUTIONS

Setter's Solution: CHRL4.cpp
Tester's Solution: CHRL4.cpp
Editorialist's Solution: CHRL4.java

This question is marked "community wiki".

2★vaka ♦♦
253131822
accept rate: 16%

2★skbly7
1.9k91724

why this problem is in beginner section??

(16 Nov '17, 23:37)

 18 Using logarithm technique is completely wrong here. There are tests where it is impossible to distinguish two candidates for the answer. I'm sure that almost all contestants solutions will fail on one of these tests: 15 2 1 4096 16513 4096 18705 4096 14351 4096 18577 4096 16257 4096 14449 4096 1 15 2 1 1365 16384 2359 16384 1247 16384 14351 16384 4287 16384 5419 16384 14449 1  The correct answer for both tests is (284 − 1) mod (109 + 7) = 946258190. But, for example, my solution gives 946258190 for one test and 946258191 for another in MSVS compiler and 946258191 for both tests on ideone. The idea of these tests is two construct two sequences with almost equal products. I found that 284 − 1 has a good factorization, while 284 obviously has it too. Then the task of constructing tests was pretty straightforward. Searching for large numbers of the form an − 1 with maximum prime factor under 105 leads to the large list, that could be used to construct the big pool of tricky tests. Some examples are: 1523012 − 1 ≈ 1.6e50 with max prime 80209 1427112 − 1 ≈ 7.1e49 with max prime 59221 1008512 − 1 ≈ 1.1e48 with max prime 81439   973012 − 1 ≈ 7.2e47 with max prime 79357   863812 − 1 ≈ 1.7e47 with max prime 78649 ... (many other large numbers of the form a12 − 1 - this form is particularly good) 16116 − 1 ≈ 2.0e35 with max prime 54881 18716 − 1 ≈ 2.2e36 with max prime 93761   9518 − 1 ≈ 4.0e35 with max prime 86311 21418 − 1 ≈ 8.9e41 with max prime 41221   4220 − 1 ≈ 2.9e32 with max prime 83621   1724 − 1 ≈ 3.4e29 with max prime 83233   1230 − 1 ≈ 2.8e32 with max prime 35671     636 − 1 ≈ 1.0e28 with max prime 55117 There are also a lot of examples of 8th and 10th powers but they are smaller. answered 26 Jan '14, 16:31 6.7k●62●119●138 accept rate: 12% 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) xellos07★ 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)
 5 why this problem is in beginner section?? answered 19 Aug '16, 14:51 61●1●1 accept rate: 0%
 2 For those getting SIGSEGV , here is a test case file whose ans should be 100. link text answered 03 Sep '15, 10:30 355●8●19 accept rate: 20%
 0 Can Someone Plz Explain The Solution for Subtask Two in a Bit More Easy Language ?? answered 17 Jan '15, 23:08 80●2●7 accept rate: 4%
 0 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 1 accept rate: 0%
 0 The logarithm technique is good, this answer on Quora explains why: https://www.quora.com/How-can-I-calculate-the-shortest-path-if-the-path-lengths-are-not-summed-but-multiplied 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 1●1 accept rate: 0%
 0 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 3★xpan 1 accept rate: 0%
 0 Correct.....!!!!!! answered 08 Nov '15, 18:17 11 accept rate: 0%

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=i-k) { prod=i; } cout<<prod; return="" 0;="" }="" but="" the="" oj="" is="" saying="" wrong="" answer<="" p="">

2★akay97
1
accept rate: 0%

 0 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 1 accept rate: 0%
 0 **A short note on when to delete elements from PQ correctly : valid window indexes are from i-k to i - 1 for position i. The minimum log value and it's index will come from this range ( i-k, i-1 ) 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 [i-k, i-1]. 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 [i-k, i-1]. 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 1 accept rate: 0%
 0 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 48●1●5 accept rate: 10%
 0 Can I get some testcases to check my answer? @furko answered 28 Jan '16, 16:03 -3●1●2 accept rate: 0%
 0 The difficulty of this problem is very high for a beginner's practice problem. answered 30 Jan '16, 07:39 58●2●3●7 accept rate: 0%
 0 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/K-1. And the product array goes like PA=[N,N-K,N-2K .......iK] answered 08 Feb '16, 23:34 0★minchx 1 accept rate: 0%
 0 can somebody tell me why this easy approach is failing in codechef : http://ideone.com/JwC46i answered 01 Jun '16, 17:31 2★pjrocks 1 accept rate: 0%
 0 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/someone-please-help-me-with-this-question-stuck-with-it-for-weeks-now answered 04 Jun '16, 15:10 0★gonecase 187●1●12 accept rate: 0%
 0 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 5★rathi_22 11●2 accept rate: 0%
 0 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. https://www.codechef.com/viewsolution/15602465 answered 05 Oct '17, 00:46 1 accept rate: 0%
 0 why this problem is in beginner section?? answered 16 Nov '17, 23:39 1 accept rate: 0%
 0 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 y-x<=k condition -_- . Spent more than 2 hours for nothing . answered 25 May '18, 20:11 21●2 accept rate: 0%
 0 The problem states that "you can move from the X-th street to the Y-th 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 1 accept rate: 0%
 0 /* Shotest path in DAG problem, with order O(E) solution. */ /* Weights are in product, but log() linearizes it. */ /* MinCost(i, j) = MinCost(i, k) + MinCost(k + 1, j); k <= K upto j. /* Edges are in the order of N * K since, the number of edges from a given Node say 'a' is atmost K. N nodes, K per node. */  answered 09 Mar, 18:11 0★sum_8636 1 accept rate: 0%
 0 /* Shortest path in DAG problem, with order O(E) solution. */ /* Weights are in product, but log() linearizes it. */ /* MinCost(i, j) = MinCost(i, k) + MinCost(k + 1, j); k <= K upto j. /* Edges are in the order of N * K since, the number of edges from a given Node say 'a' is atmost K. N nodes, K per node. */  answered 09 Mar, 18:11 0★sum_8636 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×2,214
×1,723
×16
×16

question asked: 26 Jan '14, 14:11

question was seen: 25,022 times

last updated: 09 Mar, 18:11