🔗 Full Problem 1017

Given a list of numbers, Jimin wants to pair them up so that the sum of each pair is a prime number. For example, suppose we have ${1, 4, 7, 10, 11, 12}$. Jimin can group them as follows.

$1 + 4 = 5$, $7 + 10 = 17$, $11 + 12 = 23$
or
$1 + 10 = 11$, $4 + 7 = 11$, $11 + 12 = 23$

Given a list of numbers, write a program that, when Jimin pairs up all the numbers, prints in ascending order which numbers can be paired with the first number. In the example above, $1 + 12 = 13$, which is prime. However, there is no way to pair up the remaining 4 numbers such that their sums are all prime. Therefore, the answer for the example is 4, 10.

The first line gives the size $N$ of the list. N is a natural number less than or equal to 50, and is even. The second line gives the numbers in the list. Each number in the list is a natural number less than or equal to 1,000, with no duplicates.

Print the answer on the first line. If there is none, print -1.

• Input

TC
6
1 4 7 10 11 12

• Output

TC
4 10

Perhaps thanks to having already been introduced to bipartite matching through problem 1014, Cheating, this was, relatively speaking, one of the more understandable Platinum problems I've solved so far.

The content is still fairly convoluted, but the behavior required by the algorithm can be summarized as follows. Suppose we have the input array of 6 numbers ${ 1, 4, 7, 10, 11, 12 }$. If we pair up the numbers in the array two at a time and add them, we get 3 sums in total. The problem asks us to: if all the paired sums are prime, print the numbers matched with the first number of the input, sorted in ascending order.

As explained in the example, the cases where all the paired sums are prime are $1 + 4 = 5$, $7 + 10 = 17$, $11 + 12 = 23$ and $1 + 10 = 11$, $4 + 7 = 11$, $11 + 12 = 23$. Since the very first number of the input is 1, the numbers paired with 1 — 4 and 10 — are the answer.

Now let's look at the details more closely. The key to solving this problem is primality. This algorithm requires primality testing. There are many ways to test for primality, but using the classic Sieve of Eratosthenes makes this fairly easy to solve.

Now that we have a way to test primality, we need to properly pair up the numbers in the input array. The key requirement is that the sum of each pair must be prime. One approach would be to try adding every pair of elements, but as the array grows larger, the required computation grows too, so that's not ideal. In other words, we need to group things using only plausible combinations.

Let's think about primes. A prime is a number divisible only by 1 and itself. In other words, a prime must be odd. Extending this premise, the sum of a paired set of numbers must be odd. The only way for the sum of two numbers to be odd is odd + even — there's only one such case.

So, if we split the input into groups of odd and even numbers and only add numbers between the two groups, the result will always be odd, meaning that number has a chance of being prime. Since we need to combine the two groups without overlap, bipartite matching is a fitting solution. If we split into odd and even groups, and connect pairs whose sum is prime with an edge, this becomes solvable using bipartite matching.

The image above shows Example 1 split into odd and even groups and displayed as a bipartite graph. If we match all 6 numbers, we'll get 3 pairs. Since every number must form exactly one pair to be added, the result of bipartite matching must always be $N \div 2$.

The very first number in the example is 1. In other words, we need to find combinations where the sum of every paired element is prime, and then find which number is matched with 1 in each of those combinations. Extending this, if the sum of a number paired with 1 isn't prime in the first place, there's no need to even consider it.

If the matching result in the image above turns out to be 3, that means there exists a combination where every paired sum is prime. All we need to do is save that combination and find the value paired with 1. If the number of odd numbers and even numbers doesn't match, matching is impossible, so per the problem's conditions we must return -1.

The elements whose sum with 1 is prime are 4, 10, and 12 — all of them — so we can connect all of them with an edge. If we connect one of the elements that can be matched with 1, we can then run bipartite matching on just the remaining 4 elements.

If 1 is matched with 4, the prime-sum matching for the remaining 4 elements can be represented as shown in the image. Since the sums of the combinations $[ 7, 10 ]$ and $[ 11, 12 ]$ are both prime, the combination $[ 1, 4 ]$, $[ 7, 10 ]$, $[ 11, 12 ]$ satisfies the algorithm's conditions. Therefore, 4 is included in the answer.

