SevenDeadlySins's blog

911 G. Mass Change Queries
By SevenDeadlySins, history, 7 years ago, In English

Can this problem be solved by sqrt decomposition?

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

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

Yes indeed.This problem can be solved using sqrt decomposition.

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

Does anybody have Java implementation for the same?

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

I solved is with sqrt decomp and dsu. My java solution TLEd tho so I just ported it to c++ to get it to pass. I think it's probably solvable with sqrt decomp in java but you might need to do something smarter than I am or perhaps add some more optimizations. JAVA: 33816939 C++ : 33817280

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

    What exactly did u use the dsu for ? Why cant we just use linkedlist ? I didnt get whats the flaw in my logic .. I have given the solution link above

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

      So basically if it said to turn x into y, I had a lookup table for which set was currently x and which set was currently y and I merged both sets. Then I put that no set is currently x. Looking through your solution it does seem to have the same runtime as mine but perhaps the fact that you initialize 100 linked list per bucket is where the main difference is since mine only initializes 1 dsu and 2 arrays.

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

Here's my AC Solution : 33799911 .

I did get TLE in one of my submission on Test 2, link : 33755328, it was due to way the elments in one bucket were shifted from x to y. Intially, I used merge() to shift element to y and then delete the elements from x. This leads to TLE. After using splice() , if worked fine till test case 114, because of way I've coded the process,made necessary changes in the implementation, and it works in 2047ms.

I did see a submission with sqrt decomposition working in ~970ms. link :33736310

Well, SQRT decompostions works for this problem. It's only the way they have been implemented in the code leads to TLE.

I don't have much knowledge of Java implementation, so can't help with your code.

Here's a link to an interesting question, it asks you to change element x to y in range l to r, and also count element x in range l to r : https://www.hackerearth.com/practice/data-structures/advanced-data-structures/segment-trees/practice-problems/algorithm/replace-27c5286c/ , consider it as more advance version of this question. Tester's (Bohdan Pryshchenko) solution is in C++.

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

    Thank you for your reply. For the advanced vesrion of the question that you have posted link for, we will have to use node based pesistant segment tree right ?

    → Reply