Someone Explain the logic of this problem

https://www.codechef.com/problems/MGOLD

I’m assuming that you want an explanation of the solution rather than an explanation of the problem itself?

Notice that k<=7, which means that each element of our subarray modulo k can have a maximum possible value of 7. Hence we can solve the following problem instead:

What’s the maximum length of a subarray such that the elements of the subarray modulo k equal to i, where 0<=i<k(We solve this individually for all values of i)?

If we were to replace all values of our array with its values modulo k, we can see that the minimum cost to change it to some i would be (its value - i) if the value is >=i. Otherwise the cost is (the value + (k-i)). Let this be stored in cost[x] for all values of 1<=x<=n.

Hence if we set our leftbound of our array, we can keep adding elements until the cost is no longer less than m. Hence we know our rightbound. However this would be O(n^2). But notice that for the leftbound to shift from l to l+1, we can assign another cost[l] to pick up more elements to the right of whatever our earlier rightbound was. Hence using a sliding window, we can solve the problem in O(n).

3 Likes

thanks👍

My solution is giving WA :disappointed_relieved:. Can u pls tell the mistake
https://www.codechef.com/viewsolution/36054363

help pls?