Show all threads Hide all threads Show all messages Hide all messages |
31 ms is achievable with just combinatorics | sweepea | 1353. Milliard Vasya's Function | 31 Jul 2024 13:38 | 2 |
If you give me your email i can send you really fun AC solution using 0,15 ms ) |
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 |
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. |
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 |
For people, who have TLE. | Dima_Philippov | 1353. Milliard Vasya's Function | 1 Dec 2016 23:43 | 9 |
If you are using recursion function to calc the answer, then I suggest you to do it in one of some ways: 1) To write DP without using recursion. 2) To use array of memory and put there -1 if we calced the function of this parametres and 0 if not. 3) if you write in C++, inline may be will help you. If you have any questions, write. Edited by author 19.11.2010 01:08 :) Edited by author 19.11.2010 12:02 And me too - I want to see how to use recursion in this problem =))) goryinyich [dog] inbox [dot] ru Thank you!(otajanov_quvondiq@mail.ru.) Only for reading & outputting one integer? You can precalculate all the 81 values locally (it could take up 1 minute). Then use all the values to create static array: int ways[82] = { 0, 10, 45, 165, ..., 9, 1 }; int main() { int sum; cin >> sum; cout << ways[sum]; }
Edited by author 01.12.2016 23:44 |
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 |
Can anyone tell me the answer for s=10? | Grigor Gevorgian | 1353. Milliard Vasya's Function | 30 Nov 2015 22:18 | 4 |
I use a simple DP ,but WA#10.Give me some useful tests,pls. And I'd like to know if there is a better algo. |
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 :) |
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. |
test#11 to admins!!! | AndrKonin | 1353. Milliard Vasya's Function | 16 Aug 2015 03:17 | 2 |
what is 11 test? I think I checked everything possible variants? can you help me? It was replied to before. 75501. |
Can you give me some test | Nujarin | 1353. Milliard Vasya's Function | 23 Apr 2015 17:54 | 5 |
Cos My English is Bad I don't Understand this Problem PS. Thank you Here is tests 1 _ 10 2 _ 45 3 _ 165 5 _ 1287 6 _ 3003 11 -> 75501 15 -> 478731 20 -> 2714319 45 -> 40051495 Please provide some more tests who have passed the problem 30 - 22505751 40 - 45433800 50 - 25614639 |
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 |
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 |
To admins: Reduce Time limit | Georgi_georgiev | 1353. Milliard Vasya's Function | 25 Aug 2013 17:01 | 4 |
My source is consisted of 8 cycles from zero to nine and one counting and works for 0.356 or something like that. Yes, bruteforce algo with 8 cycles AC. :) But with 9 cycles got TL. Edited by author 14.07.2009 00:30 Why 8, not 9? Because 9th you can calculate. P.S. Yes, I'm necroposter XD Edited by author 25.08.2013 17:02 Edited by author 25.08.2013 17:02 |