i have the problem knapsack has condition N<=100 and w,v<=10^9.
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3773 |
| 3 | Radewoosh | 3646 |
| 4 | ecnerwala | 3624 |
| 5 | jqdai0815 | 3620 |
| 5 | Benq | 3620 |
| 7 | orzdevinwang | 3612 |
| 8 | Geothermal | 3569 |
| 8 | cnnfls_csy | 3569 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 163 |
| 2 | cry | 161 |
| 3 | maomao90 | 160 |
| 4 | -is-this-fft- | 159 |
| 5 | awoo | 158 |
| 6 | atcoder_official | 157 |
| 7 | adamant | 155 |
| 7 | nor | 155 |
| 9 | maroonrk | 152 |
| 10 | Dominater069 | 148 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 20.09.2024 02:16:50 (k1).
Десктопная версия, переключиться на мобильную.
При поддержке
Any other condition specified? Probably there's.
No has any other condition :v
No constraint on the input array?
a[i],b[i] <=10^9 too
What if you use a map instead of array to save space? Just a guess.
But i will have TLE in the case N=100 and K=10^9
Unless the test cases are weak.
This one has a extra condition $$$w\times v\le 10^9$$$, and I don’t think the problem is solvable without this condition.
The problem i refer don't have any special condition :v
LOL it's my problem
Could you please add the link? Or the full statement?
The problem is vietnamese :(
The problem probably has some other stuff if it is meant to be solvable with this range of values. The best you can do with a small $$$N$$$ would be "meet in the middle", which will still be a TLE if your $$$N \leq 100$$$
Vip pro ngừi Việt. As far as i know there's a solution with $$$O(n\sqrt{totalweight})$$$ complexity. So with $$$totalweight=n*w= 1e11$$$ then yeah this solution passes. The idea is that there are about $$$\sqrt{w}$$$ possible sums of subsets when the sum of all of the elements in the set equal $$$w$$$ so we just need to calculate all those possible sums first, then apply the general dp algorithm -> $$$O(n\sqrt{sum})$$$ instead of $$$O(n*sum)$$$. How? I havent implemented it myself but this blog exlains it well and also provides an implementation :D https://codeforces.net/blog/entry/97396
How is that true? Pick elements: $$$1, 2, 4, 8, 16, 32, \ldots, 2^n$$$. Each number from $$$[0, 2^{n+1})$$$ can be obtained as a sum of some subset. We have sum $$$w = 2^{n+1} - 1$$$ and $$$w + 1$$$ possible sums of subsets.
You did not understand that blog. N in that blog is the sum (or maybe more precisely the sum being O(N)). That'd give us O(totalweight^1.5) in here, which is obviously useless.
Yeah you are right, my sincere apologies, I didn't read the blog carefully, what a shame.
https://vtv.vn/giao-duc/vu-sai-sot-de-thi-o-quang-binh-giao-vien-noi-sai-2-cau-so-giai-thich-chi-sai-1-20231215105607163.htm
This is vietnamese newpaper about their problem
Can you add a link to the problem?
My problem from the province exam