# 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

On June 9, HackerRank Ad Infinitum 18 has started. It is a math-oriented programming contest. There are 7 problems to solve, and I had a pleasure to prepare 2 of them.

If you like math and haven't joined the contest yet now it's time to do it  It's a rare opportunity for math lovers.

It's a rather rare opportunity for math enthusiasts. The next edition is planned in around 3 months from now.

# HackerRank Week of Code 24

HackerRank Week of Code 24 started yesterday. It is a contest lasting a week, with 7 problems to solve. On each day, one of the problems becomes available to solve, and tomorrow, my problem called Simplified Chess Engine opens up. It is a nice problem related to analyzing chess games played on a smaller board with just a few pieces. I hope it will be interesting for all of you.

Moreover, there are T-shirts for top 10 participants, so it pays off to compete for them

# RookieRank contest by HackerRank

I'm pleased to invite you, especially these ones of you who are starting with competitive programming, or like to practice with easy problems, to compete in a brand new contest RookieRank by HackerRank.

There will be 5 problems to solve, starting from very easy ones up to a few just slightly harder. I'm the author of 4 of them.

Moreover, there will be two separated leaderboards. One especially for all first time competitive programmers, i.e. these who are not listed on the Algorithms Leaderboard yet. The point is, that if you are just starting on HackerRank, you will compete with other people with similar experience.

The contest starts in 4 hours and you can register for it here.

Good Luck!

# Regular Expresso 2 Contest

Hi guys,

My contest called Regular Expresso starts in just over 2 hours on HackerRank. The contest is all about regular expression and this is its second edition. It contains 8 problems of various difficulties and it will last 24 hours.

Top 10 participants will be awarded with cool T-shirts

You can register for the contest here:

https://www.hackerrank.com/regular-expresso-2