ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1353. Milliard Vasya's Function

Why this DP solution doesnt work?
Posted by Dmitriy 11 Oct 2016 14:17
I thought that this problem is so easy. After many tries to solve that I should say: that is not so easy and I cant solve it! Please, if you DP-master tell me where I'm wrong.

So, the state is dp[sum][length] += dp[sum - digit][length - 1], for each digit 0..9. The base is dp[1..9][1] = 1.

I've got WA#10:
My program for 10 output: 43756 (correct answer: 43749)

I can't find a little bug ;(
Re: Why this DP solution doesnt work?
Posted by Dmitriy 11 Oct 2016 14:18
[code]

for s := 1; s <= S; s++ {
for l := 2; l <= 9; l++ {
for d := 0; d < 10 && s - d > 0; d++ {
if dp[s - d][l - 1] == 0 {
continue
}

dp[s][l] += dp[s - d][l - 1]

if d == 0 {
dp[s][l]++
}
}
}
}
[/code]
Re: Why this DP solution doesnt work?
Posted by Dmitriy 16 Oct 2016 09:20
Re: Why this DP solution doesnt work?
Posted by Egor 1 Dec 2016 23:39
You don't need to store previous positions:

for (int position = 2; position <= 9; position++)
for (int sum = 81; sum > 0; sum--)
for (int digit = 1; digit <= 9; digit++) if (sum >= digit)
ways[sum] += ways[sum - digit];
Re: Why this DP solution doesnt work?
Posted by Manciu Ion 1 Jan 2017 05:26
because you have to start l at one and eliminate continue and s - d >= 0
Re: Why this DP solution doesnt work?
Re: Why this DP solution doesnt work?
Posted by IlushaMax 4 Apr 2017 01:08
Guys, what are you doing in New Year? Hahaha
Re: Why this DP solution doesnt work?
Posted by Dmitriy 13 Feb 2018 06:22
No. You are wrong here.
I've found my error, it was a dp base.

Thx for all.