I participated in Codechef starters (which ended just now). I tried this one Contest Page | CodeChef (Chef’s Homework dilemma) and tried a dp approach, with priority queue, however I’m getting runtime error in last testcase (rest of all got AC). I kept debugging for ~1.5-2 hrs but uable to find error Can someone please help me regarding this? Ubuntu Pastebin (Link to my code, its pretty short). The logic is simple-> dp[i] means the minimum time the chef spends doing homework (from ith day to n-1th day, days are zero indexed), if he does NOT skips the homework on ith day. Then dp[i] = arr[i] + min(dp[i+1],dp[i+2],dp[i+3]…dp[i+k+1]). The dp can be optimized by using priority queue (min) (in which the elements are {dp[],day index}) , I’m simply removing the topmost elem in queue if its index - curr index -1>k, otherwise if index - currindex - 1<=k then, dp[i] = arr[i] + q.top().first , and then I push {dp[i],i} to the queue.

2 Likes

I was also getting the same error. Declare the dp array as global and try once again. It worked for me so you can give it a try.

2 Likes

It worked but how is this possible? Really is their compiler broken?

1 Like

1 Like

Thanks ! Very helpful indeed!