# 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

# Unofficial Editorial: Big Queries from Codechef October Long 2016

Codechef October Long has just finished and I wanted to share my unusual approach to one of the problems from the contest. It barely fits the time limit even after optimizations, so I expect that this is not the model solution (I expect some kind of segment tree to be the intended solution). However, knowing the technique I used can be really helpful when trying to solve similar problems with queries.

Contest: https://www.codechef.com/OCT16/problems/BGQRS/
Practice: https://www.codechef.com/problems/BGQRS/

Problem:

For a given array $A$ of $N$ integers, the task is to perform $Q$ queries, each of one of the following types:

- $\texttt{mul}(L, R, X) :=$ multiply elements of $A$ with indices in range $[L, R]$ by $X$

- $\texttt{assign}(L, R, Y) :=$ assign new values to elements of $A$ in range $[L, R]$ in such a way that $A_L = Y, A_{L+1} = 2 \cdot Y, A_{L+2} = 3 \cdot Y, \ldots$

- $\texttt{query}(L, R) :=$ returns the number of trailing zeros in the product of elements of $A$ with indices in range $[L, R]$

As the final answer we need to return the sum of results of all query operations.

Here, I’m going to provide a solution which is possibly slower than the one intended by the author. When I implemented it without much care at the first time, it just passed only one of test cases in the last subtask. I wanted to know if there is a change that it will pass all of them, so I submitted it handling only $10%$ of queries and it barely passed in time something like $0.95/1s$ in the worst case. So I knew that I need to optimize it at least around $10$ times. I started throwing out dynamically allocated memory and exchanged it with static arrays and improved all others bottlenecks. Finally, the solution works in around $0.89$ in the worst case, so it barely fits time limit. I think that authors didn’t want such a solutions to pass, and this was probably the reason that output in the problem is reduced just to one number in order to avoid some fast I/O tricks.

Solution

First observation that we should make is that the number of trailing zeros in a product of some integers is equal to the highest power of $10$ which divides this product. Let’s say that the product is equal $P$, moreover, let $e_2$ be the highest integer such that $P$ is divisible by $2^{e_2}$. Similarly, let $e_5$ be the highest integer such that $P$ is divisible by $5^{e_5}$. Then the highest power of $10$ that divides $P$ is equal to $\min(e_2, e_5)$. Thus, in order to answer $query(L, R)$, we just need to know how many times, in total, numbers from range $[L, R]$ in $A$ are divisible by $2$ and how many times, in total, they are divisible by $5$. We will show how to maintain that information across all the updates and how to exactly answer the queries.

The method I’m going to explain is a nice trick to have in mind while approaching this kind of problems. Personally, I call the method “sqrt-blocks”, but maybe a better name can be suggested. The general idea is to initially divide the input array into $M$ blocks, each of size $K$ in such a way that the first blocks stores information about $A_1, A_2, \ldots A_K$, the second one about $A_{K+1}, A_{K+2}, \ldots, A_{2 \cdot K}$ and so on. What information do we need to store in these blocks? Well, we should store some indices denoting the starting and ending positions of the block, its length, and most importantly, the total number of times that $2$ divides elements of $A$ corresponding to the block and the total number of times that $5$ divides elements of A corresponding to the block. If we can maintain these information across all queries in all blocks, we will be able to handle all of them.

In my implementation I used one more invariant: before each update and query operation on range $[L, R]$ there is a block starting with $A_L$ and there is a block ending in $A_R$.

This invariant makes the code more clear, because any update or query will operate only on full blocks. In order to fulfill the condition from the invariant, we can split blocks just before update/query operation if needed - notice that at most $2$ blocks need to be split.

Now, how do we handle each operation? Well let’s take a look:

- $\texttt{mul}(L, R, X)$ - We want to multiply all elements in range $[L,R]$ by $X$. First, we want to compute the number of times that $2$ divides $X$ and the number of times that $5$ divides $X$. Having these values, we will update information stored in all blocks falling into range $[L, R]$

