anh1l1ator's blog

By anh1l1ator, 23 months ago, In English,

So , formally the problem statement :

You are given a sequence A of N (N≤250000) integers between 1 and 50000. On this sequence you have to apply M (M≤10000) operations of the form: modify the i-th element in the sequence and then say how many inversions are there in the sequence. The number of inversions in a sequence is given by the number of pairs (i,j) with i < j and Ai > Aj.

My approach is to , 1) Divide the array into square root pieces , and maintain a fenwick tree for each of the blocks that stores 1 corresponding to each number in that block ( For querying number of numbers lesser than a particular value in that block )

2) Count the inversions .

3) Now whenever Update comes , I update get inversions from all blocks except the index's box(I count the difference between the inversions due to the new value — inversions due to old value and add it to the inversions) and add it ! Plus I traverse the block of index ! Total Query time O( Sqquare root of N * log 50000 ) .

It is giving TLE Even with fast scanning and outputting Here is my code , can it be further optimised ? Ideone

Link to problem Spoj

Is there any other approach to it ?

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

»
23 months ago, # |
  Vote: I like it +1 Vote: I do not like it

For each query you should find: in how many inversions i-th number participed before and new number of inversions for updated number.Total number of inversions will change for difference of this two number. So you should count in each query how many numbers are bigger left of a[i] and how many numbers are smaller right of a[i]. You can do this in sqrt(n)-easy dp. Dp[i][j] count the number of smaller numbers than j in i-th block.After query update dp for block where is placed i-th number. Total complexity O( n sqrt(n)).

  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    To update DP[i][j] after each update it will take j operations where j can be at max 50000. Now to speed up this procedure I have used a series of fenwick trees (for each square root block a different one ) which can cause fast retrieval and fast updation but the problem is it is timing out!!

    As your state is Dp[i][j] count the number of smaller numbers than j in i-th block

    I dont think there is someway to update it faster than log N . Please see my code !!

    • »
      »
      »
      23 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      My bad, you are right ( I see three ziroes in max number, not four :D ). I can make it a little better ( maybe):

      You can sort all the blocks and after that to find number of values bigger and smaller than a[i] in every block you can run binary search. Complexity of that program is O(m sqrt(n) log (sqrt(n))).

      • »
        »
        »
        »
        23 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Happens with everyone :D And I will try it once I get AC , coz I dont think there is much difference as the maximum value of elements is lesser than max of N . Plus BIT doesn't have a big constant

»
23 months ago, # |
  Vote: I like it +6 Vote: I do not like it

I recently solved this problem using sqrt decomposition , i got TLE first when i had block size as 500 , but then i tried some other things like trie + treap / trie + segtree , all TLEd then finally i went back to sqrt decomposition and kept block size as 1000 and added fast input and it gave AC .

Final AC code with sqrt decomp

Segtree + Trie (TLE)

Treap + Trie (TLE)

TLE sqrt decomp

  • »
    »
    23 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Are you talking about Mo's algorithm ? What have you done ? I think your solution is quite close to mine!

    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I do not know dude , when I change my block size to 1005 my code gets AC -_- !!

      • »
        »
        »
        »
        23 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        And I didnt even knew that it is a standard type of algorithm known as "SQuare root decomposition"

  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Do you know of a problem in which the expected solution involves a Treap + Trie or a Segment Tree with a Treap for each node?
    I'd really like to solve such a question :P

    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      you can use it anywhere but i dont think its ever expected

      • »
        »
        »
        »
        23 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you show me a good problem in which you've used it and got AC :P

        • »
          »
          »
          »
          »
          14 months ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          I know 1, if u are still interested.

          • »
            »
            »
            »
            »
            »
            14 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yes please

            • »
              »
              »
              »
              »
              »
              »
              14 months ago, # ^ |
                Vote: I like it +5 Vote: I do not like it

              http://informatics.mccme.ru/moodle/mod/statements/view3.php?chapterid=111142. THe statement is in russian, but the rough trasnlation is:

              Shooting gallery. U have 3D space and N shooting marks in it, which are rectangles, parallel to x0y plane and Z meters away from it. (U shoot from x0y plane). All Z[i] are different.

              Then u have M queries, each query is: given 2D point on the x0y plane, meaning that shoot is happening from this point. When u shoot bullet moves perpendicular to x0y plane towards increasing z. When it hits a mark bullet stops and mark falls.

              For each shoot task is to output number of mark it hits or 0, if it doesnt hit any1.

              Queryes are happening one by one, previos queryes DO affect marks obviously(i mean, if any mark falls after some query, its not used anymore).

            • »
              »
              »
              »
              »
              »
              »
              14 months ago, # ^ |
                Vote: I like it +5 Vote: I do not like it
            • »
              »
              »
              »
              »
              »
              »
              14 months ago, # ^ |
                Vote: I like it +5 Vote: I do not like it

              If u will need some hints PM me, otherwise i might not notice.

  • »
    »
    14 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Same happened with me. Changing block size to 1000 from 500 worked. I have analyzed the complexity. This is why it worked

    For each query, For 500 block size complexity= O(500+ 500 * log(500))=O(5000) For 1000 block size complexity= O(1000+ 250 *log(1000))=O(3500)

    Therefore 1000 works

    Edit: Corrected my mistake.

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      I believe O(1009) makes no sence btw

      • »
        »
        »
        »
        14 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh Sorry My bad. It was 500*log(500) so O(5000) for the 500 block and O(3500) for the 1000 block.

        • »
          »
          »
          »
          »
          14 months ago, # ^ |
            Vote: I like it +13 Vote: I do not like it

          i mean you dont use O() like that, it has to have some function of N inside brackets. at least i believe in it

        • »
          »
          »
          »
          »
          14 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I think there exists some better algorithm for this task seeing multiple solutions with very small running time

»
14 months ago, # |
  Vote: I like it +6 Vote: I do not like it

you can use segment tree with an ordered multiset(also you can compress numbers first and use fenwick that is faster) on each node. so we can answere each query in O(lg(n)^2)

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Yeah this is a very easy solution , I probably didn't ever knew anything as segment tree with sets that's why i wrote such a bad solution :D

»
14 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

My implementation. Sqrt-Decomposition + BIT. Time : 1.1 Seconds (before they changed the processors). 0.8 seconds on Cube.

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    And how did you know if its cube or pyramid or anything else? Where's this written?

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      it's written under the time limit

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I wrote many solutions and I got two of them accepted:

Nested Trie

Trie + sqrt(n) decomp