Editorial of MindCoding 2016 Round 3 (Div. 1)

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).

1000 - Journey

Solution by Gabriel-Robert Inelus

In order to solve the problem we must imagine that we are in the middle of an infinite grid at coordinates (0, 0). Hence, at any step we can move from the current position (i, j) to:

  • (i+1, j)
  • (i-1, j)
  • (i, j+1)
  • (i, j-1)
as long as we don't pass twice through a position which has been visited before in the current path.

Thus, we will use a backtracking algorithm which generates all these solutions; however, there will be repetitions which must be taken care of.

The actual problem is to find a method to determine whether or not two paths have the same "shape" given that we are allowed to apply some translation operations to them.

The key idea is that we can find an extreme point on the border of the shapes. A good choice can be to find the element (x, y) of a path, which has the smallest x coordinate and, in case of equality, the smallest y coordinate. Then, we normalize the shape by translating it (originally centered at (x, y)) to (0, 0) by subtracting (x, y) (by components) from all the elements of the current path. After this, we will be left with a normalized path which can be stored in a hash map (for instance, we can use STL map to store some vectors, or unordered_map to store some strings).

The result is the size of the hash map.

Questions?

Sponsors Gold