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

Codechef June Lunchtime 2017

On Saturday, Codechef June Lunchtime 2017 took place. I wrote the editorials for the contest and have to tell you that at least 2 problems were quite interesting, and one of them exceptionally hard! If you take a look at the final standings, you'll see that only 3 people solved all problems during the contest, and we had very strong participants as usual. My bet was that nobody will solve it, but fortunately, I was wrong

If you didn't participate and want to practice problem-solving skills, I recommend trying COMPCLUB problem, or if you want something really hard, then try SHDWCMP.

My editorials are available here.

My participation in Codechef June 17 Long Contest

Hi,

Codechef June 17 has just finished. After a few months of my inactivity in Codechef Long contests, caused by helping in preparing these contests, I took part in this one.

It turned out to be a fun contest with decent problems. I especially liked CLONEME problem and also ES - I'm not math expert by any means, so I got to put some unusual effort to solve it Challenge problem SABOTEUR was also nice, but I regret I didn't put enough effort there. I also regret not tackling the OAK problem.

I finished 34th, which is my second best result there I think, and this resulted in jumping to the top rank in Poland in the overall ranking. I'll try next month to beat that result.

If you have any questions regarding the problems from the contest or my approaches to them, I'd be happy to answer them.

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.

SnackDown Online Pre-elimination round A

SnackDown 2017, Codechef's most important contest of the year takes place right now.

Over 12 000 teams advanced from the qualifier round to pre-eliminations rounds. Today first pre-elimination round A started and it'll end in around 14 hours.

There are 6 problems to solve in this round, and at least 5 are interesting. Top 1000 teams from this round will advance to the last Elimination Round, from which around 50 top teams will move to the onsite finals!

This time I'm not involved in contest preparation, but I'm participating in the contest Since this is a team contest I paired with my friend Tong Wei. However, when the contest started he was sleeping, so I took care of all these problems We have all problems solved, so we are tied for 1st place, so for sure we'll advance to the next round.

If you need any clues for approaching the problems (after the contest) just let me know.

See you in the next round!