# 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

# HackerEarth February Clash

Hi,

After a few months, my problems are again in a HackerEarth contest. This time it is Clash, which is targeted to experienced programmers.

The contest starts just under 6 hours from now and will last for 24 hours. You can register for it here: https://www.hackerearth.com/challenge/competitive/february-clash-17/

I created two problems for the contest and both are related to graphs. One is a problem with trees and windmills while the other one is approximation problem used as a tiebreaker in such contests.

I hope all of you will enjoy the contest and my problems especially

# December Lunchtime - my first Codechef contest

I'm happy to announce upcoming Codechef December Lunchtime as the setter of all the problems in the contest. This is my first contest on Codechef and for sure not the last one

The contest starts on Saturday December 31 and have 4 problems to solve, 2 easier and 2 harder ones. Some graph theory might be useful while trying to solve them If you want to finish the year strong, this is a nice possibility.

After the contest my editorials will be posted on discuss.codechef.com as always.

Happy coding and good luck!

# My approximation problem in HackerEarth November Circuits

HackerEarth monthly long contest starts tomorrow and one of the problems there is my approximate challenge The goal will be to find the best walk in a matrix within some constraints. It will be available just from the beginning of the contest so stay tuned.

There are some prices for top finishers, like cash and t-shirts.

You can register for the contest here: https://www.hackerearth.com/november-circuits/