Hi Ronald, I also have similar complaints about editorial, but it's basically because I am used to read research papers where they specify problem (in this case, the problem statement itself), existing approach (what others have done) and what are short comings, followed by their approach with a big why about their approach. But again, my lack of understanding of competitive programming could be a reason for not understanding these editorials. I have implemented the same algorithm (unfortunately, I could not solve it during contest) in Haskell [1].
callRest :: Integer -> [Integer] -> [Integer] callRest prime [] = [prime] callRest prime (x : xs) = prime : callRest (div x prime) xs recoverPrime :: [Integer] -> [Integer] -> [Integer] recoverPrime (x : y : xs) acc | x == y = recoverPrime (y : xs) (x : acc) | otherwise = ret ++ callRest sprime (y : xs) where sprime = gcd x y fprime = div x sprime ret = reverse . callRest fprime $ acc Best, Mukesh [1] https://github.com/mukeshtiwari/Topcoder/blob/master/Codejam/Crytpograms.hs#L7-L18 On Tue, Apr 9, 2019 at 3:33 AM Ronald van Loon <[email protected]> wrote: > > 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. -- 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/CAFHZvE_YhYYiKa_a_gbZ-pmNLWQ67HYbgLuacn-MnpjXB4OLkg%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
