Nov 082013
 

J. Alien Abduction Again

Author: Felix Halim
(link to problem J)

This problem was prepared by Felix Halim (author) and Risan (tester). I didn’t interfere with their work on this problem, but from what I see, I think Felix Halim was very strict with this problem. He specifically asked me to put the note “your program must be very-very efficient” in the problem statement. He also didn’t want Risan’s Segment Tree solution to get accepted. Felix’s solution run in ~1.5 seconds while Risan’s run in ~12 seconds, but after a lot of (crazy?) optimization, Risan managed to cut down his running time to ~6 seconds. For this kind problem, even a constat factor in your algorithm plays an important role. You have to understand your algorithm well (not just the Big-Oh). This problem not only tests your problem solving skill, but also your programming skill.

As a side note, Felix managed to convey a “secret” message to someone (special?) in the problem statement, but he said that the message was too secret such that the target didn’t notice that ((:. This message has nothing to do with the problem or the contest at all.

This write-up is written by the author himself, Felix Halim. If you want to know more about this problem, you can visit his page on http://felix-halim.net/story/icpc13/j-preparation.php

Given up to N functions fp(x) = ax3 + bx2 + cx + d, each with different range [xp1, xp2]. These functions are added incrementally. As the functions get added, there queries asking about the total sum of the values of the functions that intersects with range [x1, x2] at integral values of x.

Approach #1 – Bruteforce
For each query, iterate through all the functions and iterate on the [x1, x2] range. This clearly will get TLE.

Approach #2 – Segment Tree
The first observation is that each power can be computed/maintained separately (i.e, the sum of values for ax3 can be maintained in a separate data structure from bx2). Thus we can have 4 (identical) data structure to maintain the sum. The data structure suitable for this is (Lazy) Segment Tree.

This solution is not supposed to work.

Firstly, it will require more than 64MB memory (will not work for Java solutions, however, for C++ it can still run since there is no memory limit for C++). Secondly, the problem asks for a very-very efficient program :).

Sadly, due to PC2 inability to distinguish runtime of 5 seconds vs 4 seconds, Segment Tree solutions can get accepted if it is implemented efficient enough. That is, we set the time limit to be 4 secs in the PC2, but solutions with 5 seconds runtime were still receiving YES. Well, I was disappointed with PC2 with this glitch, but seeing there was a team from NTU spent 10 attempts to get AC, it’s justified :P.

Approach #3 – Binary Indexed Tree (Fenwick Tree)
A more efficient approach is to use Binary Indexed Tree (BIT) for each power. However, it is not that easy. You must know how to perform range updates using BIT.

Here is a pointer on how to use BIT to do Range Updates (read all the links in the comments too):
http://petr-mitrichev.blogspot.com/2013/05/fenwick-tree-range-updates.html

To give an example, consider the simplest case where f(x) = d. That is, the values for a, b, and c are zero. In this case, the problem is equal to a very simple BIT range update.

Here is a nice post on how to convert a (Lazy) Segment Tree into two BITs:
http://apps.topcoder.com/forums/?module=Thread&threadID=756271&start=0&mc=2#1579597

We can generalize this for the other powers (a, b, and c) and we will need five BITs. The runtime for this approach is less than 2 seconds and it consumes only ~20MB memory.

This problem also requires the knowledge of mod-inverse. That is, you will need to do division with modulo somewhere in the calculation.
http://comeoncodeon.wordpress.com/2011/10/09/modular-multiplicative-inverse/


  12 Responses to “ACM-ICPC 2013 Jakarta – Problems and Analysis”

  1. are you sure there isn’t mod operation ?

    and this : j = j + 1, why it isn’t j = j-1 ?

    • Ah, you’re right, it should be j =j – 1 (updated).

      MOD operation is not needed, What we really need is whether a two substrings have a same hash value or not, not the hash value itself. There are only addition and multiplication operators, so overflowing the result doesn’t matter.

  2. ^that comment above is for pasti pas

  3. Halo Mr. Suhendry.
    Saya ingin sekali bisa berkompetisi di ACM ICPC. Saya Mahasiswa tingkat 2 di salah satu perguruan tinggi di bandung. Tapi skill koding saya tidak terlalu bagus. algoritma sorting saja masih bingung. Gimana ya kiat nya untuk belajar algoritma yg baik dan benar agar bisa nanti suatu saat ke ACM ICPC?

  4. How to determine which prime number should be used? I tried some prime numbers and the result is not as expected.

    • (Problem F). Just use large prime number (larger is better, its chance to collide is smaller). I used 1000003 and it’s fine.

      • I have implemented it and submitted on Live Archive, but got WA 😀
        Is there something wrong with my implementation? Could you please check it? http://pastebin.com/ECJX9yEa

      • I didn’t read your code, but it failed the first sample input: PASTIPAS.

        • Yes and it works if I do MOD operation, but still WA on Live Archive. Does your solution with above algorithm still work on LA? Maybe you/others have added more test cases to break that hash function? Or my implementation wrong?

        • I’m the one who send the data to LA and I’m pretty sure LA’s admin was quite busy to do any changes on the dataset.

          BTW, I’ve just noticed an error in F’s pseudocode. There is one line which is wrong. Try to figure that out! 🙂

          hint: pay attention to the rolling hash (when you do the multiplication with prime number); you might want to check other resources on rolling hash.

  5. ^ problem F Pasti Pas!

  6. Problem H can be solved by Dynamic Programming,here I find two states,one is index of the current question,another is wrong answers used/left so far, and then minimize the answer. But this solution does not work,though sample test case gives correct output. I saw another boolean state in some accepted codes in HUST, which tries both minimizing and maximizing. Can you please explain why another state is needed here?

 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)