What if 1 is matched with 12 instead? That can be represented as shown above. For 7, either 4 or 10 works as a pair and gives a prime sum, but for 11, neither 4 nor 10 gives a prime sum, so no matter how you match the remaining elements, the matching result for the 4 elements is only 1. In other words, the total matching count — including the one pair with 1 — is only 2, which doesn't satisfy $N / 2$, so this combination cannot be part of the answer. Therefore, the result for the example is 4 10, as shown in the output.

JAVA
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.LinkedList;

/**
 * 백준 전체 1017 문제 알고리즘 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/06/26/a1017">1017 풀이</a>
 * @since 2021.06.26 Sat 03:19:32
 */
public class Main
{
	// 에라토스 테네스의 체 배열 (소수 판별용)
	private static final boolean[] IS_NOT_PRIME = eratosthenes();
	
	// 왼쪽 배열 (이분매칭의 기준)
	private static int[] left;
	
	// 오른쪽 배열
	private static int[] right;
	
	// 노드 연결 여부
	private static boolean[][] hasNode;
	
	// 방문 여부
	private static boolean[] isVisit;
	
	// 매칭된 수
	private static int[] matched;
	
	// 현재 선택 중인 수
	private static int selected;
	
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 *
	 * @throws IOException 데이터 입출력 예외
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		// 입력값 갯수
		int N = Integer.parseInt(reader.readLine());
		
		// 입력값 배열
		int[] numbers = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		
		// 첫 번째 수가 홀수일 경우
		if (numbers[0] % 2 != 0)
		{
			// 왼쪽 배열에 홀수를 할당
			left = Arrays.stream(numbers).filter(value -> value % 2 != 0).toArray();
			right = Arrays.stream(numbers).filter(value -> value % 2 == 0).toArray();
		}
		
		// 첫 번째 수가 짝수일 경우
		else
		{
			// 왼쪽 배열에 짝수를 할당
			left = Arrays.stream(numbers).filter(value -> value % 2 == 0).toArray();
			right = Arrays.stream(numbers).filter(value -> value % 2 != 0).toArray();
		}
		
		// 홀수 배열과 짝수 배열의 수가 동일할 경우 (이분매칭 가능)
		if (left.length == right.length)
		{
			hasNode = new boolean[left.length][right.length];
			
			// left의 첫 번째 행은 기준 매칭이므로 이분 매칭에서 제외한다.
			for (int i = 1; i < left.length; i++)
			{
				for (int j = 0; j < right.length; j++)
				{
					int ref = left[i] + right[j];
					
					// left[i] + right[j]의 값이 소수일 경우
					if (!IS_NOT_PRIME[ref])
					{
						// 노드를 연결한다.
						hasNode[i][j] = true;
					}
				}
			}
			
			LinkedList<Integer> list = new LinkedList<>();
			
			// 첫 번째 수와 상대 그룹의 요소를 하나씩 매칭해본다.
			for (int i = 0; i < N / 2; i++)
			{
				// left[0]와 right[i]의 합이 소수일 경우
				if (!IS_NOT_PRIME[left[0] + right[i]])
				{
					selected = i;
					
					int size = bipartite();
					
					// 모든 요소가 매칭될 경우
					if (size == N / 2)
					{
						list.add(right[selected]);
					}
				}
			}
			
			// 하나도 매칭되지 않은 경우
			if (list.size() == 0)
			{
				writer.write("-1");
			}
			
			// 매칭이 하나 이상 있을 경우
			else
			{
				// 오름차순으로 정렬
				list.sort(Integer::compareTo);
				
				StringBuilder builder = new StringBuilder();
				
				for (int item : list)
				{
					builder.append(item).append(" ");
				}
				
				writer.write(builder.toString().trim());
			}
		}
		
		// 홀수 배열과 짝수 배열의 수가 동일하지 않을 경우 (이분매칭 불가능)
		else
		{
			writer.write("-1");
		}
		
