Home > Applied Algorithms, Arrays, Language Specific > Append to Divide – ICPC 2011 Amritapuri Online Round

Append to Divide – ICPC 2011 Amritapuri Online Round

Problem Statement: Honeydukes’ Sweet Shop has donated buckets of Bertie Bott’s Every Flavor Beans (a kind of jelly bean) to the students of Hogwarts School of Witchcraft and Wizardry, one basket per House. But when the baskets (each labeled with the House number i) were delivered to the school, it was discovered that the number of sweets in each bucket were not exactly divisible by the number of students in that house A[i], and quarrels broke out about who got the extra sweets.
Harry Potter to the rescue! Harry suggested using magic to make sure that every bucket contained a number of sweets that were exactly divisible by the number of students in the corresponding House.
Can you tell us how many sweets were in the last bucket, given the way Harry’s spell worked:

Given the number of students A[i] in each of the N houses, we define the array B[0..N] as follows. Initialize B[0] = 1 and for i = 1 to N, set B[i] to the smallest integer obtained by appending one or more digits (0-9) to B[i-1] such that B[i] is divisible by A[i]. Find the value of B[N] modulo 1000000007.

Huh? Did you get the problem? If not, read through it again. It is pretty simple to understand what they want you to do. If you still can’t, here is an example:

For input 2, 3, 4 answer will be 1020. Why? Because:

A[1..3] = {2,3,4}, B[0..3] = {1, 10, 102, 1020}.

Hope you understand it now. (Call me up if you still don’t)

So how do we solve this? Well, here it is:

You start with 1 and start appending zeros. For each position i of B (starting with i>1), you check if the number formed is divisible by A[i-1] (Hence, starts with A[0]). If yes, this is the number you require for B[i]. If not, then find the modulus of the number formed with A[i-1], subtract this modulus from A[i-1], and add it to the number formed IFF the number of zeros added is less than or equal to the number of digits in the (A[i]-modulus) figure you obtained. Otherwise, add another zero to the end of the number formed earlier. Keep repeating the process and you’ll get the answer 🙂

Here is how this would work for the example specified above,

A[0..2]={2,3,4}, B[0] = 1

Now forming numbers for B[1],

appending 0 to B[0], we get 10, which is divisible by A[i-1] (2). Hence, B[1]=10

Now forming numbers for B[2],

appending 0 to B[1], we get 100, which leaves modulus = 1, And A[i]-mod=2. As number of digits (1) is less than or equal to the number of zeros added (1), add 2 to 100, which gives, B[2]=102

Similarly, for B[3]=1020. And hence the answer!

But oh wait! The question isn’t over. We had somewhat mistaken the limits assuming the answer would fit in “long long”. The limts were as follows,

1 <= T <= 10
1 <= N <= 1000
1 <= A[i] <= 1,000,000

If you think about it properly, your answer (before modulus 1000000007) can end up being more than 1000 digits long. Which will be difficult to handle in C/C++. Hence, we needed to use BigInteger to solve this. Which I did! 🙂

If you went through the solution properly, you would have understood it. 😉

PS: I can mail the JAVA code in BigInteger if someone wants. Leave a comment with your correct email-id in the field.

Advertisements
  1. IndianCoder
    October 24, 2011 at 12:12 am
    • October 24, 2011 at 9:00 am

      We did try that approach but somehow it was failing for some corner cases. Anyway, I guess we were in too much of a hurry and must have made some mistake while trying continuous mod. Cool! Thanks for pointing it out! 🙂

  2. avinash
    October 21, 2012 at 1:43 pm

    Its easy but how to apply it in C++, Is there any BigInteger Class??

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: