Editorial for Cafe 12

Prerequisites: Greedy/ Dynamic Programming

Explanation: First, lets have an easy observation that it is always optimal to arrange the couples first. As there are too many queries so we will precalculate the maximum number of places for couples. That can be calculated greedily or using dynamic programming.

Greedy Technique: At first, think we have 2×22\times 2 matrix. We will try to fill columns and rows with couples respectively. This is always optimal to take column first, why? Let the current status of the matrix is -

0001\begin{matrix}0 & 0\\ 0 & 1\end{matrix}

If we fill up the 1st row with a couple then if there were another column like 01\begin{matrix}0\\ 1\end{matrix} this, then we won’t able to fill it up with another couple here. But if we take column first instead of row then we will fill 1st column with couple and there will be still remain a chance to fill the 1st row with a couple. Finally, the 2×32\times 3 matrix that we are considering can be filled with maximum 22 couples.

000011\begin{matrix}0 & 0 & 0\\ 0 & 1 & 1\end{matrix}

Before placing couples.

111111\begin{matrix}1 & 1 & 1\\ 1 & 1 & 1\end{matrix}

After placing 22 couples.

So, we will iterate through left to right (also can iterate through right to left) and fill all 2×22\times 2 matrix with couples optimally and we will get maximum number of couples that can be placed.

Dynamic Programming: DP will have two states indicating current column and the value assigned in previous column. Thus we can calculate maximum places for couples.

Time Complexity: For precalculation, O(N)O(N) and answering queries in O(1)O(1).

Solution:

  1. Setter’s solution (greedy)

  2. Alter’s solution (dp)

    Statistics


    51% Solution Ratio

    ashraf_pavelEarliest, 3M ago

    JobaidulFastest, 0.1s

    tareq_sakibLightest, 5.9 MB

    Zobayer_AbedinShortest, 788B

    Toph uses cookies. By continuing you agree to our Cookie Policy.