🔗 Problem #1006

Chorage is a special agent who has been given the mission of raiding Korea's secret national defense base (Ontagon). The Ontagon building is donut-shaped, and to determine efficient strike points, Chorage divided the area into two circular zones as shown below. (The numbers in the diagram indicate each zone's number.)

Chorage plans to deploy multiple special squads, each consisting of $W$ members, to infiltrate every zone, and Chorage knows exactly how many enemy soldiers are stationed in each zone. The special squads can infiltrate under the following conditions.

1. Besides the zone it infiltrates, a special squad can additionally infiltrate one adjacent zone. (Zones are considered adjacent if they share the same border. In the diagram above, zone 1 is adjacent to zones 2, 8, and 9.) That is, a single special squad can cover one or two zones.
2. Since special squads cannot distinguish friend from foe, each zone must be covered by only one squad.
3. The sum of enemies in the zones covered by one special squad must be less than or equal to the squad's member count $W$.

Chorage wants to know the minimum number of special squads that must be deployed to cover every zone of the Ontagon.

The first line contains the number of test cases $T$. Each test case is structured as follows.

The first line gives (number of zones)/2, value $N$, and the number of special squad members $W$. ($1 ≤ N ≤ 10000$, $1 ≤ W ≤ 10000$).

The second line gives the number of enemies stationed in zones $1$ through $N$, and the third line gives the number of enemies stationed in zones $N + 1$ through $2N$, separated by spaces. (1 ≤ maximum number of enemies stationed in a zone ≤ 10000) However, there is no zone where more enemies are stationed than the number of special squad members. (Therefore, the maximum number of enemies stationed in each zone ≤ $W$)

For each test case, print on one line the minimum number of special squads that must be deployed to cover every zone of the Ontagon.

• Input

TC
1
8 100
70 60 55 43 57 60 44 50
58 40 47 90 45 52 80 40

• Output

TC
11

The arrangements where a single special squad can cover two adjacent zones are (2,10), (9,16), (4,5), (7,8), and (13,14). The remaining 6 zones can each be covered by a single special squad. Therefore, a minimum of 11 special squads must be deployed.

This problem is said to make beginners like myself, who solve Baekjoon algorithms in order, feel the difference in skill level. According to solved.ac, the problem's difficulty rating is a whopping PLATINUM III. Considering that the highest-rated problem I've solved so far was ACM Craft (GOLD III), this is a significantly harder problem. Even while actually solving it, I couldn't figure out an approach on my own at all, and even reading solutions was hard to fully understand.

The zones given in this problem are circular. To approach this problem more easily, you need to arbitrarily cut this circle and unroll it into a rectangular shape. In other words, while you solve it in a rectangular form, since it's actually circular, you must also account for the two cut ends of the rectangle when calculating. This is one of the factors that raises the difficulty.

If we diagram the zones as a rectangle based on the example given in the case, it looks like this:

As shown above, it can be represented as an 8x8 array. Now, how can we find the minimum value for filling up to and including the 6th row with special squads?

Let's think about it in reverse. Suppose our special squads are so capable that they always occupy the target zones with the minimum number of teams. The operation report marks the occupied zones as shown below, displayed as yellow regions.

That is, the yellow region represents where the minimum number of special squads was deployed, and it's also the result of the algorithm we'll actually implement.

By the problem's setup, a special squad must always be deployed as a whole team, and the minimum deployable unit is also one team. If so, if we exclude the area that one special squad can cover from the picture above, it can be divided into three cases, $a$, $b$, and $c$, as shown below.

In other words, if we can calculate the minimum number of special squads for those three cases, we can ultimately find the number of special squads that cover the entire 6th row. This is because, given that the minimum number of personnel has already occupied the rest of the zone, only the minimum deployable unit — one team — can additionally be deployed.

You may have seen the above three diagrams in many blogs; this is the background for why such diagrams appear out of nowhere.

The variables used to design the algorithm are as follows.

• $T$: number of cases
• $N$: number of rows of zones
• $e$: number of enemies per zone
• $a_i$: minimum number of special squads deployed for the first case
• $b_i$: minimum number of special squads deployed for the second case
• $c_i$: minimum number of special squads deployed for the third case

Let's design the minimum-value formula for $a_5$ using the first case.

Reasoning the same way as before, we need to find $a_5 - 1$, which is $a_5$ minus one team, and this can be divided into two cases depending on the condition of $e$.

Generally, the following case applies.

Since $a_5 - 1 = c_5$, $a_5 = c_5 + 1$

The following case applies only when $e_{04} + e_{05} ≤ W$.

Since $a_5 - 1 = b_4$, $a_5 = b_4 + 1$

Compared to the general case, this results in a smaller value for $a_5$.

Generalizing the formulas derived per case gives us the following.

