Please Help me at CHRL4

help
, ,
1

I am trying to solve problem CHRL4 in beginner section.
This is my solution:

 #include<iostream>
    using namespace std;
    int main()
    {
        long int n,k,t=1;
        cin>>n>>k;
        if(n>=1 && n<=100000 && k>=1 && k<=n){
        long int sp[n];
        for(int i=0;i<n;i++)
            cin>>sp[i];
        for(int i=n-1;i>0;i-=k)
        {
            t*=sp[i];
        }
        cout<<t;
    }}

I am getting Wrong Answer when i try to submit. Any suggestions??

2

Its not exactly a beginner level problem, I dont know why its put in that section. The editorial states that its a easy-medium problem, I suggest give it another try after you learn some concepts in graph theory.

1 Like
3

for this test case you code will print 12 but answer should be 8.

4 2

1 3 2 4

and it’s because question is saying that 1 <= Y - X <= K. but you are choosing k in kind of every case… Which will not give optimal result all time at all. you can think of dp solution for this.

Just for hint, I will say try to think in this direction… lets say you know minimal multiplication(how answer is defined in question) for every element of array, then if I add new element in array then can you find answer for new element. Till now you can easily solve First subtask by just using couple of arrays and for loops.

For subtask 2… You will see that Complexity is increasing because of for loops over k, which are doing redundant calculations again and again. To optimise that part… I will ask, can you do some pre-calculation of O(n) and answer queries like, find minimum element in a range of array in O(1) or O(log(n))? If yes, then you will see that second subtask is also solved. :slight_smile:

I tried to mention how you could approach this problem and how problems should be approached(main purpose of subtasks in problems). I did not mention exact algorithm because that is already there in editorial. But you can ask questions if something thing is not clear… :slight_smile: