The problem is in your code (string ret have length 3 instead of 2) see this submission 5069697

You also output '\0', it's a well-known bug of grey and green coders

O_o No way, it's some sort of precomputation-geometry stuff. Not sure what exactly, it's ugly.

For each circle, compute the sum of its cells. Then we fix one circle (x1, y1) and try to find the maximum possible other one (x2, y2).

Notice that because the radius is fixed, we can easily precompute for every value of x1 — x2 what is the maximum value of k such that we can't place the second circle on the segment from (x2, y1 - k) to (x2, y1 + k). So we only need to loop for every value of x2 and get the maximum of all circle from (x2, r + 1 ... y1 - 1 - k) and (x2, y1 + 1 + k ... n - r). This can also be precomputed.

Total time complexity is O(N^3)

I precalced all circle sums: Calculate sum of first circle in O(R²), calculate sum of other O(N²) circles in time O(R) (use sum of adjacent circle and update border). O(N*N*R)

Then, for each row: For the first cell, create a map (circle sum => count), which counts occurrences of circle sums in the whole field excluding circle sums of colliding circles in O(N²). We can pair the circle at the current position with K other circles with a total of (sum of current circle) + V, where V is the biggest V in the map (V=>K). Update end result accordingly. For the other O(N) cells, update the map in O(R) (and update the end result). For all rows this is: O(N * (N*N*logN + N*R*logN))

This results in O(N*N*N * log(N)).

At first I ran into the time limit. I speed up my solution by skipping circle sums for the map that are obviously irrelevant (smaller than: best sum of two circles (so far) — maximum of a circle sum in the current row).

Actually, choosing k richest boys and k cheapest bikes is just to check if it is possible to rent k bikes. Once it is possible to do so, we simply spend all of the shared budget renting k bikes (min(shared budget, total costs of k bikes)) to minimize the personal amount. It doesn't matter which boys are chosen in this case.

I do not know how to formally prove it but here's my best to explain my thought:

assume we have sorted boys money in A[], sorted bikes price in B[];

assume we have fix k boys a_1, a_2 ... a_k and k bikes b_1, b_2...b_k and a_i boy buys b_i bike

I want to check if any other scheme will make me use less share money (as it can potentially make more boys buy bikes)

Let's pick any a_i,a_j and b_i, b_j where i < j,

try to swap them to see if we can use less share money

i.e. a_i buy b_j and a_j buy b_i

Case 1: if b_i <= a_i, then a_i, a_j >= b_i, it is always better using a_j buy b_j as a_i can afford b_i by himself --> No swapping

Case 2: if b_i > a_i, no matter b_i > a_j or b_i <= a_j, swapping them won't able to make result better --> No swapping

So using this greedy scheme to buy the bikes uses least share money for a fixed k boys and k bikes.

Then, obviously for a fix k after bsearch, we can, again,

greedily choose the richest k boys to buy the cheapest k bikes as they should make us possibly save more share money

Lastly, when we know how many bikes k we can buy, we do not need to know which k boys buy them, as the total minimum answer is always the cheapest k bikes minus all share gold

Even I'm confused with the problem statement. I think the problem setter intended to say "You are allowed to delete any character from the word, including characters at both ends."

In the task it is said that we need to output the minimum amount of personal money spent, not common.

exactly !! like for a test case "abcdefgghhi" output should have been "abcdefggh" with length 9 but according to the tutorial given its "abcdefgghi" with length 10 ! I used recursion for the deleting condition as given in question but its giving TLE for testcase 5.

update your sum, everytime you move out from block.

n_sum = sum;
while(end<n){
        sum=sum-a[st]+a[end];
        st++;
        end++;
        if(sum<n_sum){
            n_sum=sum;
            start=st;
        }
    }