Блог пользователя magieNoire

How to solve GCD 2010 -- Timus online judge.
Автор magieNoire, 10 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
      ← Rev. 5   Проголосовать: нравится +9 Проголосовать: не нравится

      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

      → Ответить
»
10 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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++.

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

      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).

      → Ответить