# Cafe 12

CUET Intra University Jun...

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\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 $-$

$\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 $\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\times 3$ matrix that we are considering can be filled with maximum $2$ couples.

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

Before placing couples.

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

After placing $2$ couples.

So, we will iterate through left to right (also can iterate through right to left) and fill all $2\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)$ and answering queries in $O(1)$.

Solution:

### Statistics

52% Solution Ratio
ashraf_pavelEarliest, Jun '21
ASH1901041MFastest, 0.1s
tareq_sakibLightest, 5.9 MB
Zobayer_AbedinShortest, 788B