11392  Binary*3 Type Multiple
Moderator: Board moderators
11392  Binary*3 Type Multiple
I don't understand why my O(n) algorithm get TLE. Is there any faster way to solve it?
Heres my approach:
For k=14, the answer is 3333330.
14 does not have factor 3, so it means 10^6+...+10^1 is divisible by 14.
If k doesn't have factor 3, the problem is to find (a,b) such that 0<=a<=b and 10^b+10^(b1)+...+10^a is divisible k.
This could be done by O(n) algorithm.
If k is divisible by 3, divide it by 3 and do the same thing.

Rio
For k=14, the answer is 3333330.
Code: Select all
3333330 = 3*(10^6+...+10^1)
If k doesn't have factor 3, the problem is to find (a,b) such that 0<=a<=b and 10^b+10^(b1)+...+10^a is divisible k.
This could be done by O(n) algorithm.
If k is divisible by 3, divide it by 3 and do the same thing.

Rio

 New poster
 Posts: 10
 Joined: Sun Jan 20, 2008 8:19 am
What's the output for this
Can somebody check whether my output is correct?
Or is there any tricky input?
Or is there any tricky input?
Code: Select all
Input:
1
2
3
4
5
6
7
8
9
10
11
12
13
236773
42610
207363
428950
718729
958356
227092
63702
922718
84511
298077
803248
249764
882133
249776
858939
723076
244080
954760
335073
Code: Select all
Output:
1 1 0
2 1 1
1 1 0
3 1 2
2 1 1
2 1 1
6 6 0
4 1 3
3 3 0
2 1 1
2 2 0
3 1 2
6 6 0
39462 39462 0
4261 4260 1
2652 2652 0
2048 2046 2
16206 16206 0
11408 11406 2
14195 14193 2
10615 10614 1
230680 230679 1
12072 12072 0
22926 22926 0
8224 8220 4
7346 7344 2
126018 126018 0
7660 7656 4
11792 11792 0
2757 2755 2
1012 1008 4
23871 23868 3
3660 3660 0
Visit my script to hunt UVA problem here:
http://felixhalim.net/uva/hunting/

Felix Halim
http://felixhalim.net/uva/hunting/

Felix Halim
I'm using GCD in
My algo is O(L + K) where L is the length of the multiple in the output. K iteration is needed to initalize the array. I use GCD in each iteration of L. I got TLE. How to better than this?The problem is to find (a,b) such that 0<=a<=b and 10^b+10^(b1)+...+10^a is divisible k.
This could be done by O(n) algorithm.
Visit my script to hunt UVA problem here:
http://felixhalim.net/uva/hunting/

Felix Halim
http://felixhalim.net/uva/hunting/

Felix Halim
First of all it suffices to look at the numbers 3,33,333, 3333 etc., since any number ending in some number of 0s can be expressed as the difference of two of these numbers with no 0s, ie. 333  33 = 300.
Hint: If you start marking the remainders you get mod K from this sequence, what happens when you get a remainder that you have seen before (and why does this prove that a solution always exists)?
Hint: If you start marking the remainders you get mod K from this sequence, what happens when you get a remainder that you have seen before (and why does this prove that a solution always exists)?
For help with problems, visit http://www.uvatoolkit.com/
Awesome.. I never thought of this elegant solution. Thanks greveFirst of all it suffices to look at the numbers 3,33,333, 3333 etc., since any number ending in some number of 0s can be expressed as the difference of two of these numbers with no 0s, ie. 333  33 = 300.
Hint: If you start marking the remainders you get mod K from this sequence, what happens when you get a remainder that you have seen before (and why does this prove that a solution always exists)?
Visit my script to hunt UVA problem here:
http://felixhalim.net/uva/hunting/

Felix Halim
http://felixhalim.net/uva/hunting/

Felix Halim
Re: 11392  Binary*3 Type Multiple
Hi! I got AC within 2.XX sec by O(n), but i see that there are someone who got AC within only 1 sec
is there a O(1) algorithm ??
is there a O(1) algorithm ??
electron