The problem : Identify the Number Any help will be much appreciated .
Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3880 |
| 2 | jiangly | 3669 |
| 3 | ecnerwala | 3654 |
| 4 | Benq | 3627 |
| 5 | orzdevinwang | 3612 |
| 6 | Geothermal | 3569 |
| 6 | cnnfls_csy | 3569 |
| 8 | jqdai0815 | 3532 |
| 9 | Radewoosh | 3522 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | awoo | 161 |
| 2 | maomao90 | 160 |
| 3 | adamant | 156 |
| 4 | maroonrk | 153 |
| 5 | -is-this-fft- | 148 |
| 5 | SecondThread | 148 |
| 5 | atcoder_official | 148 |
| 8 | Petr | 147 |
| 9 | nor | 144 |
| 9 | TheScrasse | 144 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.07.2024 00:27:10 (j2).
Десктопная версия, переключиться на мобильную.
При поддержке
maybe it can be solved using dp with printing the path but i didnt try to solve it.
Can you be more specific ? , like what are the overlapping sub-problems here !
He is throwing random guesses.
First of all, I have to say that I didn't solve the problem. However, I think the following approach works well. Let DP[pos][rem] be the maximum number with reminder rem (when it's divided by Q) that we can obtain considering the digits from 0 to the position pos. Clearly, the answer will be DP[N.size()-1][R] , and is not difficult to realize that DP[pos][rem] = max( DP[pos-1][rem] , DP[pos-1][newrem]*10 + N[pos] ) , where newrem = (rem — N[pos] ) * inv(10,modQ) , here there are some tricky cases. If newrem doesn't exist , if newrem takes more than one value because 10 and Q have some common factor(observe that if this is the case, there are at most 10 possible values for newrem) and I think that's it. I hope this help.
This approach makes sense ,but how can I take the max number with reminder rem when I can't store the number !?
Let's define DP[ind][rem] where ind is the index of the character in the string n and rem is the current remainder when divided by Q. DP[ind][rem] contains a pair of the maximum length for this subproblem and the leftmost digit.
Now we can calculate DP[ind][rem] from DP[ind + 1][rem] and DP[ind + 1][rem * 10 + N[ind] % Q]. If one of them has a larger length than the other, then it's optimal to choose the one with the maximum length. If both lengths are equal, then the optimal is to choose the one with the larger leftmost number. If both have the same lengths and leftmost digit, It'll be optimal to choose the current index rather than a next one (because the current index can cover more than a later one).
Isn't it possible when both subproblems have the same lengths and leftmost digit but the past one was larger and the current index didn't cover any more digits ?
No. Imagine that there are two indices x, y where x < y where you can get the same length and leftmost digit from both. Now the second left most digit in the x subproblem can be chosen from x + 1 to n where in the y subproblem it can be chosen from y + 1 to n only, as x < y then it's guaranteed to reach the answer from x.
The whole problem actually states.You are given N digits.Choose a subset of them so that the number formed gives R as rest and is maximul possible.
This can be solved by DP. dp[i][j]=maximum number formed using from first i digits and it gives rest j.
With digit i you can move from 0 to Q-1 and add digit i at the end :)