Hi all,
after reviewing the analysis of the problem on the website, and having had my
aha! moment that if you have AB BC CD DE that gcd(AB,BC) = B, I thought I would
give my own analysis, because the one from Google seems a bit too complicated.
All the Runtime Errors seem to stem from the fact that there are a number of
special cases. These cases all have to do with the observation that the initial
string of characters could either be:
1- the same (ie AAAAAAAA....B)
2- alternating, even length: ABAB....AB C
3- alternating, odd length: ABAB....A C
4- all different: ABC (which is case 2, without the leading ABABAB...)
For 1, this would lead to AA (A^2) as values until the first B is encountered.
For 2 and 3 this would lead to AB BA AB BA (etc.) as the numbers in the
encrypted message, and these numbers in the encrypted message therefore would
also be the same.
For 4, this could be considered the normal case.
We can observe that once we have determined what scenario we have to entertain,
we can determine A, B and C. Once that's done we can just move forward through
the encrypted message (even starting from the first position, at the cost of a
few additional multiplications)
Now, let us say that the first set of two consecutive different numbers is at
some position P. Let's take the first number at P to be P1, and the one next to
it P2 (as we have at least 25 different prime multiplications, these are
guaranteed to exist)
Let's take the regular case first, two different products of prime, right at
the start:
So: AB BC. It can be observed that the gcd(AB,BC) will have B as the common
factor.
b = gcd(P1,P2), a = P1 / b;
We cannot use the same formula for case 1-3, because we don't know what (a) and
(b) represent just yet.. Take the first product at position 0, let's call that
one P0.
1- for AAAA....B we end up with P0 = AA, P1=AA, P2=AB
So, the gcd(P1,P2) -> gcd(AA,AB) -> A. DIV(P0,A) -> A. However, we can test
whether P0 = A*A and so we know that we have successfully determined the first
prime.
2- ABABAB...ABC: We observe that C is at an odd position in the string.
gcd(P1,P2) -> gcd(AB,BC) -> B. DIV(P0,B) -> A. So, if we are not at the
starting position, we can leave things as they are as in case 4, we have found
A, if we know BC is at an even position.
3- ABAB....ABAC. C is at an even position. So, AC will be at an odd position.
gcd(P1,P2) -> gcd(BA,AC) -> A. DIV(PO,A) -> B. If we know the second one is at
an even position, we know we have to swap (a) and (b) as calculated above.
Once we successfully determine A, we have essentially bootstrapped the process.
We can store A in a binary tree, store it also as the first letter (it is of
course not necessarily the smallest, but we do not know that yet) and continue
the process:
The regular decoding is to just take the last prime calculated (ie A) and:
divide the current position's product by the last prime, yielding a new prime.
Store the prime in the binary tree, add the prime to the decrypted message.
(Note: once you have 26 primes in your binary tree, you could optimize the
process by assigning at that time each prime a letter according to the order in
the binary tree, decode everything stored up to that point, throw away that
part of the encrypted message and just decode on the fly. This should reduce
the memory footprint significantly, especially when using large primes. Of
course, the worst case scenario would be that you have a humongous plaintext of
A..........BCDEF..Z)
Once done, assign the primes a rank according to the order in the tree.
Then decode the message by looking up each value in the encrypted message, and
write it to the output.
In Java, the bootstrapping part of this process would be:
private BigInteger bootstrap() {
int startPos = 0;
boolean flip = false;
for (int i = 0; i < m_encryptedMessage.size(); ++i)
{
if
(!m_encryptedMessage.get(i).equals(m_encryptedMessage.get(i + 1)))
{
startPos = i; break;
}
flip = !flip;
}
// AAAAAA.....AAB : gcd(AA, AB) -> A : DIV(AA,A) -> A; A*A = eM(0)
// ABABAB.....ABC : gcd(AB, BC) -> B : DIV(AB,B) -> A; (flip = false)
// ABABAB.....BAC : gcd(BA, AC) -> A : DIV(BA,A) -> B; (flip = true)
BigInteger p1 = m_encryptedMessage.get(startPos);
BigInteger p2 = m_encryptedMessage.get(startPos + 1);
BigInteger b = p1.gcd(p2);
BigInteger a = p1.divide(b);
if (startPos != 0) // irregular case
{
BigInteger p0 = m_encryptedMessage.get(0);
BigInteger a_square = a.multiply(a);
if (flip && (!a_square.equals(p0))) // case 3, switch them around
{
BigInteger temp = b;
b = a;
a = temp;
}
}
BigInteger currentPrime = a;
m_primes.put(currentPrime, 0);
m_primesUsed.add(currentPrime);
return currentPrime;
}
So, this yields A to the calling function, which then becomes simply:
public void calculateSolution() {
BigInteger bootstrapPrime = bootstrap(); // find first and second prime
BigInteger lastPrime = bootstrapPrime;
for (BigInteger currentProduct : m_encryptedMessage) {
BigInteger newPrime = currentProduct.divide(lastPrime);
m_primes.put(newPrime, 0);
m_primesUsed.add(newPrime);
lastPrime = newPrime;
}
int count = 0;
for (Map.Entry<BigInteger,Integer> mapUpdater : m_primes.entrySet()) {
mapUpdater.setValue(count);
++count;
}
}
For completeness, these are the datastructures used:
private ArrayList<BigInteger> m_encryptedMessage = new ArrayList<>();
private ArrayList<BigInteger> m_primesUsed = new ArrayList<>();
private TreeMap<BigInteger, Integer> m_primes = new TreeMap<>();
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/0411a25e-21ff-458b-be41-e9bfad32733c%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
