ZIO12002 - Editorial

editorial
, , , , ,
1

Editorialist: Raj Shah

DIFFICULTY: EASY-MEDIUM

Problem Statement: ZIO 2012 Problem 2

PREREQUISITES: Basic Mathematics, Digit Dynamic Programming

PROBLEM:

A toy set contains blocks showing the numbers from 1 to 9.There is an infinite number of blocks showing each number and blocks showing the same number are indistinguishable. We want to examine the number of different ways of arranging the blocks in a sequence so that the displayed numbers add up to a fixed sum. For example, suppose the sum is 4. There are 8 different arrangements:

  • 1 1 1 1
  • 1 1 2
  • 1 2 1
  • 1 3
  • 2 1 1
  • 2 2
  • 3 1
  • 4

This is called an arrangement in the dictionary order.
If S=4 and K=5 then the answer would be 2 1 1 as you can see.

Ways to Sum to N using numbers 1 to 9:

There can be 1 to 9 in the first position for any arrangement
You have to make the sum of N-i with rest of the digits in the arrangement
Therefore the number of ways summing up to N will be sum of the number of ways to make N-i where i goes from 1 to 9
Below is the pseudocode for it:

countWays(N):

  • Declare and initialize count[N + 1] = {0}
  • count[0] = 1
  • for i = 1 to N
    • for j = 1 to 9
      • if i >= j : count[i] += count[i -j]
  • return count[N]

QUICK EXPLANATION:

  • S = 4 and K = 5, and say the problem is defined as (S, K)
  • Let’s say the first number in the combination will be i (i can be in 1 to 9).
  • We have to make S - i from the rest of the number
  • Now let’s say there are N ways to do that, where N = countWays(S-i)
  • There are two possible options now:
  1. N < K
    • So all the possible arrangements starting from a number i comes before the Kth arrangement.
    • So you go onto next number and deduct N from K
    • And the problem reduces to f(S, K-N)
  2. N >=K
    • So the desired Kth arrangement resides between this set of arrangements where it is started from a number i
    • So you fixed the first number i and problem reduces to f(S-i, K)
    • The final solution will be [i, Arrangement from f(S-i, K)]

SOLUTIONS:

  1. S = 9 , K = 156
i S N = count[S-i] K Condition
1 9 128 156 N<K
2 9 64 28 N>=K
1 7 32 28 N>=K
1 6 16 28 N<K
2 6 8 12 N<K
3 6 4 4 N>=K
1 3 2 4 N<K
2 3 1 2 N<K
3 3 1 1 N>=K

Final Answer = [2 1 3 3]

7 Likes
2

I solved this paper. I agree with solutions for Q1,3,4 and 2(a) but for 2(b) and 2(c), I got different answers: 341111 (instead of 34112 which I think is 882nd number) and 2115131 (instead of 211721 which I think is 4603rd number).

3

Can you plz show the workings of 2b and 2c, because your solution did not work in my case