i am having problem in solving this problem using 0/1 knapsack problem. http://codeforces.com/contest/19/problem/B

# | User | Rating |
---|---|---|

1 | tourist | 3557 |

2 | Radewoosh | 3468 |

3 | Um_nik | 3429 |

4 | Petr | 3354 |

5 | Benq | 3286 |

6 | mnbvmar | 3280 |

7 | wxhtxdy | 3276 |

7 | LHiC | 3276 |

9 | ecnerwala | 3214 |

10 | yutaka1999 | 3190 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 191 |

2 | Radewoosh | 180 |

3 | tourist | 172 |

4 | Vovuh | 165 |

4 | PikMike | 165 |

4 | antontrygubO_o | 165 |

7 | rng_58 | 160 |

8 | majk | 156 |

8 | Um_nik | 156 |

10 | 300iq | 155 |

i am having problem in solving this problem using 0/1 knapsack problem. http://codeforces.com/contest/19/problem/B

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/18/2019 10:55:53 (e2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

You need to keep two states:

I: Current item.R: Number of items remaining.The transition is, take the item

Ipayingc_{i}and go to the itemI+ 1 withR- 1 -t_{i}remaining items, or dont take the itemIand go to the itemI+ 1 withRremaining items.ohk...thank u!

There's a simple solution that runs in

O(2^{N}). Just try all combinations and keep the best.But 1 ≤

N≤ 2000, do you have some super computer ?Well, not me, but the studios where I usually work make 3D movies too, so they have a farm of around 45 powerful computers running at the same time.

Wow, in how many seconds them run 2

^{2000}operations ?, can you give me one powerful computer ?Well, you can do the math. One powerful computer can do 1000 million operations per second, which is around 2

^{30}, so it can do 60 * 2^{30}in a minute. That's around 2^{36}in a minute and 2^{42}in one hour, so it would take something like 2^{1958}hours to run the solution. One year has 2^{13}hours approximately, so it will take 2^{1945}years. Is it good enough?Complexity if exponential, but you can get it to run under 1000ms (in java) using the sleep.thread() trick. This should be common knowlegde.

Indeed, or you can use #pragma lightspeed in C++55, which will be released in 37 years. But since it uses black hole quantum physics to compile and run, it doesn't matter, you can use it today by calling that pragma.

So it turns out C++ really is better at everything. I think using a bitset will reach O(1/n) (watch out for n = 0) complexity, but seems that its too difficult for a simple problem as this

well they didn't make minecraft in c++ did they

Another way is [itemupto][time] with observation time > 2000 dont matter. do we store dp[item][time] = minimum cost.

Note that for each item we can "add" 1 second to it because it takes care of itself.

And we us the dp table to solve problem.

EDIT: Wow it seems I've greatly infected the integrity of CF by giving out correct solutions! The horror!

Seems people doubt the accuracy of my previous comment. Well, my method works and it's implementation is short:

http://codeforces.com/contest/19/submission/44525896

Cool man doesn't look at the explosion.

Cool codeforces-er doesn't edit comment after being downvoted (I think).

yeah if you look back at the explosion you gonna get hit by shrapnel, thats how movies work

but yeah dont subject me to your personal definition of "cool"