i got clue upto this could u verify
The total number of strings of length N is 2^N. Some of these are periodic.
Others are not. Let's call the number of periodic strings A(N), and the
number of non-periodic strings B(N). Then
A(N) + B(N) = 2^N
If we define strings of length 1 to be non-periodic, then
A(1) = 0
B(1) = 2
Let's assume now that N > 1. Then the set of periodic strings of length N
includes
strings that are periodic with a period shorter than N. However, this is
not the case for the set of non-periodic strings of length N.
The set of periodic strings of length N is made up of repetitions of
non-periodic strings of lengths that are divisors of n, including those of
length 1. In other words:
A(N) = sum(B(k) where k divides N and k < N)
For example:
A(6) = B(1) + B(2) + B(3)
= (2^1 - A(1)) + (2^2 - A(2)) + (2^3 - A(3))
= 2 + (4 - B(1)) + (8 - B(1))
= 2 + 2 + 6
= 10
So we now have a recurrence equation for the number of periodic and
non-periodic strings of length N.
Unfortunately, this doesn't help us that much to answer the actual question.
The question implies that Bob has received a specific string, and he wants
to know how many non-periodic strings differ by at most K bits from this
string. There are C(N,K) possible mutations of the received string that
could be the transmitted string. We need to subtract from this the number
of periodic strings in this set. How can we go about this?
First, we can use the observation that any periodic string is a repetition
of non-periodic strings. So, for each potential period k (divisor of N), we
look at the substrings of length k. If all strings are different from a
common string by no more than K bits combined, then this common string is
the basis for a periodic string and we should decrease the count by one. If
the minimum distance is d, and K - d > N/k, then we can flip individual
bits in each substring and still have a match, and we have to decrease our
count accordingly.
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
To view this discussion on the web visit
https://groups.google.com/d/msg/google-code/-/L0JeK4bIEyIJ.
For more options, visit https://groups.google.com/groups/opt_out.