• $a_5 = c_5 + 1$ -> $a_{i+1} = c_{i+1} + 1$
• $a_5 = b_4 + 1$ -> $a_{i+1} = b_i + 1$

Thus, the final general formula is as follows.

$$a_{i+1} = \begin{cases} c_{i+1} + 1, & (\text{default})\\ min(c_{i+1} + 1, b_i + 1), & (e_{0i} + e_{0(i + 1)} ≤ W) \end{cases}$$

Let's design the minimum-value formula for $b_5$.

We need to find $b_5 - 1$, which is $b_5$ minus one team, and this can be divided into two cases depending on the condition of $e$.

Generally, the following case applies.

Since $b_5 - 1 = c_5$, $b_5 = c_5 + 1$

This is identical to the formula for $a_5$.

The following case applies only when $e_{14} + e_{15} ≤ W$.

Since $b_5 - 1 = a_4$, $b_5 = a_4 + 1$

Compared to the general case, this results in a smaller value for $b_5$.

Generalizing the formulas derived per case gives us the following.

• $b_5 = c_5 + 1$ -> $b_{n+1} = c_{n+1} + 1$
• $b_5 = a_4 + 1$ -> $b_{n+1} = a_n + 1$

Thus, the final general formula is as follows.

$$b_{i+1} = \begin{cases} c_{i+1} + 1, & (\text{default})\\ min(c_{i+1} + 1, a_i + 1), & (e_{0(i-1)} + e_{0i} ≤ W) \end{cases}$$

Let's design the minimum-value formula for $c_5$. (Note that $c_5$ is filled up to row 4.)

We need to find $c_5 - 1$, which is $c_5$ minus one team, and this can be divided into several cases depending on the condition of $e$.

Generally, the following case applies.

Since $c_5 - 1 = a_4$, $c_5 = a_4 + 1$

Since $c_5 - 1 = b_4$, $c_5 = b_4 + 1$

Whichever of the two cases is smaller becomes $c_5$, resulting in the following formula.

$c_5 = min(a_4 + 1, b_4 + 1)$

The following case applies when $e_{04} + e_{14} ≤ W$.

$c_5 = c_4 + 1$

Compared to the general case, this results in a smaller value for $c_5$.

There's one special case for $c_i$. For $a_i$ and $b_i$, we only calculated values after subtracting the minimum deployable unit of 1. For $c_i$, because it's rectangular, up to 4 zones can be occupied by 2 teams.

The following case applies when $e_{03} + e_{04} ≤ W$ and $e_{13} + e_{14} ≤ W$.

$c_5 = c_3 + 2$

Compared to all cases, this results in a smaller value for $c_5$.

Generalizing the formulas derived per case gives us the following.

• $c_{i+1} = min(a_{i} + 1, b_{i} + 1)$
• $c_{i+1} = c_{i} + 1$
• $c_{i+1} = c_{i-1} + 2$

Thus, the final general formula is as follows.

$$c_{i+1} = \begin{cases} min(a_{i} + 1, b_{i} + 1), & (e_{0i} + e_{1i} > W)\\ min(a_{i} + 1, b_{i} + 1, c_{i} + 1), & (e_{0(i-1)} + e_{1(i-1)} ≤ W)\\ min(a_{i} + 1, b_{i} + 1, c_{i} + 1, c_{i-1} + 2), & (e_{0(i-1)} + e_{0i} ≤ W,e_{1(i-1)} + e_{1i} ≤ W) \end{cases}$$

Organizing the derived general formulas gives us the following.

$$a_{i+1} = \begin{cases} c_{i+1} + 1, & (\text{default})\\ min(c_{i+1} + 1, b_i + 1), & (e_{0i} + e_{0(i + 1)} ≤ W) \end{cases}$$ $$b_{i+1} = \begin{cases} c_{i+1} + 1, & (\text{default})\\ min(c_{i+1} + 1, a_i + 1), & (e_{0(i-1)} + e_{0i} ≤ W) \end{cases}$$ $$c_{i+1} = \begin{cases} min(a_{i} + 1, b_{i} + 1), & (e_{0i} + e_{1i} > W)\\ min(a_{i} + 1, b_{i} + 1, c_{i} + 1), & (e_{0(i-1)} + e_{1(i-1)} ≤ W)\\ min(a_{i} + 1, b_{i} + 1, c_{i} + 1, c_{i-1} + 2), & (e_{0(i-1)} + e_{0i} ≤ W,e_{1(i-1)} + e_{1i} ≤ W) \end{cases}$$

You can now translate the above formula into code, but it's not complete yet. That's because this zone is a circular, not linear, structure.

So far, for the sake of understanding the principle and deriving the formulas, we cut Ontagon arbitrarily and unrolled it into "Table-tagon" to compute the formulas. Since this linear structure has a start and end point but the circular one is a cyclic structure, we need to write the conditional formulas accordingly. In other words, we must assign initial values to some cases so that they're compatible with the circular structure in order to finally write the algorithm we want.

