Tutis's blog

Power of bitsets
By Tutis, history, 5 years ago, In English

I was solving this task: https://oj.uz/problem/view/IOI17_mountains. The first submission got 20 points (brute-force using bitsets). The second submission got 70 points because I used memoization. After that, I wrote my own bitset with custom hash and got 100! Can someone suggest why the number of different bitsets is $$$O(n^2)$$$?

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

»
5 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Does the editorial mention anything about the number of different bitsets?

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

    Intended solution is some DP using $$$O(n^2)$$$ states.

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

      So isn't hat the reason? If they have $$$O(N^2)$$$ states in their dp, there's a high chance that your solution will have $$$O(N^2)$$$ different states. Sorry if I can't help you more.

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

It's not. It is exponential. Here is a python program that generates a counter-test:

print 2000

def f(x):
    if(x>0):
        print x,x,
        f(x-1)
        print x,x,

f(500)
→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

We were given this problem in IOITC and many of us used segment tree in this problem

→ Reply