Блог пользователя Tutis

Power of bitsets
Автор Tutis, история, 5 лет назад, По-английски

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)$$$?

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится

      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.

      → Ответить
»
5 лет назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

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)
→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить