11392 - Binary*3 Type Multiple

All about problems in Volume 113. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

11392 - Binary*3 Type Multiple

Post by sclo » Mon Jan 14, 2008 11:39 am

I don't understand why my O(n) algorithm get TLE. Is there any faster way to solve it?

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Mon Jan 14, 2008 2:18 pm

I got AC with 2.65~ sec using O(n) algorithm.

-----
Rio

tanaeem
New poster
Posts: 26
Joined: Mon Mar 12, 2007 6:58 pm
Location: BUET
Contact:

Post by tanaeem » Tue Jan 15, 2008 5:52 am

I have got AC in 1.960 sec.
My algorithm is order of no. of 3 (most obvious one)

User avatar
CMG
New poster
Posts: 37
Joined: Sat Dec 08, 2007 5:01 am
Location: ...

Post by CMG » Wed Jan 16, 2008 7:38 am

O(n)? I don't see any relationship between the numbers and their answers, other than the fact that at some point when you reach an odd prime number that hasn't been used in the factors of the previous answers its answer will be p-1 p-1 0. What am I missing that makes this problem easy to calculate?

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Thu Jan 17, 2008 3:52 am

Heres my approach:
For k=14, the answer is 3333330.

Code: Select all

3333330 = 3*(10^6+...+10^1)
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^(b-1)+...+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

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Thu Jan 17, 2008 9:38 am

I did similar approach, except it doesn't matter if k is divisible by 3 or not. I basically compute 333...3 mod k for each length

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am

Post by hamedv » Sat Jan 19, 2008 1:53 pm

problem 10127 is another version of this problem. you can code it in less than 15 lines. in this problem numbers can be multiple of 2 or 5 because you can add zeros to the end of your number.

crackerwang
New poster
Posts: 10
Joined: Sun Jan 20, 2008 8:19 am

Post by crackerwang » Fri Jan 25, 2008 5:55 pm

but i want to know is any num which can'ti div by 2 or 5 have a mutiple like 111..1111

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am

Post by hamedv » Sat Jan 26, 2008 12:14 pm

if a number is a multiple of 2 it's first digit must be 0 or 2 or 4 or 6 or 8.
and if a number is a multiple of 5 it's first digit must be 0 or 5.
due this a number which is like this "11..11" is not a multiple of 2 or 5.

User avatar
fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:

What's the output for this

Post by fh » Sun Jan 27, 2008 7:41 am

Can somebody check whether my output is correct?
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://felix-halim.net/uva/hunting/
-----------------------
Felix Halim

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Sun Jan 27, 2008 12:26 pm

My AC code got same output as yours.

-----
Rio

User avatar
fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:

I'm using GCD in

Post by fh » Sun Jan 27, 2008 1:58 pm

The problem is to find (a,b) such that 0<=a<=b and 10^b+10^(b-1)+...+10^a is divisible k.
This could be done by O(n) algorithm.
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?
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim

greve
New poster
Posts: 27
Joined: Tue May 29, 2007 8:52 pm
Contact:

Post by greve » Sun Jan 27, 2008 2:17 pm

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)?
For help with problems, visit http://www.uvatoolkit.com/

User avatar
fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:

Post by fh » Sun Jan 27, 2008 2:40 pm

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)?
Awesome.. I never thought of this elegant solution. Thanks greve :D
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim

f74956227
New poster
Posts: 37
Joined: Sun Jan 27, 2008 1:50 am
Location: Taiwan
Contact:

Re: 11392 - Binary*3 Type Multiple

Post by f74956227 » Sun Jan 11, 2009 5:13 pm

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 ?? :roll:
electron

Post Reply

Return to “Volume 113 (11300-11399)”