Screen Shot 2018-02-12 at 11.17.44 AM

Cut a Strip Editorial - my hard problem in HackerRank Week of Code 36

Hello,

Recently HackerRank Week of Code 36 took place and two my problems were there:

Ways to give a check

Cut a Strip

I hope you had a fun time solving them!

Several people messaged and asked to share my approach to Cut a Strip problem (for some reason HackerRank hasn't published my editorial yet). So I decided to describe my approach here:

If you're not familiar with the problem yet, please read the statement here: Cut a Strip

Editorial

First of all, let's make some observations, which make the task easier to implement:

The first observation is that we can reduce the original problem, to the problem where we are allowed to cut only horizontal strips, i.e. ones with size 1 \times x. This reduction is possible because if we have a solution only for horizontal strips, the vertical strips can be handled by rotating the input grid 90 degrees either way and solving the problem for horizontal stripes on this rotated grid. Notice that any vertical strip in the original grid is then transformed to a horizontal strip in the rotated grid.

Next observation is that we can consider any pair of columns x \leq y and reduce the problem to 1-dimensional problem. How to do that? For now, let's assume that we can't cut any strips and just want to find the maximum sum of a sub-grid. In order to do that, we can iterate over all pairs of columns x \leq y and for each such pair define an array b[1 \ldots n] such that b[i] := \sum\limits_{j=x}^y A_{i,j} and then use Kadane algorithm to find the maximum sum of a subarray of b. Since we considered all pairs of columns, then we're finding indeed the maximum sum of any sub-grid of A.

If we can only adjust the above technique to handle cutting a horizontal strip, we have a solution.

Now comes the crucial observation leading to an elegant solution. Notice that cutting the best horizontal strip of size 1 \times x for x \leq k corresponds to choosing exactly one of elements of the array b defined above and subtracting from it a sum of the strip we want to cut. Notice that for fixed columns x \leq y and value of b[i] such a strip is a non-empty subarray of array [A_{i,x}, A_{i, x+1}, \ldots, A_{i,y}] of size at most k. Furthermore, the best of such strips that can be cut has the minimum sum amongst all possible ones. Thus what we really want to do is to select one of the elements of the array b, let's say b[i], and subtract from it the minimum sum of subarray which b[i] covers.

All these values can be computed using dynamic programming techniques. For an exact implementation of this method please refer to my commented submission attached below.

Total time complexity is therefore O(n^2 \cdot (n+m) + m^2 \cdot (n+m)) since we are solving the problem twice (for original grid and the rotated grid).

 

For implementation details, you can see my commented code using the exact method described above.

Cheers,

Pawel

  • https://plus.google.com/+IvanAvdonin Ivan Avdonin

    My solution at Hackerrank got accepted but I found the test which break it

    3 3 3
    1 0 1
    -2 -1 -2
    1 1 1

    My solution gives answer 3, but the right answer is 5

    • http://chasethered.com pkacprzak

      Interesting, maybe there were no test case where the best is to remove the max length strip or/and when the strip spans across the whole column/row. Do you think this is the case your solution misses?