Editorial for COCI '15 Contest 6 #6 San
Submitting an official solution before solving the problem yourself is a bannable offence.
Let denote the number of occurrences of the number
in the table. We can (not in an efficient way) calculate it using the following algorithm for each
from
to
:
for x from 1 to N:
tab[x] = tab[x] + 1
tab[x + rev(x)] = tab[x + rev(x)] + tab[x]
This algorithm is linear, but can be up to
so it is not efficient enough. It is crucial to notice that the amount of numbers for which
is very small. Let's denote the number of different numbers
such that
as
. Notice that
if and only if
. Let's denote the array of numbers consisting of all the numbers for which
as
and sort it ascendingly. The values of
for these numbers can be calculated using the following algorithm:
for each x in S:
tab[x] = tab[x] + cnt[x]
tab[x + rev(x)] = tab[x + rev(x)] + tab[x]
This algorithm consists of loop iterations. It is crucial to notice that the amount of numbers in set
is relatively small (only a couple of millions) so the upper algorithm is efficient enough in order to calculate the values
for each
for which the value is larger than
. For each other
it holds
, so now we actually have the value
calculated for each
, which enables us to efficiently answer queries (using partial sums of the array tab). Notice that the indices in the array
are very big, but we don't need the whole array so we will actually store it in a map.
We are left to calculate the values of for all numbers. We will recursively find all numbers
and the values
for each
for which the value is larger than
. Let's see what happens when we add a
-digit number with itself, only in reverse:
a1 a2 a3 a4 a5 a6
+ a6 a5 a4 a3 a2 a1
-----------------------------------------
c0 b1+c1 b2+c2 b3+c3 b3+c4 b2+c5 b1
Here are
or
and denote the carrying digits,
,
and
.
The values could be determined so that we fix the digits
in all possible ways, but there are a lot of combinations for that. Another approach would be to determine
and
in all possible ways (therefore the sum is uniquely determined) and calculate how many different selections of
results in exactly
and
. How can we do this? We will use a recursive function
gen
which takes 4 parameters, their meanings described in the following list:
pos
means we are currently determiningc1
means thatis equal to
c2
means thatis equal to
num
is the value of the current part of the sum
Here is the pseudocode for function gen
:
gen(pos, c1, c2, num):
if pos = 4:
(we have determined the whole sum and the number of ways to obtain it)
if c1 != c2 return
(c1 and c2 must be equal because they both represent c3)
increase cnt[num] by 1 and return
for pairs of digits (x1, x2):
(x1 and x2 determine b_pos, we are determining digits pos and 6-pos+1 of num)
if c1 = 1 and x1+x2 < 10 continue
if c1 = 0 and x1+x2 >= 10 continue
bb = (x1 + x2) % 10
nnum = num
set digit 6-pos+1 of nnum to bb + c2
set digit pos of nnum to bb + 1 and call
gen(pos+1, 1, x1+x2 >= 10, nnum)
(c1 = 1 denotes that we want the carry digit)
set digit pos of nnum to bb and call
gen(pos+1, 0, x1+x2 >= 10, nnum)
(c1 = 0 denotes that there is no carry)
The upper approach can be generalized for an arbitrary number of digits. The upper recursion for a number of length performs approximately
operations, which is too slow for all points. It is crucial to note that we don't need to iterate over all pairs of digits, because it is sufficient to iterate over all possible sums and for each sum know how many ways there is to obtain it. Then we perform approximately
operations, which is fast enough for all points. We leave the details as an exercise to the reader.
Comments