Good Sets

ACM ICPC India Regionals Online Preliminary round got over last week. Our team ‘Dashwood’ (named after the password used by Harold Finch in the TV series Person of Interest ), we were able to solve 5 questions out of the 7 questions.

The 5 questions which we could solve were all relatively easy compared to the other two.

Link to the contest here.

Out of the 5 questions which we solved one was very interesting to solve, so here’s a blog explaining how I did it.

It was basically a Dynamic Programming problem.

Read the question here.

Here is the code in C++

The inp[] will contain 1 at the indices corresponding to the input numbers.

Now we iterate through the array inp and if an index i has 1.

We update dp[i] by

dp[i] = (dp[i] + 1) % MOD;

Then we update the dp array at all the indices which are the multiples of i .

dp[j] = (dp[j] + (dp[i] + 1)) % MOD;

where j loops over all the multiples of i.

and with each update of the dp array we increment the variable sum by the same amount.

Now after all the updates sum will contain the final answer.

Why this works?

For example let the given array be {2, 3, 6, 12}.

Now we take {12} and we have to find the number of ways we can append new arrays to it such that 12 is near to its factor.

So we can append 6 or 3 or 2 with {12} or not append anything. We can append not just the individual numbers but also the arrays which can be formed with those numbers.

So for {6} we can append 2 or 3 or not append anything.

{2, 6}, {3, 6}, {6}

So dp[6] contains 3

For 2 and 3 we cannot append any numbers.

{2}, {3}

So dp[2] = dp[3] = 1

So we can append {2, 6}, {3, 6}, {6}, {2}, {3} to {12}

So the number of ways we can form subarrays with 12 is

dp[6] + dp[3] + dp[2]

which is 5.

The final answer is the sum of number of ways you can make arrays ending with {2}, {3}, {6} and {12}.

The variable sum has the total sum of the dp[] array and hence the final answer.

 

Advertisements

One thought on “Good Sets

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s