Which case am i missing?? My wrong solution link: CodeChef: Practical coding for everyone
Any help will be appreciated.
why this problem is in beginner section??
12 Likes
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.
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