The picture below compares Ontagon and Table-tagon.

As shown, in the circular structure $e_{00}$ and $e_{07}$ can also be connected, but in the linear structure this is structurally impossible. Therefore, we need to assign initial values for these cases.

As you might guess, there are a total of 4 cases depending on the overlap shape.

The case where regions don't overlap, such as $e_{00}, e_{07}$ or $e_{10}, e_{17}$. This is the basic case, which is also applicable in a linear structure. Relating it to the shapes of $a_i, b_i, c_i$, it can be diagrammed as follows.

$a_i$ only fills the top cell of column $i$, so only $e_{00}$ is occupied, giving 1

$b_i$ only fills the bottom cell of column $i$, so only $e_{01}$ is occupied, giving 1

$c_i$ fills column $i - 1$, but $c_{-1}$ is logically impossible, so 0

Thus, the initial values are as follows.

$$a_0 = 1$$ $$b_0 = 1$$ $$c_0 = 0$$

These initial values are assigned when $i = 0$.

In this case, $c_N$ becomes the answer to the algorithm.

For example, when $N=8$, since it's $c_8$, we can find the most appropriate minimum value.

The case of occupying $e_{00}, e_{07}$. This case is only possible in the circular structure. Except for the no-overlap case, all remaining cases are only possible in a circular structure, so keep this in mind. When $i = 0$, there's no effect, so it's the same as the no-overlap case. Since overlapping requires at least two rows, $N > 1$ must be satisfied.

The connected part is highlighted with a checkered pattern. Since these two are connected to each other, a special squad from a different zone cannot occupy them. Therefore, this part should be treated as a nonexistent area when calculating the initial value. Taking this characteristic into account, the initial values can be assigned as follows.

In the example, since $N = 8$, the general form of the condition is $e_{00}, e_{0(N-1)}$.

$$a_1 = 2$$ $$b_1 = \begin{cases} 1, & (e_{10} + e_{11} ≤ W)\\ 2, & (e_{10} + e_{11} > W) \end{cases}$$ $$c_1 = 1$$

These initial values are additionally assigned when $i = 1$.

In this case, $b_{N-1} + 1$ becomes the answer to the algorithm. Think of $e_{00}$ and $e_{07}$ as combined into $e_{00}$.

For example, when $N=8$, since it's $b_7 + 1$, we can find the most appropriate minimum value.

The case of occupying $e_{10}, e_{17}$. The details are the same as the top-row-only overlap case.

In the example, since $N = 8$, the general form of the condition is $e_{10}, e_{1(N-1)}$.

$$a_1 = \begin{cases} 1, & (e_{00} + e_{01} ≤ W)\\ 2, & (e_{00} + e_{01} > W) \end{cases}$$ $$b_1 = 2$$ $$c_1 = 1$$

These initial values are additionally assigned when $i = 1$.

In this case, $a_{N-1} + 1$ becomes the answer to the algorithm. Think of $e_{10}$ and $e_{17}$ as combined into $e_{10}$.

For example, when $N=8$, since it's $b_7 + 1$, we can find the most appropriate minimum value.

The case of occupying $e_{00}, e_{07}$, $e_{10}, e_{17}$. The details are the same as the top-row-only overlap case.

In the example, since $N = 8$, the general form of the condition is $e_{00}, e_{0(N-1)}$, $e_{10}, e_{1(N-1)}$.

$$a_1 = 1$$ $$b_1 = 1$$ $$c_1 = 0$$

These initial values are additionally assigned when $i = 1$.

In this case, $c_{N-1} + 2$ becomes the answer to the algorithm. Think of $e_{00}$ and $e_{07}$ as combined into $e_{00}$, and $e_{10}$ and $e_{17}$ as combined into $e_{10}$.

For example, when $N=8$, since it's $c_{N-1} + 2$, we can find the most appropriate minimum value.

• Default
  • $a_0 = 1$
  • $b_0 = 1$
  • $c_0 = 0$

• Overlap only in the top row $(e_{00} + e_{0(N-1))} ≤ W)$
  • $a_1 = 2$
  • $b_1 = \begin{cases} 1, & (e_{10} + e_{11} ≤ W)\\ 2, & (e_{10} + e_{11} > W) \end{cases}$
  • $c_1 = 1$

• Overlap only in the bottom row $(e_{10} + e_{1(N-1)} ≤ W)$
  • $a_1 = \begin{cases} 1, & (e_{00} + e_{01} ≤ W)\\ 2, & (e_{00} + e_{01} > W) \end{cases}$
  • $b_1 = 2$
  • $c_1 = 1$

