Nov 112014

J. Most Valuable Good Segment

Author: Felix Halim
Prepared By: Felix Halim, Suhendry Effendy
(link to problem J)

This problem has the least number of accepted submission (together with problem D). I expected this one to be a hard problem in this contest.

It’s a bit hard to explain the solution to this problem, but I’ll try my best. There are a couple ways (which I know) to solve this problem, but most of them are differ only in the implementation detail. I’ll explain my solution in this post.

For each element X, we need to find the first element (Y) to the right which sum with X is 0 (mod M). We need a data structure which able to: (a) store all all elements between X and Y, (b) answer how many elements are there in the set which at most a certain value. BIT (Binary Indexed Tree) data structure can be used. So, a naive (and more stupid) answer would be iterating from A[X+1] to the right, push all elements into BIT, and stop when you found A[Y] where A[X] + A[Y] = 0 (mod M). The value for X then will be the number of elements in BIT (?). Of course this answer will get WA (as we haven’t handled the distinct elements), not to mention TLE.

First, to avoid the WA, we have to modify our BIT a bit. Instead of storing all elements, we should store indexes of distinct elements. Choose the one with lower index if there are two or more elements with the same number. Next, to avoid TLE, we should do two things: (1) compute NOMOD[] for each element in the array, and (2) compute all element’s value in decreasing order (from N to 1). NOMOD[X] is the largest index where there is no element between index X and N in which the sum with A[X] is 0 (mod M); in other word either NOMOD[X] = N or A[X] + A[NOMOD[X]+1] = 0 (mod M). NOMOD[] can be computed in O(N) for all elements – hint: start from the last element. Thus, each query on BIT should be made with NOMOD[X], i.e. how many elements are there which value is at most NOMOD[X]. Now, to handle the distinct elements part, we should process each X starting from the last element. When we process X, first we have to remove all indexes in BIT which number is the same as A[X]. You can do it such that there is at most one such indexes needed to be removed for each X, i.e. by removing only the lowest index to the right (which have the same number). If you keep doing this at each X in decreasing order, then your BIT will only contain indexes of distinct elements.

Now, the problem also asked the segment which have such value. Supposed we already know that X is the head of the most valuable segment. We can find the segment end with min(NOMOD[X],NODUP[X]), where NODUP[X] is the largest index in which increasing X will not increase the value of the segment. Similar to NOMOD[], we can compute NODUP[] in O(N) for all X.

There are 49 submissions have been made for this problem, in which 3 teams managed to get accepted. The first team who solve this problem is Sylph (minute 163) from Bina Nusantara University. The other two are: Panda Shu from Bina Nusantara University (after their 15th attempts) at minute 248, and BerinGAS from University of Indonesia (with 6 attempts) at minute 289.

  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

  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

    • 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>