When time is short - Codeforces

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

UPD: Huge thanks to P_Nyagolov and halyavin for helping — finally solved it! Hope this thread can be useful to someone in the future.

Hello, Codeforces! I just want to thank all of you guyz for this wonderful place uniting these wonderful people. Place where you can improve yourself and if you having any troubles you won't be left alone. Thank you, community! Now to the topic.

I ask you to help me improve my algorithm, which gives TLE.

Here is the problem: For given N (1<=N<=1000) find the smallest positive integer with the sum of digits N which is divided by N. Samples: - input: 1; output: 1 - input: 10; output: 190 Time limit: 2sec.

My solution I used DP approach: dp[sum][rem] — smallest positive integer with the sum of digits sum and remainder after division by N is rem. Now for every integer dp[sum][rem] we iterate through all possible digits and add them to the end. With obtained number we try to improve dp[sum+lastDigit][(rem*10+lastDigit)%N]. Answer is dp[N][0].

But this solution is too slow and runs more than 4 seconds on max test.

Any tips will be appreciated.

UPD: How I solved the problem: instead of storing integers as strings, I stored length and first digit. Then went backwards as halyavin suggested. Here is my code

N = 11 [ 0] [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 0] 0 - - - - - - - - - - [ 1] - 1 - - - - - - - - 10 [ 2] 11 - 2 - - - - - - 20 - [ 3] - 12 - 3 - - - - 30 - 21 [ 4] 22 - 13 - 4 - - 40 - 31 - [ 5] - 23 - 14 - 5 50 - 41 - 32 [ 6] 33 - 24 - 15 60 6 51 - 42 - [ 7] - 34 - 25 70 16 61 7 52 - 43 [ 8] 44 - 35 80 26 71 17 62 8 53 - [ 9] - 45 90 36 81 27 72 18 63 9 54 [ 10] 55 1090 46 91 37 82 28 73 19 64 109 [ 11] 209 56 1091 47 92 38 83 29 74 119 65 [ 0] [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 0] 0 - - - - - - - - - - [ 1] - 1 - - - - - - - - 1. [ 2] 1. - 2 - - - - - - 2. - [ 3] - 1. - 3 - - - - 3. - 2. [ 4] 2. - 1. - 4 - - 4. - 3. - [ 5] - 2. - 1. - 5 5. - 4. - 3. [ 6] 3. - 2. - 1. 6. 6 5. - 4. - [ 7] - 3. - 2. 7. 1. 6. 7 5. - 4. [ 8] 4. - 3. 8. 2. 7. 1. 6. 8 5. - [ 9] - 4. 9. 3. 8. 2. 7. 1. 6. 9 5. [ 10] 5. 1... 4. 9. 3. 8. 2. 7. 1. 6. 1.. [ 11] 2.. 5. 1... 4. 9. 3. 8. 2. 7. 1.. 6.

Comments (11)

Write comment?

P_Nyagolov

9 years ago, # |

You don't need strings, that makes your solution slow. Let dp[sum][rem] is the length (not the number itself, only its length) of the shortest number that can be obtained. To restore the number, we need an extra table best[sum][rem] which gives us the smallest digit such that the minimum length is obtained. After filling both tables, it's easy to restore the number. I am almost sure that I have solved a similar problem on SPOJ so if you don't understand my explanation I can try to find it and give you my code :)

→ Reply

micklepru

9 years ago, # ^ |

← Rev. 2 →

Thank you for the hint, i understood it. However, it could be that length of both numbers is same, but they are different. And it happens quite a few times. For example N=10, then we update 360 values with integers of same length. Like 219->129, 218->128, 417->327, ...

So it seems like we do need to save whole number

That's why we store the table best[sum][rem] which gives us the smallest digit for which we obtain the minimum length, that is, we store the minimum first (leftmost) digit that obtains the minimum length :)

Problem: http://www.spoj.com/problems/INUMBER/
My BFS implementation, it follows the same idea: http://ideone.com/6E3F3J

I've been thinking about this and now I'm completely lost. Can you tell in more details what is table best and how are we recover result?

If we save only length and first digit how to distinguish exact number? For example len=3,first=2 may be 217 or 271 or something else

You understood how to fill the table "best". Let's talk about restoring the number. After filling the dp and best tables, we can restore it in the following way:

Let the current state be (0,0), I mean sum=0 and remainder=0 so no digits were added. We know that the best. We know that the first digit of the minimum number is D=best[sum][remainder]. Let's print D and do sum+=D, remainder=(remainder*10+D)%n. Then do the same, print D'=best[sum][remainder] and do sum+=D' and remainder=(remainder*10+D')%n. You will stop the restoration when sum==n and remainder==0. That's what the following piece of code does:

sum=0;
remainder=0;
while(sum<n || remainder!=0) {
  p=best[code[sum][remainder]];
  printf("%d", p);
  sum+=p;
  remainder*=10;
  remainder+=p;
  remainder%=n;
}
printf("\n");

Genuinely thank you for your help even though I am bothering you too much. But after your last reply, I am even more confused now. I think I completely misunderstood two tables idea. I believe the best way to understand is a real example.

You said that for every state (sum,rem) we save not a integer, but first digit and length. So we have something like "2.." instead of "209".

Consider next tables. First is when we are holding whole number, second — only first digit and length.

For correct tables display i'll create new comment, because this area is too narrow.

Mhammad1

Could you provide the link for the problem?

The problem that I started with wasn't from OJ. However, P_Nyagolov gave a link to almost identical problem: Link

Rows represent rem, columns — sum. Integer in cell — smallest possible positive integer with sum of digits sum and remainder rem modulo N.

Our answer is "2..". How do we distinguish exactly "209"??

The problem in this case is that you cannot find the remainder of the previous state so you need to fill the tables from [N,0] to [0,0] like I do in BFS. After that it's quite easy to restore the number. If you can rewrite the table, I can explain how it happens. Now I am solving some problems from JBOI so I cannot make the table right now :)

halyavin

You move from cell (11, 0) to cell (11 - 2, (0 - 2 * 100) (mod 11)) = (9, 9). Then you see that optimal length is less than 2 there, so you add "09" to the answer (0 in the answer doesn't change the cell in the table) and move from (9, 9) to (9 - 9, 9 - 9 * 1(mod 11)) = (0, 0). (0, 0) means we are done and the answer is "209". All you need is to precalculate remainders of 10^k by modulo N for k from 0 to the length of the result minus 1.

Another example, just in case. (11, 2) -> (11 - 1, (2 - 1 * 1000)(mod 11)) = (10, 3). (10, 3) -> (10 - 9, (3 - 9 * 10)(mod 11)) = (1, 1). (1, 1) -> (1 - 1, (1 - 1) (mod 11)) = (0,0). Final answer is "1" + "09" + "1" = "1091".

micklepru's blog