JacobianDet's blog

TLE IN SPOJ PATULJCI
By JacobianDet, history, 7 years ago, In English

I tried this problem using segment tree but it's getting TLE. Can anybody explain how to remove TLE from this code?

Solution : https://pastebin.com/8iuk4mQp

Problem : http://www.spoj.com/problems/PATULJCI/

  • Vote: I like it
  • -5
  • Vote: I do not like it

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

Well, i don't see why this code should pass. There are simple alternatives than trying to squeeze a heavy-constant segment tree anyway, but if you still want to, you can read. I was able to pass with a Merge Sort Tree in szkopul using some constant optimization, code here. There is a simple solution using the fact that the element appears > 1/2 in the range, we can try to pick random a number between [L,R] and see if in the range, this number appears more than 1/2 times using a histogram, the probability of error is if you try k numbers

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

    I read that editorial but still couldn't get past the TLE. By the way that codechef question got AC. Thanks for help

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

      Can you explain the probability idea more clearly as I am not aware about it

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

        Just random generate index between L and R ~30 times and see if the number this index represent appears more than 1/2 in subarray [L,R]

        → Reply