Editorial of MindCoding 2016 Round 3 (Div. 2)

50 - Gaps

100 - Panic Attacks

250 - Byte Trains

    1 #!/usr/bin/python3
    2 
    3 s = input()
    4 theirVersion = ''
    5 myVersion = ''
    6 
    7 for x in [s[i:i+8] for i in range(0, len(s), 8)]:
    8     if x[0] == '1':
    9         theirVersion += '1' + '0' * (len(x) - len(x.rstrip('0')))
   10     myVersion += x[0]
   11 
   12 print(['No', 'Yes'][theirVersion == myVersion])

500 - Odd

Solution by Gabriel-Robert Inelus

In order to solve the problem we have to compute the digit sum of all numbers in the closed interval [0, x]. For this, we need to precompute the digit sum, sum[n], on closed intervals [0, 99…9] where 9 occurs n times.

Writing the first few terms of the sum on intervals [0, 9], [0, 99], [0, 999] we observe that the digit sum is: sum[i] = i * 10i-1 * 45.

Now, to get the digit sum of the numbers in the closed interval [a, b], we firstly need to compute a function F, where F(x) is the digit sum on interval [0, x]. The first useful observation is that for a given digit d which appears on position p (right to left in the number, 1-indexed), the digit sum[p-1] appears exactly d times.

For the sake of an example, digit 5 in 89959914, adds the sum [0, 9999] 5 times to the digit sum, also digit 8 adds sum[7] exactly 8 times. On a smaller example: 378, digit 3 adds the sum [0, 99] 3 times: 0[0, 99], 1[0, 99] and 2[0, 99].

The next useful observation is that a given digit d on position p (right to left, 1-indexed) contributes with d*(d-1)/2 * 10p-1 to the sum. For the sake of another example, digit 3 of 378, contributes in this way: 0 - 100 times, 1 - 100 times, and 2 - 100 times. This is 100 * (3*2/2).

Currently, we took into consideration the [0, 99…9] sums (which look like suffixes of numbers), and the current digit. Now, we have to take into consideration the prefix of the number which also contributes to the sum. The digit sum of the prefix (without the current position p) will be repeated d * 10p-1 times. Thus, we need to know:

  • nrdig - the number of digits
  • prefix_sum[p] - the prefix sum of the leftmost p digits
  • sum[n] which is the digit sum on interval [0, 999…9] where 9 repeats n times
  • digit[k] - kth digit right to left

The final formula for F(x) is:

Σ(digit[k]*sum[k-1] + digit[k]*(digit[k]-1)/2 * 10k-1 + prefix_sum[k+1] * digit[k] * 10k-1) for k = nrdig to 1.

Note that the three terms of the sum corespond to the suffix contribution (all the [0, 999…9] digit sums), the current digit's contribution and the contribution of the current prefix. In the end, we have to add the digit sum of the actual number as we added everything up to the number -1.

Now that we have the function F(x) which returns the digit sum on any interval [0, x], we have to use it in a smart way to obtain the digit sum on the interval [a, b]. So, the digit sum on interval [a, b] is F(b) - F(a-1) given that a is positive, otherwise it is simply F(b).

We now have all the tools in order to solve the problem. The relation between the odd-number digit sum and the digit sum of all the numbers in interval [a, b] is pretty easy. First of all, we make the interval of the shape [newA, newB] such that newA is even and newB is odd, by adding 1 to a in case it is odd and subtracting 1 to b in case it is even. Now, for each odd number in the interval [a, b] there exists exactly one even number, whose digit sum is 1 less than the respective odd number. Thus, the digit sum of odd numbers in the adjusted interval is the digit sum of all numbers in the adjusted interval, plus the number of odd numbers (which is (newB-newA+1)/2), divided by two. In case the original a was odd and we increased it by one unit, we need to add digitsum(original_a) to the result.

Finally, the solution is: (Interval_sum(a, b) + (b-a+1)/2)/2 and we add the digit sum of (a-1) in case it was originally an odd number and we added 1 to make it even. Note that here, a and b are the modified ones such that a is even and b is odd (so we always have a previous even number to all the odd ones - which has digit sum 1 less, as previously discussed) and Interval_sum(a, b) is F(b) - F(a-1) in case a is positive, otherwise if a is 0 the result is F(b).

Questions?

Sponsors Gold