I. Prime Reduction Game
Author: Suhendry Effendy
Prepared By: Suhendry Effendy, Felix Halim
(link to problem I)
I like this problem and I’m happy with the fact that only a few strong teams were able to solve this problem.
From the problem statement:
At each step, you should choose two non-coprime elements from two distinct rows, let the number be A and B. Next, divide those two numbers by a prime number P where GCD(A,B,P) = P.
Those statements basically mean that you have to divide both numbers with a (common) prime number. You might have noticed that there are no relation between different prime numbers (prime number cannot divide other prime number). Thus, you can treat each prime number independently to solve this problem.
For a prime number P, first you have to compute the number of prime factor P on the given matrix and group them by their row – you will obtain an array of length R where each element denotes the number of prime factor P in the corresponding row; let’s say the array as B. This array represents the “potential moves” you can made in the original matrix. Each move consists of reducing two different non-zero elements in the array by 1.
Finding the maximum number of moves (pairs) is easier. At each step, you only need to pair the largest element with any one element in the array. Keep doing it until you left with at most one non-zero element, in which it terminates. This solution might seem slow, but it gets accepted (try to calculate the worst case). Alternatively, you can compute the maximum number pairs directly. If the largest element is larger than the sum of all remaining elements, then clearly the maximum possible pairs is equal to the sum of those remaining elements (because all those remaining elements can be paired completely with the largest element). Otherwise, there’s always a way to pair the elements such that the remaining non-zero element (if there is one) will have a value of 1. I’ll leave the proof to the reader.
Next, to find the minimum, first you have to observe this fact: the pairing process will terminate when there is at most one non-zero element remained; otherwise, it’s still possible to pair the remaining elements (the game hasn’t terminated yet). Therefore, to find the minimum number of pairs, we should pair the elements such that the (last) remaining non-zero element is as large as possible. We can do this by finding the maximum number of moves in the array excluding the largest element, and then pair the remaining non-zero element with that largest element. Recall that we want to find the minimum number of moves, which mean we should maximize the last remaining non-zero element. So, we should pair the elements such that the largest pair has as few pairs as possible (this where “the maximum number of moves in the array excluding the largest element” comes). Again, I’ll leave the detail proof to the reader.
Remember that you have to do all the above procedure for all prime numbers.
There are 43 submissions have been made for this problem, in which 5 teams managed to get accepted. The first team who solve this problem is DELAPAN.3gp (minute 106) from Institut Teknologi Bandung.