- $\texttt{assign}(L, R, Y)$ - This operation is the most tricky one. Notice that it corresponds to first assigning values $1, 2, \ldots$ to $A_L, A_{L+1}, \ldots A_R$ and then multiplying each element in $[L, R]$ by $Y$. This last multiplication is the same as $\texttt{mul}(L, R, Y)$ and we already know how to do it, so let’s take a look how to assign values $1, 2, \ldots$ to corresponding elements. The method we are going to use is to assign to each block its starting and ending elements of this sequence and these indices can be easily computed while iterating over the blocks from left to right. Then, based on this values, we have to update the information stored in a single block. Notice than we need to overwrite almost all of them because all values have changed in $[L, R]$. We want to compute the total number of times that $2$ and $5$ divides elements covered by a single block and we can do it quickly if before handling any queries we precompute prefix sums of these values for all $i = 1,\cdots,N$. Then we can use indices stored in blocks denoting first and last elements of the sequence written in the block and these prefix sums to compute the total number of times that $2$ and $5$ divides elements covered by the block

- $\texttt{query}(L, R)$ - This operation is the easiest one. The only think we have to do is to count the total number of times that $2$ and $5$ divides elements in $[L, R]$ and this corresponds to summing up information stored in all blocks falling into $[L, R]$. Finally, we return minimum of these two values, because it is equal to the number of trailing zeros in the product of elements in $[L, R]$ as we noticed at the beginning

So far so good, but what are the advantages of the blocks? Well, if there are always less than $c \cdot M$ blocks, each of size at most $K$, then each single update or query operation will take $O(M + K)$ time, because there will be at most $O(M)$ blocks to iterate over, and splitting them costs $O(K)$, because we split at most $2$ blocks before each update/query and each one has size at most $K$. However, the number of blocks grows when we split them, but on the other hand we want to keep $c \cdot M$ small enough so the complexity is not too high. How to handle it? This is the crucial step: as soon as the number of blocks exceeded $c \cdot M$, we rebuild the whole array $A$ and construct completely new $M$ blocks as we did in the beginning of the computation. This reconstruction is possible using the information stored in the blocks and one such reconstruction takes $O(N)$ time, because we want to compute the exact value of each element in the array and construct new blocks from the scratch. For more details please refer to implementation section below.

Now it’s time to wisely choose values for $M$, $K$ and $c$ in such a way that the total complexity is minimized. The intuition is that when $M$ is big, then a single update or query may take longer, but we will need less rebuilding. It turns out, that choosing $M$ closely to $\sqrt N$ and $c = 2$ works very well. Notice that if $M = \sqrt N$ then $K = \sqrt N$ as well (of course we want them to be integers so actually they might be slightly different). Using these values of the parameters, we have the total time complexity of $O(Q \cdot \sqrt N + \big(Q \big/ \sqrt(N)\big) \cdot N)$. The second value, $\big(Q \big/ \sqrt(N)\big) \cdot N$, denotes the total time needed for all rebuilding - each rebuild takes $O(N)$ and there will be at most $O(Q \big/ \sqrt(N))$ of them, because $O(M) = O(\sqrt N)$ queries have to be performed in order to get the number of blocks greater than $c \cdot M$.

Implementation details

In my implementation I don’t store exact elements of array $A$. Instead, for each element $A_i$, I store two information: the number of times $2$ divides $A_i$ and the number of times $5$ divides $A_i$. This is the only information we need and it makes the implementation more clear. For all the details please refer to my submission below, especially to see how rebuilding is done and what information exactly I store in blocks to make the code clear enough:

You can see my solution here: https://www.codechef.com/viewsolution/11864811

Bonus

In the past, I used the same technique to solve the hardest problem from HackerRank Weekly Challenges 7:

I hope you enjoyed the description and the method itself.

# CodeChef September Lunchtime

A good news for all of us interested in practicing problem solving. September Lunchtime 2016 is coming. It takes place on Saturday 16:00 CEST and will last 3 hours and 30 minutes (check other timezone).

Problem set is prepared by and tested by Sergey Kulik. The contest has four brain-teasing problems which will make your weekend thrilling. My task is to write detailed editorials for all of you.

Joining us on the problem setting panel are: Mandarin Translator: Hu Zecong, Vietnamese Translator: VNOI Team, Contest Admin: Praveen Dhinwa

Moreover, Top 10 school students each from Global and Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here: https://www.codechef.com/laddu.  (For those who have not yet got their previous winning, please send an email to winners@codechef.com).

Good Luck and see you on Leaderboard!

# CodeChef August Lunchtime

Hi,

CodeChef August Lunchtime starts in an hour. I'm the author of all editorials to the problem set and I can assure you that all the problems are interesting to solve. There is one cakewalk problem and 3 harder ones of various difficulties, so anyone should be pleased, especially those ones interested in graph theory

All the editorials will be available after the contest here: https://discuss.codechef.com/tags/ltime39