Please read the new rule regarding the restriction on the use of AI tools. ×

woolgatherer's blog

Complexity of Bitmask DP
By woolgatherer, history, 2 years ago, In English

Here in this problem problem it is said that for n jobs, given is the base price p for each job and an extra charge s for every pair of jobs (i, j), meaning that you have to pay additional s for job i, if and only if job j was completed before, you are to compute the minimum total costs needed to finish all jobs. constraint: 1 <= tc <= 100, 1 <= n <= 14 and base price 1 <= p <= 100000. I noticed some people solved it in O(2^n * n^2) using bitmask dp. As n is 14 so the complexity is approximately 321426400(> 1e8) considering 100 tc as well. How come it passes in 1 sec? An AC Code

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

As I can see, n<=14. 14^2=196, 2^14=16384. So it's 10^6. Should pass with no problem. Or did I miss something?

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

    It has 100 test cases, so i think 100 would be multplied, isn't it?

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

      Overall it's about 3*10^8 which might fit in one second

      → Reply