Nov 112014
 

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.


  27 Responses to “ACM-ICPC INC 2014”

  1. “One popular approach was by first sorting all the strings and pair each succesive string whenever possible”, kode saya spt itu, hanya saja pasangkan dr yg terpanjang http://ideone.com/PGjPAq

  2. komen untuk prob J

    β€œOne popular approach was by first sorting all the strings and pair each succesive string whenever possible”, kode saya spt itu, hanya saja pasangkan dr yg terpanjang http://ideone.com/PGjPAq

    • koreksi, prob G

    • Ngga, kode kamu nggak seperti itu. Approach kamu itu jadi sama dengan approach greedy yang bener (pasangin dari leaves) — string yang paling panjang saat itu pasti leaf.

      Yang dimaksud “pair each succesive string whenever possible” itu comparenya bener-bener cuma sama 1 string di sebelahnya aja (sorted); sedangkan kamu compare dengan yang panjangnya lebih pendek.

  3. a bit curious about problem H. Did you use the real Kawal Pemilu data for judge’s test case? πŸ˜€

  4. nice problem, nice editorial, pretty helpful, thx πŸ™‚

  5. saya penasaran dgn problem yg blm sempat saya kerjakan (dan AC), apakah mungkin akan diupload ke situs online judge ?

    saya dpt ide sederhana utk problem J dgn menelusuri apakah suatu nilai bisa jadi pivot (menjadi ‘L’), setelah itu cek apakah bs dr index tersebut menjadi good segment, jika tidak cetak impossible, kode saya : [[REMOVED]]

    thx koreksinya πŸ˜€

  6. How about ACM-ICPC 2014 Jakarta write up?? Will it be published?

  7. How can I get input data ?

    Thank you for sharing.

    • Ah… I didn’t notice this comment before >.< I'll not share the input data publicly. You can test your solution in some online-judges, e.g., tokilearning or joj. (I think) I have sent the test data to the admin on those sites.

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)