CHRL4 - Editorial

editorial
, , , ,
1

PROBLEM LINKS

Contest

Practice

Author: Roman Furko

Tester: Sergey Kulik

Editorialist: Praveen Reddy Vaka

DIFFICULTY:

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.

chrl4-graph.png1115×208

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

3 Likes
2

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.

16 Likes
3

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 :smiley:

Then again, Codechef doesn’t really try to make strong test cases. Just one acronym: SEAGRP.

1 Like
4

Can Someone Plz Explain The Solution for Subtask Two in a Bit More Easy Language ??

5

My code is giving the correct answer for both the test cases but after submitting it is telling wrong answer.

6

For those getting SIGSEGV , here is a test case file whose ans should be 100.
link text

1 Like
7

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

8

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.

9

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

10

Correct…!!!

11

i have done it like this…

include

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

12

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 !

13

**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.

14

Can anyone please suggest a data structure other than priority queue to solve this question and why would it be better than it.

15

Can I get some testcases to check my answer? @furko

16

The difficulty of this problem is very high for a beginner’s practice problem.

17

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]

18

can somebody tell me why this easy approach is failing in codechef :

19

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

20

Which case am i missing?? My wrong solution link: https://www.codechef.com/viewsolution/10521857
Any help will be appreciated.