oguzk's blog

Basic Query Problem
By oguzk, 9 years ago, In English

We have N balls(numbered from 1 to N) and we have 2 types of queries:

1-put ball x in front of ball y

2-print the ith ball's number

initial state: 1 2 3 4

query 1 : 1 3 1 --> 3 1 2 4

query 2 : 1 4 3 --> 4 3 1 2

query 3 : 2 2 --> 3

query 4 : 2 4 --> 2

How to perform these queries efficiently ?

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

»
9 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

I think with SQRT-decomposition you can do it in :

  • Query 1: Find the bucket that contains the ball in steps and put the ball in position inside the bucket in another steps. If the bucket is not the last one, get the last ball from this bucket and put in the beginning of the next bucket, so you can always have only items inside each bucket. You can maintain a list for fast insert/deletion in any place, so pushing a ball in front and popping back is done in O(1), and the bucket-balancing phase is done in at most steps as well.

  • Query 2: You can find the bucket that contains the position you want in either by doing a binary search or in plain . Inside the bucket you run through the list in to find the ball you want.

Final complexity is per query.

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

    caioaao How do I "Find the bucket that contains the ball in root N steps" in query 1 ?

    Got it by using a boolean array [rootN][N] size. Which marks what balls are present in the bucket. Thankyou.

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

      You can also keep an array [N] marking the bucket idx for each ball, and remember to update it anytime a ball moves from one bucket to another. This way you'll find the bucket in O(1). When I wrote the answer, I thought the first query was "Put ball x in front of ith ball", that's why I thought of going through the buckets in to insert a ball.

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

Looks like a basic Treap exercise

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

    Absolutely agree , an Implicit Treap can solve that problem in O( log ( n ) ) per query.

    Link

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

      Do you have another link in english?

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

        You can use a Web page translator(like Google Translator) or use Google Chrome to go through This page in English.

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

Can the queries be proceeded offline? If yes, there is a solution, which takes O(N + Q). I wanted to give this problem on my team's contest in Petrozavodsk, but I could not pick restrictions, so that only linear solutions would pass. The main idea is to copy balls instead of moving them, while storing them in a list, so that the list will contain all the previous versions of every ball. At first one can proceed all queries of the 1-st type. Then iterate through the list and for every version of every ball get its position in the list. After that, one can answer all queries of the 2-nd type.

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

Splay tree may solve in O(logN) average complexity per query.

→ Reply