magieNoire's blog

How to solve GCD 2010 -- Timus online judge.
By magieNoire, 10 years ago, In English

Hello everyone, I tried recently this problem, but unfortunately I got TLE. I am using an O(nlogn) algorithm as supposed( a segment tree for updating the list and a map to keep track of frequency of each number and it's position ). I think there is some overhead with the update function -- can I rewrite it iteratively ? Any suggestion is welcomed.

Here is my code: link

Note: if someone can redirect me to a non recursive implementation of segment trees that will be great.

  • Vote: I like it
  • +8
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
10 years ago, # |
  Vote: I like it +9 Vote: I do not like it

I solved it with the same (recursive) approach, but I did not use a map. I compressed the input values by using an auxiliary array (and by sorting it). It passes in 0.171 seconds and 3965 KB.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please explain more. A tiny example will be perfect :)

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 5   Vote: I like it +9 Vote: I do not like it

      For the sample input:

      5
+ 8 (i=0)
+ 6 (i=1)
+ 8 (i=2)
- 8 (i=3)
- 8 (i=4)

      I keep a copy of the input, I sort the "copy" thus getting this:

      5
+ 6 (i=1)
+ 8 (i=0)
+ 8 (i=2)
- 8 (i=3)
- 8 (i=4)

      I assign increasing numbers k to "mark" distinct values (in this case there are 2 distinct values):

      5
+ 6 (i=1) (k=1)
+ 8 (i=0) (k=2)
+ 8 (i=2) (k=2)
- 8 (i=3) (k=2)
- 8 (i=4) (k=2)

      (while computing this, I store for each i the corresponding k).

      Then, for each i (from 0 to q - 1), I add/remove the number (which I get from the "original" input) in/from the k-th position.

      Code here

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks dude! Good explanation and good solution too ;)

        → Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I've used the segment tree realization, which I know as "Implicit segment tree". The main idea is to build segment tree on whole range of numbers (from 1 to 1000000000 in this problem), but nodes we create only when they are need.

My solution passes in 0.187s with VC++ compiler and 0.343s with G++.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The link that you gave me doesn't work ( empty page ). I am the only one ?

    You know what I got it accepted with VC++ compiler too. But, I am highly interested in your solution, please fix the problem.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      My solution using an implicit segment tree. There are at most 100000 numbers to store; a root-to-leaf path requires lg(1000000000) ~ 31 nodes in the segment tree. Pre-allocate a pool of nodes of size 100000 * 31, whenever you want to create a new node, fetch it from the pool (faster than malloc-ing at runtime). Update is similar to ordinary segment tree (I use left/right pointers).

      → Reply