		writer.newLine();
		writer.close();
		reader.close();
	}
	
	/**
	 * 이분 매칭 갯수 반환 함수
	 *
	 * @return [int] 이분 매칭 갯수
	 */
	private static int bipartite()
	{
		// 이미 left[0]과 right 요소 하나가 선택됨
		int size = 1;
		
		matched = new int[left.length];
		
		Arrays.fill(matched, -1);
		
		for (int i = 1; i < left.length; i++)
		{
			isVisit = new boolean[left.length];
			
			// 매칭 가능할 경우
			if (dfs(i))
			{
				size++;
			}
		}
		
		return size;
	}
	
	/**
	 * DFS 알고리즘 결과 반환 함수
	 *
	 * @param num: [int] 시작점
	 *
	 * @return [int] 매칭 갯수
	 */
	private static boolean dfs(int num)
	{
		// 첫 방문일 경우
		if (!isVisit[num])
		{
			isVisit[num] = true;
			
			for (int i = 0; i < right.length; i++)
			{
				// 연결된 노드가 있으며, 첫 번째 숫자와 매칭된 숫자가 아니며, 소수일 경우
				if (hasNode[num][i] && i != selected && !IS_NOT_PRIME[left[num] + right[i]])
				{
					// 매칭이 아직 되지 않았거나, 매칭된 숫자가 다른 숫자와 매칭될 수 있을 경우
					if (matched[i] == -1 || dfs(matched[i]))
					{
						matched[i] = num;
						
						return true;
					}
				}
			}
		}
		
		return false;
	}
	
	/**
	 * 아레토스 테네스의 체 배열 반환 함수
	 *
	 * @return [boolean[]] 아레토스 테네스의 체
	 */
	private static boolean[] eratosthenes()
	{
		boolean[] isNotPrime = new boolean[2000];
		
		isNotPrime[0] = true;
		isNotPrime[1] = true;
		
		int maxPrime = (int) Math.ceil(Math.sqrt(2000));
		
		for (int i = 2; i < maxPrime; i++)
		{
			// 소수일 경우
			if (!isNotPrime[i])
			{
				for (int j = i + i; j < isNotPrime.length; j += i)
				{
					// 아직 소수가 아님을 표시하지 않았을 경우
					if (!isNotPrime[j])
					{
						// 소수의 배수는 소수가 아니므로 제외함
						isNotPrime[j] = true;
					}
				}
			}
		}
		
		return isNotPrime;
	}
}

For convenience, matching is always performed with the left group as the reference. The goal is to find, among the valid combinations, the numbers matched with the first number — and the first number could be either odd or even. So depending on whether the first number is odd or even, the corresponding group is assigned to the reference array.

JAVA
// 첫 번째 수가 홀수일 경우
if (numbers[0] % 2 != 0)
{
	// 왼쪽 배열에 홀수를 할당
	left = Arrays.stream(numbers).filter(value -> value % 2 != 0).toArray();
	right = Arrays.stream(numbers).filter(value -> value % 2 == 0).toArray();
}

// 첫 번째 수가 짝수일 경우
else
{
	// 왼쪽 배열에 짝수를 할당
	left = Arrays.stream(numbers).filter(value -> value % 2 == 0).toArray();
	right = Arrays.stream(numbers).filter(value -> value % 2 != 0).toArray();
}

The code above shows this. Based on the left array left, if the first number is odd, the odd-number array is assigned to left; otherwise, the even-number array is assigned.

For primality testing, we use the Sieve of Eratosthenes algorithm to prepare a primality array covering the maximum possible sum of elements, 2,000.

Wait, the problem says the maximum value an element can take is 1,000?
Since we're adding an odd number and an even number, the maximum possible sum is the sum of the maximum values of each: 999 + 1,000 = 1,999.

Since the array only needs to go up to 2000, I judged it far more efficient to prepare the array up front rather than comparing on every single operation. If you wanted to test primality on the fly for each operation instead, you'd compute the square root of the number being tested and divide it by every number from 2 up to that square root. If any of them divides evenly, the number is not prime.

JAVA
// 대상 숫자
int number = 1000;

// 소수 여부
boolean isPrime = true;

