why this problem is in beginner section??
1 Like
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 .
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?
/* 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. */
/* 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. */
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 
Then again, Codechef doesn’t really try to make strong test cases. Just one acronym: SEAGRP.
4 Likes
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
why this problem is in beginner section??
6 Likes
Solved it using segment trees to find min in range(i-1,i-k).
My solution: CodeChef: Practical coding for everyone
Hope that it would be helpful.
Solution of Editorialist is incorrect for example take number
7 3
1 2 5 7 9 10 13
The correct solution should be 1x2x5x7x9x13
but the java solution is displaying 91 which is incorrect.
Is anyone have any idea…?
It does not even say that for every street Y>X.
Assume you have this case
7 3
1 3 5 7 4 2 13
I think this can be improved and moved to Intermediate level because this goes way over my head (whoosh).
If a test case is provided like:
5 4
1 5 6 7 8
8
Then what should be the answer and WHY ?
Hello! I am pretty new to programming , I only know python( my extent of knowledge is very low). I tried this program and cam upwith this code:-
n,k=input().split()
n,k=int(n),int(k)
totalstreet=[]
diffstreet=[]
usedstreet=[n]
product=1
a=list(map(int,input().split()))
for i in range(0,len(a)):
if 0<a[i]<=n:
totalstreet.append(a[i])
while n!=min(totalstreet):
for j in range(0,len(totalstreet)):
diff=n-totalstreet[j]
if 1<=diff<=k:
diffstreet.append(diff)
if len(diffstreet)==0:
break
if 1<=max(diffstreet)<=k:
usedstreet.append(n-max(diffstreet))
n=n-max(diffstreet)
del diffstreet[0:len(diffstreet)]
for h in range(0,len(usedstreet)):
product=product*usedstreet[h]
print(product%1000000007)
I tried it with multiple test cases and it worked in python. But when I submit, it says nzec re and rejects the program. Any reasons why? Please help. The indents are properly given. See screenshot below.
The post is terribly formatted. Very hard to read.
I don’t really know much about algorithms at present. After hours of thinking, what I did was:
- Traverse from right to left.
- Maintain an array minimums[] of the same length as the input array.
- For each element, look at the next k elements of minimums. The element in minimums corresponding to the current element is set to the current element multiplied by the smallest value from those k elements.
- Once the traversal is done, minimums[0] would be the answer.
Drawback: You can only do the mod 10^9 + 7 at the end otherwise the “smallest value from those k elements” will give a wrong answer. I used Python for my solution.
It’s an O(kn) algorithm if my calculations are right. One test case from subtask 2 exceeded time. My solution link: CodeChef: Practical coding for everyone
1 Like
I solved this problem in python with an O(n) algorithm. I used monotonic increasing queue instead of priority queue.
https://www.codechef.com/viewsolution/30404866
Can Anyone please explain me , The example given in the problem, I am not able to understand how we got the answer 8.
Example
Input: 4 2
1 2 3 4.
Output: 8
Can someone tell me the problem with my code… its giving AC for just one testcase…
#include
#define mod 1000000007
using namespace std;
int main(){
int n, k;
cin>>n>>k;
int a[n];
for(int i=0;i<n;i++) cin>>a[i];
long long dp[n];
for(int i=1;i<n;i++) dp[i]=mod+1;
dp[0]=a[0];
for(int i=1;i<n;i++){
int j=i-1;
long long minVal=mod+1;
while(i-j<=k && j>=0){
minVal = min(minVal,dp[j]);
j--;
}
dp[i]=(a[i]*minVal)%mod;
}
cout<<dp[n-1];
return 0;
}
1 Like
since k=2, chef can skip one lane at max, so he goes like 1->2->4, giving the product as 8.
I thought I was the only one who felt that way… I am a beginner and was completely demotivated when I saw the answer to this question. This is in no way a beginner level question!