• Overlap in both rows $(e_{00} + e_{0(N-1)} ≤ W)$, $(e_{10} + e_{1(N-1)} ≤ W)$
  • $a_1 = 1$
  • $b_1 = 1$
  • $c_1 = 0$

Now, all the pieces we need to implement the algorithm are in place.

JAVA
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * Baekjoon problem #1006 algorithm class
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/06/06/a1006">1006 solution</a>
 * @since 2021.06.06 Sun 22:44:45
 */
public class Main
{
	private static int N;
	private static int W;
	
	private static int[][] e;
	
	private static int[] a;
	private static int[] b;
	private static int[] c;
	
	/**
	 * Main function
	 *
	 * @param args: [String[]] arguments
	 *
	 * @throws IOException data input/output exception
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		
		// Number of cases
		int T = Integer.parseInt(reader.readLine());
		
		for (int i = 0; i < T; i++)
		{
			int result = 2147483647;
			
			String[] temp = reader.readLine().split(" ");
			
			// Number of rows
			N = Integer.parseInt(temp[0]);
			
			// Number of special squad members
			W = Integer.parseInt(temp[1]);
			
			// Array of enemies per zone
			e = new int[2][N];
			
			for (int j = 0; j < 2; j++)
			{
				temp = reader.readLine().split(" ");
				
				for (int k = 0; k < N; k++)
				{
					e[j][k] = Integer.parseInt(temp[k]);
				}
			}
			
			a = new int[N];
			b = new int[N];
			c = new int[N + 1];
			
			a[0] = 1;
			b[0] = 1;
			c[0] = 0;
			
			// Start from index 0
			solve(0);
			
			result = Math.min(result, c[N]);
			
			// If there are two or more rows
			if (N > 1)
			{
				// If both rows overlap
				if (e[0][0] + e[0][N - 1] <= W && e[1][0] + e[1][N - 1] <= W)
				{
					a[1] = 1;
					b[1] = 1;
					c[1] = 0;
					
					// Start from index 1 (since initial values exist up to index 1)
					solve(1);
					
					result = Math.min(result, c[N - 1] + 2);
				}
				
				// If only the top row overlaps
				if (e[0][0] + e[0][N - 1] <= W)
				{
					a[1] = 2;
					b[1] = e[1][0] + e[1][1] > W ? 2 : 1;
					c[1] = 1;
					
					// Start from index 1 (since initial values exist up to index 1)
					solve(1);
					
					result = Math.min(result, b[N - 1] + 1);
				}
				
				// If only the bottom row overlaps
				if (e[1][0] + e[1][N - 1] <= W)
				{
					a[1] = e[0][0] + e[0][1] > W ? 2 : 1;
					b[1] = 2;
					c[1] = 1;
					
					// Start from index 1 (since initial values exist up to index 1)
					solve(1);
					
					result = Math.min(result, a[N - 1] + 1);
				}
			}
			
			System.out.println(result);
		}
		
		reader.close();
	}
	
	/**
	 * Algorithm function
	 *
	 * @param num: [int] starting index
	 */
	private static void solve(int num)
	{
		for (int i = num; i < N; i++)
		{
			c[i + 1] = Math.min(a[i] + 1, b[i] + 1);
			
			// If team c can occupy two adjacent zones
			if (e[0][i] + e[1][i] <= W)
			{
				c[i + 1] = Math.min(c[i + 1], c[i] + 1);
			}
			
			// If team c can occupy two sets of two adjacent zones
			if (i > 0 && e[0][i - 1] + e[0][i] <= W && e[1][i - 1] + e[1][i] <= W)
			{
				c[i + 1] = Math.min(c[i + 1], c[i - 1] + 2);
			}
			
			// Index correction for teams a, b (team c has one extra index)
			if (i < N - 1)
			{
				a[i + 1] = c[i + 1] + 1;
				b[i + 1] = c[i + 1] + 1;
				
				// If team a can occupy two adjacent zones
				if (e[0][i] + e[0][i + 1] <= W)
				{
					a[i + 1] = Math.min(a[i + 1], b[i] + 1);
				}
				
				// If team b can occupy two adjacent zones
				if (e[1][i] + e[1][i + 1] <= W)
				{
					b[i + 1] = Math.min(b[i + 1], a[i] + 1);
				}
			}
		}
	}
}

• Dynamic Programming

I started solving this on June 1st, and it took me nearly a week to fully understand this problem. I needed to write my own take on the solution — not someone else's — which meant I needed to fully understand the problem myself. Since I couldn't understand it just by reading other people's solutions, I worked through it and put together my own understanding in my own words. I hope others reading this post can more easily understand this difficult problem.

Even after understanding it, it's still fairly convoluted; the people who can derive this from first principles all the way to code deserve a lot of respect. Or maybe it's just that I lack the skill.

• The Casterian
• Gutgeonhage
• Test cases