On Sunday, April 7, 2019 at 6:08:10 PM UTC+2, /dev/joe wrote:
> It is possible when the message starts something like ABA for the first two
> values to be the same. In this case, you get gcd = values[0] instead of the
> prime shared between the first two values, and this wrong calculation leads
> to some of your later numbers being fractions, which probably leads to you
> computing more than 26 different values and then
> alphabets[primes.index(divisors[j])] indexes beyond the length of alphabets.
>
>
> You have to find the first two values which are different and take their GCD
> to start the process off, and possible wind it both forward and backward from
> that point.
>
>
> Also, if you use math.gcd() (fractions.gcd() in versions of Python before
> 3.5) instead of your GCD function, it will use the Euclidean algorithm to
> compute GCD which will be fast enough for the hidden input where the primes
> could be up to 100 digits long.
As you seem pretty knowledgeable, any idea why my solution fails on the hidden
set ?
import io
import sys
import math
n_test = int(input())
for t in range(0,n_test):
first = True
print( "Case #%d: " % (t+1), end='' )
(v, n) = [int (v) for v in input().split(" ")]
v = [int (v) for v in input().split(" ")]
flag = True
for w in v:
flag = not flag
if w!=v[0]:
break
letter = math.gcd( v[0], w )
assert( letter>1 )
if flag:
letter = v[0]//letter
msg = []
msg.append( letter )
for n in v:
letter = n//letter
msg.append( letter )
l = list(set(msg))
l.sort()
assert( len(l)==26 )
for letter in msg:
print( chr( 65+l.index( letter ) ), end='' )
print()
Works fine on test, and data like:
4
103 31
217 1891 4819 2291 2987 3811 1739 2491 4717 445 65 1079 8383 5353 901 187 649
1003 697 3239 7663 291 123 779 1007 3551 1943 2117 1679 989 3053
10000 25
3292937 175597 18779 50429 375469 1651121 2102 3722 2376497 611683 489059
2328901 3150061 829981 421301 76409 38477 291931 730241 959821 1664197 3057407
4267589 4729181 5335543
107 29
15 15 15 15 21 49 77 143 221 323 437 667 899 1147 1517 1763 2021 2491 3127 3599
4087 4757 5183 5767 6557 7387 8633 9797 10403
10000000000000000 25
214298700164523419598163457 214298700165108977383752217
214298700165548145722944507 214298700165665257280062499
214298700166104425619255029 214298700167129151744039559
214298700168358823093784523 214298700169939829114889727
214298700172340616035838083 214298700173833788389120837
214298700174009455724801209 214298700174272956728321911
214298700174624291399683087 214298700175268404963845859
214298700176234575310091997 214298700177025078320658963
214298700177376412992022491 214298700177522802438424021
214298700178313305448992499 214298700179279475795246161
214298700179572254688050621 214298700180362757698622879
214298700182177986834017227 214298700183671159187333029
214298700184110327526544399
Case #1: CJQUIZKNOWBEVYOFDPFLUXALGORITHMS
Case #2: SUBDERMATOGLYPHICFJKNQVWXZ
Case #3: ABABACCDEFGHIJKLMNOPQRSTUVWXYZ
Case #4: ABCDEFGHIJKLMNOPQRSTUVWXYZ
--
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/d6939e75-ba80-473e-8524-869505dcaf6c%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
