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.

Slick solution! Good job 🙂

LikeLike