The problem [https://codeforces.net/contest/579/problem/D] can be solved using a simple greedy approach by precalculating prefix ors and suffix ors but I wanted to solve it using DP in which we multiply an array element at most K times ranging from 0 to k. But it fails on test 23. Thanks in advance... my solution : 69268483
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.12.2024 02:22:15 (l1).
Десктопная версия, переключиться на мобильную.
При поддержке
Auto comment: topic has been updated by masaow (previous revision, new revision, compare).
Shouldn't you call $$$solve(n-1,k)$$$? Your array is stored from $$$0$$$ to $$$n-1$$$, but you pass $$$n$$$ as $$$idx$$$ which means, you are accessing $$$a[n]$$$ in first recursion.
Yeah! You are write that's a silly mistake. But with solve(n-1,k) its failing on test 23 i.e ; 3 1 2 17 18 4 expected output is 54 and i'm getting 53 .
Okay, so I did some testing, and then I noticed that you're not storing already computed answer. If you don't use answer till now, then you're basically doing greedy, and not dp. Your function $$$solve(idx,used)$$$ just calculates maximum OR possible using at most $$$"used"$$$ multiplications and indices upto $$$"idx"$$$, but if your answer from indices $$$"idx+1", ... n$$$ has some bits already, then instead of maximizing $$$OR$$$ from left side ( $$$0,...idx$$$ ) you instead want maximum and trying to exclude those set bits already.
Basically, you need $$$prev$$$ ( already calculated answer ) as a state too.
Changed your code only a little bit ( used map to memoize, since we need to store long long ) here, but it gives TLE because now there are too many states. I guess you could solve it iteratively instead of using recursion.
Follow up: So I quickly wrote an iterative dp for this, but that fails the same case, because again, it is "greedily" choosing best prefix instead of looking at the whole answer. Code here.
Oh superb bro !!!! Amazing I got your point. A simple greedy solution is to precalculate prefix and suffix ors and for each iteration multiply a[idx] by x k times and or it with precalculated prefix and suffix ors and max of this is the answer. THANKS a lot gupta_samarth :)