This question is making me crazy..
Any help appreciated.
My Solution:
explanation:
two possible test cases:
1. where first two ciphers are different and you figure out the first two
letters by finding prime factors and division and using those numbers and
performing division on subsequent ciphers you retrieve all the characters.
2. when some of the ciphers in the beginning are same.
a. Loop till you find a cipher that is different ( point A)
b. retrieve the characters before point A, using point A and last
repetitive cipher as input in case 1
c. from point A follow case 1
import math
from string import ascii_uppercase
from collections import defaultdict
def find_prime_factor(num):
if num%2==0:
return [2, int(num/2)]
n = int(math.sqrt(num)) + 1
for i in range(3, n, 2):
if num % i == 0:
num = num / i
return [i, int(num)]
t = int(input())
for test in range(t):
n, l = list(map(int,input().split()))
nums = list(map(int,input().split()))
d = defaultdict(int)
letter_to_cipher_map=defaultdict(int)
temp = []
i=0
data=[]
lookup=defaultdict(int)
if nums[0]==nums[1]:
while(i<l-1):
if nums[i] == nums[i+1]:
st=i
p=i
while p<l-1 and nums[p]==nums[p+1]:
p += 1
data.append([st, p])
i=p
else:
i+=1
break
end=0
if len(data)>0:
# for interval in data:
interval = data[0]
start=interval[1]
next = start+1
end=interval[0]
a, b = find_prime_factor(nums[next])
# b = math.gcd(nums[start], nums[next])
# a = int(nums[next]/b)
# print('start {}, end {}, next {} '.format(start,end, next))
if nums[start]%a:
if not lookup.get((start,b)):
lookup[(nums[start],b)] = int(nums[start] / b)
letter_to_cipher_map[start]=lookup[(nums[start],b)]
else:
if not lookup.get((nums[start],a)):
lookup[(nums[start],a)] = int(nums[start] / a)
letter_to_cipher_map[start]=lookup[(nums[start],a)]
ptr=start-1
while(end-ptr!=1):
if not lookup.get((nums[ptr+1],letter_to_cipher_map[ptr+1])):
lookup[(nums[ptr+1],letter_to_cipher_map[ptr+1])] =
int(nums[ptr+1]/letter_to_cipher_map[ptr+1])
letter_to_cipher_map[ptr] =
lookup[(nums[ptr+1],letter_to_cipher_map[ptr+1])]
ptr-=1
# print(letter_to_cipher_map)
for ii in range(end, l+1):
if letter_to_cipher_map.get(ii):
continue # no longer required
else:
# next_num = letter_to_cipher_map.get(ii+1)
prev_num = letter_to_cipher_map.get(ii - 1)
if prev_num:
if not lookup[(nums[ii-1], prev_num)]:
lookup[(nums[ii-1], prev_num)] = int(nums[ii-1] /prev_num)
letter_to_cipher_map[ii] = lookup[(nums[ii-1], prev_num)]
# print(prev_num, next_num, ii, letter_to_cipher_map[ii])
else: ## only possible for beginning of non-duplicate
a,b = find_prime_factor(nums[ii+1])
# b = math.gcd(nums[ii], nums[ii+1])
# a = int(nums[ii+1] / b)
# print(a,b)
if nums[ii]%a:
if not lookup[(nums[ii], b)]:
lookup[(nums[ii ], b)] = int(nums[ii] / b)
letter_to_cipher_map[ii]= lookup[(nums[ii ], b)]
letter_to_cipher_map[ii+1]=b
else:
if not lookup[(nums[ii], a)]:
letter_to_cipher_map[ii] = lookup[(nums[ii], a)]
letter_to_cipher_map[ii+1]=a
letter_to_cipher_map[ii]=int(nums[ii]/a)
cipher = sorted(set(letter_to_cipher_map.values()))
# print(sorted(letter_to_cipher_map.values()))
# print(cipher)
chars = {}
ans = ''
k = 0
for c in ascii_uppercase:
chars[cipher[k]] = c
k += 1
# print(chars,k)
le = len(letter_to_cipher_map.keys())
for j in range(le):
ans += chars[letter_to_cipher_map[j]]
print('Case #{}: {}'.format(test + 1, ans))
--
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/5cfac37d-5771-4ea8-818c-e1c9bae05bdf%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
