This is my first post on this forum so sorry for advance if I did something wrong.
This is the problem:
Looking at the constraints I was sure it was DP, but I ran into some problems when I actually tried to write a recurrence. The problem needs us to calculate the sum of all minimum scores over all arrays that are possible.
I initially tried to construct a DP state like dp(i,s)= What are the number of such subarrays A[i:n] I can construct which will have a minimum score equal to s. But I couldn’t write a proper recurrence for it, at least not one which was right. I realised that it was hard because we had to somehow track the minimum possible score over all arrays, which I’m not sure how to do. I thought maybe we need two types of recurrences, one which will somehow track the minimum score for each subarray A[i:n] being created, and another one which would count the number of subarrays, but I wasn’t able to come up with anything.
Can anyone help? Also, for some reason codechef is showing a timer of 3 months when you open the site. Idk why though, the contest was held on 31st January and it was for 4 hours only. In other words, the contest is not currently going on!