In the problem Chef and Way ( CHRL4 Problem - CodeChef ) , My code is getting WA. I m not able to understand where is it going wrong. I have used the general DP approach with recursion to find answer. Here is my code solution ( CodeChef: Practical coding for everyone ) .
Please guide me what to be improved .
Mod is involved in this problem so u can’t compare two values directly.The approach in the editorial is really good, u can’t store product of values ,but we can store log of it and us it for comparison of different options.
we know
log(a * b * c * d) = log( a ) + log( b ) + log( c ) + log( d )
So we can make a priority queue of pairs and store the log value as the first entry and its index as the second entry.
So using priority queue we can get the optimal position from [i-k , i-1] to reach ith index . Each time pop until the top value of queue is less than i-k and hence we can notice, each value is inserted and poped only once, so Time complexity is O(N) and to get the answer
we can make another array side by side and when we get the best position from prev k steps , we can update its value in the array.
For Reference u can have a look at my code : CodeChef: Practical coding for everyone
@yatin_yk08 can you please take a look at my doubt
link to my question forum: Please find the mistake in my code