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.
“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
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.
a bit curious about problem H. Did you use the real Kawal Pemilu data for judge’s test case? 😀
According to the author: YES 🙂
Nice 😀
nice problem, nice editorial, pretty helpful, thx 🙂
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 😀
Lho, cara handle mod-nya (line 30, 41 – 43) jelas salah donk? Kenapa cuma consider pivot L yang ga punya pair-mod nya di dalam array input? Yang diminta kan pivot L yang segmentnya ga ada pair-mod nya.
contoh:
6 10
5 2 8 1 9 5
karena “((SL + Si) mod M) ? 0, for all i where L ? i ? R.”
apakah mksdnya nilai di index L, jika dipasangkan dgn semua nilai dari L sampai R, modnya tdk akan 0 ?
utk input spt itu outputnya impossible bkn ?
oh, bayangan sy sblmnya, segment L-R, jumlah bilangan yg berbeda harus sama dgn jml bilangan berbeda array 1 – N
kelihatannya di situ kesalahannya, gara2 asumsi jml bil beda hrs sama dgn array input…
pertama baca merasa ada kemiripan dgn soal spoj DQUERY yg blm sy mengerti jg 🙁
Ho iya, “value” di soal J ini sama dengan nilai si d-query (number of distinct elements in a segment).
“for all i where L <= i <= R" -- artinya cuma dipair dengan semua [L, R], bukan [1, N]; [L, R] itu segmentnya.
permisi, mengganggu lagi :D, saya sdh mencoba membuat NOMOD utk range tertentu
semoga sudah benar :), [[REMOVED]]
hanya saja kompleksitasnya NOMOD tdk O(N) karena menggunakan map, kalau ada unsorted map spt c++ 11, mgkn bs 😛
membaca tutorial kadang jd pengen kerjain lg, apakah bs diupload soalnya ke OJ ?
aduh msh ada salah ><, setelah di-fix, smg uda bener [[REMOVED]]
Oit, maap beberapa hari ini lagi away, baru bisa cek messagenya.
Solusi yang pertama (SbojVj) masih salah, tapi solusi yang kedua (5i1Mvi) AC 😀
Anyway, soal sedang diupload ke JOJ, sebentar lagi selesai.
terima kasih banyak 😀
Soal INC sudah diupload ke JOJ. Kode soal: INC14A … INC14J
http://jollybee.binus.ac.id/oj/site/problemset/problem/code/INC14A/
Warning: sistem JOJ belum stabil, jadi terkadang gradernya bisa down.
ok pak, terima kasih, di grup fb ada yg minta sekalian saya post ya link-nya 🙂
oh ya, apa komen saya yg menyertakan kode yg hampir AC dan AC bs diedit link-nya, takutnya dicopas buat JOJ (kalau boleh copas buat JOJ ya tidak diedit tidak apa2)
saya wkt nulis di ideone tdk login waktu itu, jd tdk bs edit kode di ideone
Sip, udah diremoved semua link ke code nya 😀
How about ACM-ICPC 2014 Jakarta write up?? Will it be published?
Yes, it will.
I “lost” one week due to other events after ICPC (and I’ve just come back to my home). So, expect a few more days delay 🙂
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.