Show all threads Hide all threads Show all messages Hide all messages |
Page 2 |
Hint: use DP | Raphael Osipov | 1353. Milliard Vasya's Function | 25 Jul 2023 20:54 | 1 |
try think like dp[length of string][sum of string] = count of numbers, answer is dp[9][s]. |
Easy Approach HINT | Sai Teja Chokkarapu | 1353. Milliard Vasya's Function | 31 Jul 2020 12:42 | 1 |
-> think of doing this problem first -> count of n digits numbers whose sum is equal to x. ->First try to think for smaller numbers less than 1000 i.e from 1 to 999. -> Create the tree for the same i.e numbers less than 999. -> after finding f(n,sum)(n is the number of digits and sum is the required sum). -> you can find f(9,sum)for all numbers less than 1000000000. -> now finally you need to handle for one number 1000000000. Cheers Edited by author 31.07.2020 12:43 |
С++ code for brute force | D4nick | 1353. Milliard Vasya's Function | 11 Mar 2020 14:39 | 1 |
#include <stdio.h> #include <map> using namespace std; int main() { int ans, sum, ost, s; long int full, i; map <long int, int> sums; for (i = 1; i <= 1000000000; i++) { sum = 0; full = i; do { ost = full % 10; full /= 10; sum += ost; } while (full > 0); sums[i] = sum; } for (s = 1; s <= 81; s++) { ans = 0; for (i = 1; i <= 1000000000; i++) if (sums[i] == s) ans++; printf("{%ld}, ", ans); } } it will give you {10}, {...}, ... , {...}, vector that you can use for getting AC with O(1). Edited by author 11.03.2020 14:40 Edited by author 11.03.2020 14:44 |
hint | Desserg | 1353. Milliard Vasya's Function | 27 Dec 2019 10:44 | 1 |
hint Desserg 27 Dec 2019 10:44 Python 3 when counting by force I met TLE on the 45th test. I printed out all the values of the function and saw that it is mirrored after 40 values. f (40) = f (41) f (39) = f (42) ... f (2) = f (79) therefore, counting only to 40, I got Accepted |
HINT | Michael Jordan | 1353. Milliard Vasya's Function | 28 Jan 2019 14:43 | 1 |
HINT Michael Jordan 28 Jan 2019 14:43 just be patient while making precalculation :) |
what is the meaning of this problem?? | Abbos Bo'kaboyev | 1353. Milliard Vasya's Function | 21 Nov 2018 16:51 | 1 |
I am not able to understand the problem properly. Is there somebody who can explain the problem with example. Pls Edited by author 21.11.2018 16:56 Edited by author 21.11.2018 16:57 |
Why this DP solution doesnt work? | Dmitriy | 1353. Milliard Vasya's Function | 13 Feb 2018 06:22 | 8 |
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 ;( [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] 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]; because you have to start l at one and eliminate continue and s - d >= 0 No. You are wrong here. I've found my error, it was a dp base. Thx for all. Guys, what are you doing in New Year? Hahaha |
all tests please | Evilcookie228 | 1353. Milliard Vasya's Function | 13 Sep 2016 17:02 | 1 |
|
Getting WA#2. Anybody got the test case? | Schwinn | 1353. Milliard Vasya's Function | 26 Mar 2016 14:35 | 2 |
Hint: consider what allowed for first digit |
Recursive solution works fine! If you are getting TLE, Rethink your DP state :) | Pradyumna Bang | 1353. Milliard Vasya's Function | 30 Nov 2015 22:17 | 1 |
Recursive solution works fine! If you are getting TLE, Rethink your DP state :) |
If you have TL (with recursion) | Evgeny Shulgin | 1353. Milliard Vasya's Function | 1 Mar 2015 13:05 | 1 |
Let your recursion function is "void dfs1(int k, int curr)", k is digit, curr is current S, then use it code: int start = 0; start = max(start, curr - 9 * (k - 1)); int end = min(9, curr); if(k == 10) { end = min(1, end); } for(int i = start; i <= end; i++) { dfs1(k - 1, curr - i); } It turns out, curr does not go beyond zero at k = 0! I have 937ms with this solution But with precalc I have 31ms :) Good luck |
My recursive solution passed i want to convert it to iterative. Need help | Nikhil | 1353. Milliard Vasya's Function | 2 Oct 2015 22:26 | 2 |
Hi Can anybody help me to convert my recursive solution to iterative. Can i Post code here? If your solutions are in MAX_SUMxMAX_DIGITS matrix, then just fill the solutions row-by-row. This way it is guaranteed that at each step you have all solutions you have to sum up already computed. |
o(1) solution | Arseniy | 1353. Milliard Vasya's Function | 1 Jul 2013 23:30 | 1 |
You can solve it o(1) just precalc answers fir all test by brute forse, than put it to array. Proffit |
WA2 or is it? | alpha900i | 1353. Milliard Vasya's Function | 3 Jun 2013 17:05 | 2 |
Ok, so my program gets WA2. And if I add code like int t2=45; if(n==2) cout << t2 << endl; I get WA3. Funny fact though - "45" is answer my program always gave for n==2. So we have two different "45", and only one of them is good as answer. Somehow cout << s(9,n) << endl; doesn't work well, even if s(9,n)=45. Someone had problems of this kind? Ok-key, my bad. Had some good little out-of-array code in my check function, so it spoiled everything. |
Page 1 |
Hint | PrankMaN | 1353. Milliard Vasya's Function | 30 Sep 2014 22:12 | 3 |
Hint PrankMaN 30 Mar 2013 17:47 It's not the easiest problem and I don't know good solution, but if I was on the olympiad and would have to solve the problem, I would just precalculate the answer. a difficult combinatorics problem. x1 + x2 +... + x10 = S with limitation: xi between ? , ? Need to fill an array COUNT[1..9][0..81] and answer is COUNT[9][S] Exclusion: if S == 1, then answer is 10 Edited by author 30.09.2014 22:13 |
AV #33 | balalaeshnik | 1353. Milliard Vasya's Function | 6 Jan 2013 05:44 | 2 |
AV #33 balalaeshnik 6 Jan 2013 04:51 What's wrong with 33th test?)) Or what reazons to access violation? And my IDE write correct answer - 31861500 |
Why WA1? | Savchenkov (NNSTU) | 1353. Milliard Vasya's Function | 6 May 2013 19:17 | 2 |
Why WA1? Savchenkov (NNSTU) 13 Jul 2012 14:14 My program gives the following answers: 1 -> 10 2 -> 45 3 -> 165 10 -> 43749 40 -> 45433800 80 -> 9 81 -> 1 Why do I get WA1? Edited by author 13.07.2012 14:17 Your solution is correct for every case. But whats your answer for 0? I think it should be 1. But its not testing case 0. Edited by author 06.05.2013 19:19 Edited by author 06.05.2013 19:19 Edited by author 06.05.2013 19:21 |
It's very easy to overcome TLE. | balandini | 1353. Milliard Vasya's Function | 25 Feb 2018 04:49 | 4 |
If you have program which gives right answer for the problem, but it's too slow and gets TLE, then you may just calculate answers for every possible input(there are only 81 possible variants of input, so you can calculate them all) and then create another program: put array of 81 possible answers in this program and them just read s from input and write in output corresponding answer from the array. I had made such program and it got AC. In this case what is the use solving this problem. Edited by author 25.02.2018 04:48 Edited by author 25.02.2018 04:49 Edited by author 25.02.2018 04:49 Edited by author 25.02.2018 04:49 In this case what is the use solving this problem. |
Test #11 what's the answer? | Hi4ko | 1353. Milliard Vasya's Function | 19 Dec 2011 18:41 | 1 |
I can't understand my mistake( |
What's this mean... | Sunnat | 1353. Milliard Vasya's Function | 10 Dec 2011 19:19 | 1 |
mem[1][9] <=> 1=>>10 mem[20][9] <=> 20=>>299 or 29 ? |