CarlaZZ's blog

Need help for data structure problem
By CarlaZZ, history, 9 years ago, In English

We have got N number, from 1 to N. There are 2 types of query:

  1. move number from index i to index j
  2. write what number is at index i

ex.

(0,1,2,3,4);

2 ? -> 2

(0,1,3,4,2); <- from 2 to 4

(0,4,1,3,2); <- from 3 to 1

3 ? -> 3

4 ? -> 2

(0,4,1,3,2); <- from 1 to 1

0 ? -> 0

1 ? -> 4

2 < N < 10 000 000 M < 500 000

I tried with the sqrt-decomposition but not fast enough.. any ideas? http://cms.di.unipi.it/#/task/vasi2/statement

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

this problem can be solved using bit or segment tree. can u share link to the problem so that I can test my idea and then discuss wid u.

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

If M is the number of queries you could try coordinate compression: instead of keeping track of all numbers keep track of those that appear in the queries.

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

    Assume that we have N numbers from 1 to N.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Can you send a link to the problem? The difficulty of this problem depends on the time and memory limits.

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

I solved this problem using a modified AVL tree.

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

    I've tried to solve the problem using an AVL tree like a list, with log N insertion, deletion, and find k-th item. The main problem is that I spend so much time by populating the tree with the initial number from 0 to N-1, so it's TLE.. suggestions?

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

      Do you build the tree in O(N) or O(N*logN) time?

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

        O(N), the build function is like:

          Node* construct(int s, int d)
    {
        if ( s > d ) return NULL;
        int mid = (s+d)/2;
        Node* new_node = new Node();
        new_node->id = mid;
        new_node->left = construct(s, mid-1);
        new_node->right = construct(mid+1, d);
        new_node->size = size_node(new_node->left) + size_node(new_node->right) + 1;
        new_node->height = max(height(new_node->left), height(new_node->right)) + 1;
        return new_node;
    }
        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Focus on the fact that you don't actually need to erase and insert nodes in each update...

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

            You mean when the two positions are the same?

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

              Does the tree size change after an update? If no, is it necessary to delete and allocate nodes during updates?

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

                The size of the tree does not change .. I don't know how to do an update without remove a node and re-insert it in the right position. Is it possible?

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

                  It is necessary to remove and insert nodes but you don't need to dynamically allocate them.

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

                  are you saying that i can create a static array of nodes of fixed size, and use only this space for the nodes? The heap dynamic allocations are "time dangerous"?

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

                  You call N times the function "new" or "malloc" to build the tree, instead if you use a static array you allocate memory only once.

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

                  now I'll try

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

                  I continue to receive TLE.. probably is something else c.c

                  edit. 100/100. I balance the tree only when the difference between the height of the child is more than 5.

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

The link for the problem is http://cms.di.unipi.it/#/task/vasi2/statement . The description is in italian

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

I think some straightforward-like solution with a BST might do well. The only improvement (O((M + N)logN)  →  O(MlogM)) I can think of is to store not single elements but ranges of consecutive elements. For example, in the very beginning you have a BST with only one node which represents the range 1... N. While updating you find the range which has the i-th element and split it into no more than three (that is, you delete it and insert several new).

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

Treap

→ Reply