Kick Start

Round H 2019 -Kick Start

Elevanagram

Problem

It is a well known fact that a number is divisible by 11 if and only if the alternating sum of its digits is equal to 0 modulo 11. For example, 8174958 is a multiple of 11, since 8 - 1 + 7 - 4 + 9 - 5 + 8 = 22. Given a number that consists of digits from 1-9, can you rearrange the digits to create a number that is divisible by 11? Since the number might be quite large, you are given integers A1, A2, ..., A9. There are Ai digits i in the number, for all i.

Input

The first line of the input gives the number of test cases, T. T lines follow. Each line contains the nine integers A1, A2, ..., A9.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is YES if the digits can be rearranged to create a multiple of 11, and NO otherwise.

Limits

Time limit: 20 seconds per test set. Memory limit: 1GB. 1 ≤ T ≤ 100. 1 ≤ A1 + A2 + ... + A9.

set 1 (Visible)

0 ≤ Ai ≤ 20, for all i.

set 2 (Hidden)

0 ≤ Ai ≤ 109, for all i.

Sample Input

    6
    0 0 2 0 0 1 0 0 0
    0 0 0 0 0 0 0 0 12
    0 0 0 0 2 0 1 1 0
    3 1 1 1 0 0 0 0 0
    3 0 0 0 0 0 3 0 2
    0 0 0 0 0 0 0 1 0

Sample Output

    Case #1: YES
    Case #2: YES 
    Case #3: NO 
    Case #4: YES 
    Case #5: YES 
    Case #6: NO

In Sample Case #1, the digits are 336, which can be rearranged to 363. This is a multiple of 11 since 3 - 6 + 3 = 0.
In Sample Case #2, the digits are 999999999999, which is already a multiple of 11, since 9 - 9 + 9 - 9 + ... - 9 = 0.
In Sample Case #3, the digits are 5578, which cannot be rearranged to form a multiple of 11.
In Sample Case #4, the digits are 111234, which can be rearranged to 142131. This is a multiple of 11 since 1 - 4 + 2 - 1 + 3 - 1 = 0.
In Sample Case #5, the digits are 11177799, which can be rearranged to 19191777. This is a multiple of 11 since 1 - 9 + 1 - 9 + 1 - 7 + 7 - 7 = -22 (which is 0 modulo 11).
In Sample Case #6, the only digit is 8, which cannot be rearranged to form a multiple of 11.

Analysis

Test Set 1

We need to divide each digits to two partitions: positive partition and negative partition, where positive partition means the digit is on the odd index (be calculated as add), and negative partition means the digit is in the even index (be calculated as minus).

We can use dynamic programming to solve test set 1. Let dp[i][j][k] denote if it is possible to achieve the state that when we are considering digits 1, 2, ... i, the current number of digits in the positive partition is j and the current sum modulo 11 is k. Then for each digit i, we can put 0, 1, ..., Ai digits into the positive partition, and calculate if the current state is possible. We want to calculate dp[9][sum(A)/2][0], where sum(A) means the total sum of all elements in array A.

The time complexity is O(9 * sum(A) * 11 * max(A)), which fits the time limit for test case 1. Here max(A) means the maximum of all elements in array A.

Test Set 2

Assume the positive number of digits i is Pi, and negative number of digits i is Ai - Pi. Then, we will have the following three equations:

(1) Σ Pi = ceil(sum(A) / 2) (2) Σ i × (Pi - (Ai - Pi)) % 11 = 0 (3) 0 ≤ Pi ≤ Ai

In order to solve this, initially we can put half the number of each digits to be in positive partition (e.g. Pi = Ai / 2, take care of odd numbers), and then try to adjust each Pi to satisfy equation (2). For each i, we can adjust its Pi from -Ai / 2 to Ai / 2.

We can prove the two following conclusions:

1. If there are at least two numbers of Ai ≥ 10, then the solution must exist.

This is very easy to prove. We can only adjust these two digits from -5 to 5, and each adjustment will result in a different remain value of modulo 11. Thus, we will get 0 finally.

2. If there are at least three numbers of Ai ≥ 6, then the solution must exist.

To prove this, we can prove that:

For any 1 ≤ i < j < k ≤ 9, 0 ≤ r ≤ 10, the following equations: (1) (i * x1 + j * x2 + k * x3) % 11 = r (2) x1 + x2 + x3 = 0 (3) -3 ≤ xi ≤ 3 will have a valid solution.

This can be proved by iterating all possible situations, where the total number is 9C3 * 11 * 7 * 7 = 45276, quite small.

According to these two conclusions, if there are at least two numbers ≥ 10 or at least three numbers ≥ 6, we can return YES immediately. Otherwise, there are at most one value ≥ 10, and at most two values ≥ 6, we can calculate all possible situations, where in the worst case time complexity is O(67 * 10) = O(2799360) which fits the time limit for test case 2.

google - kick start