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!
This is not a beginner level question in anyway. Do you expect a beginner to use a priority queue or segment tree in any way? Also DP can’t be a beginner level concept, however easy to implement it is, it’s still tough for beginners.
can you explain why log is used ?? any resources that can explain product is converted to sum in the given probelm not able to get it??my approach is exactly same as yours only difference is I multiplied and u used LOG??
I did it quite similar to you and am getting AC in just Task number 6. Were you able to solve it further?
Please let me know what is the issue with the below solution
/* package codechef; // don’t place package name! */
import java.util.;
import java.lang.;
import java.io.*;
/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
/* BufferedReader in= new BufferedReader(new InputStreamReader(System.in));
int n=Integer.parseInt(in.readLine());
int k=Integer.parseInt(in.readLine()); */
Scanner in =new Scanner(System.in);
int n = in.nextInt();
int k = in.nextInt();
int mod=1000000007;
int []a1 =new int[n];
int []a2=new int[k];
for(int i=0;i<n;i++)
{
a1[i]=in.nextInt(); //1 2 3 4
}
for(int i=0;i<k;i++)
{
a2[i]=1;
//1 2 3 4
int x=i;
if(x!=0)
{
a2[x]=a1[0];
}
for(int j=i;j<n-1;j+=k)
{
a2[i]=(a1[j]*a2[i])%mod;
}
a2[i]=(a1[n-1]*a2[i])%mod;
}
int min=a2[0];
for(int j=1;j<k;j++)
{
if(a2[j]<min)
min=a2[j];
}
System.out.println(min);
}
}
Notice the following line in the question:
you can move from the X-th street to the Y-th street if and only if 1 <= Y - X <= K, where K is the integer value that is given to you.
This means X + 1 <= Y and Y <= X + K . This doesn’t hold true for the input selected by you. (In your input you also need to fix the value of K . That is a minor issue but worth mentioning anyways.)
yed