I was thinking of another approach. After we have constructed the graph formed by edges which belong to a shortest path from 1 to n, we can find the bridges of this newly formed graph. And, these bridges will be the answer to given problem.

Can you please check if my method is correct or not ? Thanks

There is a mistake in the last line, it should be best_i + sum(i+1,i+len) — k (it is written correctly in the sample code).

As for the reasoning, Suppose you want to find score of array of length len starting at index, then let rem=len%m. The your score would be sum(i,i+rem-1) -k + max(i+rem).

where max(i+rem) is the maximum score you can obtain if you are starting at index (i+rem) and your sub-array's length is multiple of m (i.e. m, 2m, 3m...)

Now, you can notice that max[i] = sum(i,i+m-1) + max[i+m]. Your base case would be max[n-m]= MAX(0, sum(n-m,n-1)], and max[i]=0 for all i greater than n-m and less than n-1.

After your max array is calculated you can go through all the indices and for each rem = 1,2,3....m, find out the maximum score.

Team : Ctrl Shift Defeat from IIT Kanpur

Members : SanathSalampuria 431jericho Kev2103

Regionals : Qualified for Kanpur and Chennai

Rivals : up and coming team 'segment_trACk' from IIT Kanpur

Preferences in problemset : 1900 and below problems, NO DP

Thanks a lot

Subject: Need Help for G2 In tutorial it is said we will need to do BS over all the values by taking it as our first problem. While solving I thought that if we took min out of all the starting costs it would be enough. In case of equality between 2 such values I took the one with greater cost from back. It is showing WA at test case 828 expected 2 output 1; what is wrong in my reasoning ?