// 가장 작은 소수인 2부터 대상의 제곱근까지 나누기
for (int i = 2; i <= Math.sqrt(number); i++)
{
	// 나누어 떨어지는 수가 있을 경우
	if (number % i == 0)
	{
		isPrime = false;
		break;
	}
}

You could write it roughly in the form shown above.

JAVA
// 첫 번째 수와 상대 그룹의 요소를 하나씩 매칭해본다.
for (int i = 0; i < N / 2; i++)
{
	// left[0]와 right[i]의 합이 소수일 경우
	if (!IS_NOT_PRIME[left[0] + right[i]])
	{
		selected = i;
		
		int size = bipartite();
		
		// 모든 요소가 매칭될 경우
		if (size == N / 2)
		{
			list.add(right[selected]);
		}
	}
}

Once we've split the groups, we select a reference match by pairing the input's first number $left[0]$ with each element of the other group one at a time. We only proceed when !IS_NOT_PRIME[left[0] + right[i]] — that is, when the pairing sum is prime. If it's not prime, there's no need to even check it. selected represents the element currently matched with $left[0]$. This is needed because the element matched with $left[0]$ can no longer be matched with anything else, so it must be excluded from the rest of the matching.

This can be represented as shown in the image above. Since 1 has already been matched with 10, we need to remove the edges connecting 10 to 7 and 11 for the rest of the matching to work correctly. The connected edges are managed in the hasNode array. Based on Example 1, the values of hasNode are as follows.

Now, if we match 1 with 10, hasNode looks like this.

We need to remove every other edge connected to 1 and 10, and set hasNode[1][10] = true. You could declare a temporary array and modify it that way, but to reduce array operation overhead, this is designed so that setting selected = 10 causes the index matching selected to be treated as false during the DFS algorithm.

JAVA
/**
 * 이분 매칭 갯수 반환 함수
 *
 * @return [int] 이분 매칭 갯수
 */
private static int bipartite()
{
	// 이미 left[0]과 right 요소 하나가 선택됨
	int size = 1;
	
	matched = new int[left.length];
	
	Arrays.fill(matched, -1);
	
	for (int i = 1; i < left.length; i++)
	{
		isVisit = new boolean[left.length];
		
		// 매칭 가능할 경우
		if (dfs(i))
		{
			size++;
		}
	}
	
	return size;
}

/**
 * DFS 알고리즘 결과 반환 함수
 *
 * @param num: [int] 시작점
 *
 * @return [int] 매칭 갯수
 */
private static boolean dfs(int num)
{
	// 첫 방문일 경우
	if (!isVisit[num])
	{
		isVisit[num] = true;
		
		for (int i = 0; i < right.length; i++)
		{
			// 연결된 노드가 있으며, 첫 번째 숫자와 매칭된 숫자가 아니며, 소수일 경우
			if (hasNode[num][i] && i != selected && !IS_NOT_PRIME[left[num] + right[i]])
			{
				// 매칭이 아직 되지 않았거나, 매칭된 숫자가 다른 숫자와 매칭될 수 있을 경우
				if (matched[i] == -1 || dfs(matched[i]))
				{
					matched[i] = num;
					
					return true;
				}
			}
		}
	}
	
	return false;
}

The bipartite matching source is shown above. bipartite() isn't much different from a standard bipartite matching algorithm. The reason size starts at 1 is that the input's first number left[0] has already been matched with a right[m] whose sum is prime.

Filtering happens in dfs() based on a condition. The condition expression is hasNode[num][i] && i != selected && !IS_NOT_PRIME[left[num] + right[i]].

• hasNode[num][i]: whether left[num] and right[i] are connected (i.e., their sum is prime)
• i != selected: whether left[num] has already been matched with right[i]
• !IS_NOT_PRIME[left[num] + right[i]]: whether left[num] and right[i] sum to a prime

Matching is only performed when all of the above conditions are satisfied.

There's no guarantee that $N$ is even, or that the number of odd and even numbers in the input is equal, so in that case we must output -1. Also, even if all the conditions are met, if not a single matching succeeds, we must still output -1.

• Mathematics
• Number Theory
• Primality Testing
• Bipartite Matching
• Sieve of Eratosthenes