# Editorial: Project Code 2.0

## Contest Link : Project Code 2.0

Problem: Alien Invasion
Problem setter: @fallacy69
Tester: @mohilllll

Logic (Explanation)

DIFFICULTY:
Easy

PREREQUISITES:
Basic Math

PROBLEM:
Given 2 numbers P, Q, where P is the numerator and Q, is the denominator, we have to find the sum of the first N digits after the decimal point in the decimal representation of P/Q.

EXPLANATION:
We can get the sum of each digit simply by iterating N times and calculating the value of the digit at the i’th position 1<=i<=N.

Solution in Python
``````for _ in range(int(input())):
n = int(input())
l, m = map(int, input().split())
ans = 0
for j in range(n):
l = (l%m)*10
ans += l//m
print(ans)
``````

Problem: Sandy Tries English
Problem setter: @fallacy69
Tester: @mohilllll @vedant_k07

Logic (Explanation)

DIFFICULTY:
Medium

PREREQUISITES:
Tries

PROBLEM:
Given a dictionary of N words, we are given Q queries and have to find the closest match for each query in the dictionary. The word that is the closest match to a given query has either the same number of letters as the query and just a single letter that is changed OR the word has a single letter that was missing in the query.

EXPLANATION:
The constrains of Subtask-1 are such that it can easily be solved by an optimized brute force approach i.e., it is given in the question that the closest match to every query in the dictionary differs by only one letter. Thus if we iterate over all the word and continue to next word as soon as we find 2 incorrect letters we can solve it within given time limits.

k-2 we construct a trie for the given dictionary and search for a given query within the trie.

Solution in Python
``````class Trie:
def __init__(self):
self.il = False
self.ch = [None]*26

def insT(s, root):
pk = root
for i in range(len(s)):
ind = ord(s[i])-ord('a')
if pk.ch[ind] == None:
pk.ch[ind] = Trie()
pk = pk.ch[ind]
pk.il = True

def conT(dct, root):
for i in dct:
insT(i, root)

def chk(k, arr):
if len(k) == 0:
return arr[0]
b = True
for i in range(len(arr)):
b = True
for j in range(len(k)):
if k[j] != arr[i][j] or j > len(arr[i])-1:
b = False
break
if b == True:
return arr[i]
return "0"

def disT(root, s, lvl, ans):
if root.il==True:
ans.append(s)
for i in range(26):
if root.ch[i] != None:
s += chr(i+ord('a'))
disT(root.ch[i], s, lvl+1, ans)
return ans

def macT(k, root):
lvl, ans, pk, i = 0, [], root, 0
while i < len(k):
j = ord(k[i])-ord('a')
if pk.ch[j] != None:
pk = pk.ch[j]
lvl += 1
else:
return "0"
i += 1
ans = disT(pk, k, lvl, ans)
for i in range(len(ans)):
ans[i] = ans[i][::-1]
return ans

#f1 = open(r'C:\Users\User\Desktop\Imp\i4.txt', 'r')
#f2 = open(r'C:\Users\User\Desktop\Imp\o4.txt', 'w')
#f1.close()
#t = int(c[0].strip('\n'))
#i = 1
#_ = 0
#while _ < t:
for _ in range(int(input())):
#n, q = map(int, c[i].strip('\n').split())
n, q = map(int, input().strip().split())
dic1 = []
dic2 = []
#p = i
#while i < p + n:
for i in range(n):
#s = c[i].strip('\n')
s = input().strip()
dic1.append(s)
dic2.append(s[::-1])
#i += 1
r1 = Trie()
conT(dic1, r1)
r2 = Trie()
conT(dic2, r2)
#p = i
#while i < p + q:
for i in range(q):
#s = c[i].strip('\n')
s = input().strip()
k = len(s)
for j in range(k):
t1, t2 = j, k-j-1
if t1 >= t2:
ans = macT(s[0:j], r1)
if ans == "0":
continue
ans1 = chk(s[j+1:len(s)][::-1], ans)
if ans1 == "0":
continue
#f2.writelines(ans1[::-1] + "\n")
print(ans1[::-1])
break
else:
ans = macT(s[j+1:len(s)][::-1], r2)
if ans == "0":
continue
ans1 = chk(s[0:j], ans)
if ans1 == "0":
continue
#f2.writelines(ans1 + "\n")
print(ans1)
break
#i += 1
#_ += 1
#f2.close()
``````

Problem: Flash tries MBA
Problem setter: @vedant_k07
Tester: @mustankap @jayss5

Logic (Explanation)

After taking a look at the constraints, you could see that even if we have 100 cities where going between any city would take Flash back 100 minutes in time, we would still not able to go 10 years in the past when choosing a never visited city every time.

Assuming all the cities are nodes of a graph and the time travel that happens between them are the edges, we have to find if there exists a cycle which has a negative weight.

Hence, we have to find if the graph has a negative cycle in it. This can be easily be solved by the Floyd Warshall algorithm. In this, we try finding the shortest distance between a source and other nodes. If the shortest distance keeps on decreasing, we then know that there exists a negative cycle.

Solution in C++
``````#include <bits/stdc++.h>
using namespace std;
int inf = 1e9;

int main(){
int t;
cin >> t;
while(t){
int n;
cin >> n;
int ** matrix = new int*[n];
for(int i = 0; i < n; i++){
matrix[i] = new int[n];
}
for(int i = 0; i < n; i++){
for(int j = 0; j< n;j++){
cin >> matrix[i][j];
}
}
int ** dist = new int*[n];
for(int i = 0; i < n; i++){
dist[i] = new int[n];
}
for(int i = 0; i < n ; i++){
for(int j = 0; j < n; j++){
dist[i][j] = matrix[i][j];
}
}
int flag = 0;
for(int k = 0; k < n; k++){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
dist[i][j] = min(dist[i][j] , dist[i][k] + dist[k][j]);

}

}

}
for (int i = 0; i < n;i++){
if (dist[i][i] < 0)
flag = 1;
}
if(flag){
cout << "YES" << endl;
}
else{
cout << "NO" << endl;
}
t--;
}

return 0;
}
``````

Problem: Chef and Bank
Problem setter: @mohilllll
Tester: @vedant_k07 @fallacy69 @jayss5

Logic (Explanation)

Problem Description:
Form a sequence of N natural numbers in which all pairwise sums ai + aj (i ≤ j) are different.

Difficulty:
Easy-Medium

Pre-requisites:
Math (Sidon Sequence aka B2 Sequence), Ad-hoc

Solution:
It is given in the question that Chef’s first denomination is always 1, which means, next number in sequence would be such that it’s sum with itself or any previously deposited denomination are pairwise distinct.
In order to form the sequence of size 700 (Max constraints),

We keep a ‘visited’ array of size 1.5*10^7 where we mark all ‘visited’ sums.
We make a vector ‘ans’ for storing our sequence, since we know 1 is the first element we push it to the vector. The only sum possible is 1+1 = 2 so we mark visited[2] = true.
We now use a while loop to fill the vector till ans.size() < n.
Inside while loop, we check for ‘potential’ next element in a for loop where we start from i = lastElementInserted + 1 till infinity and for each i we check its sum with the already added element in ‘ans’ vector i.e. for 0 ≤ j ≤ ans.size()-1, we check if visited[i+ans[j]] == false or not, if none of them turns out to be true we add j to the ans vector and mark its sum with other element and itself as visited.

This is the precomputation part, something which we keep ready before executing out testcase, single time execution of it makes the answer very efficient over several testcases.
OPTIONAL: One may also maintain a sum vector where sum[k] = sum upto k elements of the sequence.

Solution in Python
``````sm=[1, 3, 7, 15, 28, 49, 80, 125, 191, 272, 369, 492, 640, 822, 1026, 1278, 1568, 1929, 2330, 2805, 3370, 3963, 4625, 5400, 6222, 7138, 8108, 9124, 10283, 11595, 12990, 14513, 16085, 17906, 19802, 21831, 24085, 26464, 28974, 31754, 34679, 37834, 41188, 44779, 48576, 52574, 56871, 61304, 66083, 70934, 76057, 81300, 86598, 92349, 98347, 104721, 111522, 118447, 125907, 133454, 141243, 149463, 157966, 166696, 175638, 185520, 195720, 206307, 217205, 228494, 240108, 251984, 264018, 276949, 290343, 304390, 318924, 333825, 348991, 364679, 380651, 397270, 414625, 432557, 451402, 470473, 490104, 509774, 530496, 552444, 574970, 598261, 621825, 645706, 670302, 695070, 720701, 746738, 772993, 800212, 828778, 858553, 888647, 919958, 952175, 984795, 1017707, 1051984, 1087314, 1122783, 1158987, 1197634, 1236794, 1276017, 1315960, 1356760, 1398642, 1441191, 1484585, 1529464, 1575371, 1622792, 1670304, 1718601, 1768665, 1819567, 1872270, 1925034, 1979708, 2035015, 2091678, 2150103, 2209131, 2269707, 2330702, 2392907, 2456036, 2520524, 2587523, 2654712, 2723224, 2792208, 2862378, 2933743, 3009361, 3086154, 3163725, 3242772, 3323081, 3406260, 3490605, 3577621, 3665495, 3754061, 3843668, 3935386, 4028273, 4122112, 4217215, 4315189, 4414772, 4516109, 4618149, 4721775, 4826329, 4933276, 5040481, 5149103, 5260940, 5373740, 5487689, 5602331, 5718622, 5835799, 5957037, 6082529, 6209166, 6338336, 6469322, 6601019, 6735433, 6870132, 7006767, 7146731, 7290025, 7434899, 7581504, 7729003, 7877596, 8027742, 8180060, 8332894, 8489730, 8646880, 8807662, 8970672, 9134174, 9299042, 9470026, 9642948, 9817119, 9994972, 10175221, 10357292, 10542695, 10731009, 10921735, 11112629, 11306106, 11502938, 11702584, 11904056, 12106755, 12312080, 12518891, 12727639, 12942074, 13159256, 13377267, 13602617, 13829299, 14058462, 14290156, 14523726, 14758345, 14993497, 15232224, 15473038, 15720860, 15974717, 16229022, 16489455, 16751075, 17013392, 17279942, 17549137, 17820648, 18094898, 18369651, 18649831, 18934120, 19224125, 19517159, 19812196, 20108702, 20407116, 20709779, 21015561, 21324402, 21642141, 21963314, 22286986, 22611792, 22940973, 23271991, 23608633, 23949534, 24292893, 24639894, 24988004, 25336903, 25699423, 26065542, 26433777, 26804473, 27176015, 27553465, 27933831, 28315843, 28698088, 29083045, 29470524, 29861042, 30252504, 30651678, 31055598, 31467445, 31880116, 32296996, 32714987, 33137440, 33571413, 34006186, 34446805, 34887953, 35331732, 35777797, 36234086, 36692512, 37154914, 37625584, 38100252, 38576052, 39057528, 39540396, 40038831, 40539915, 41048108, 41559366, 42074010, 42598317, 43125514, 43660883, 44197786, 44736117, 45278137, 45833412, 46397428, 46963534, 47530942, 48102969, 48685447, 49268854, 49854725, 50447982, 51044819, 51643245, 52243029, 52850823, 53461227, 54083017, 54707591, 55335294, 55968736, 56608783, 57257641, 57916820, 58580378, 59247715, 59920530, 60594052, 61280065, 61971751, 62664920, 63359199, 64056130, 64759292, 65470656, 66193905, 66923765, 67654773, 68394731, 69134855, 69879258, 70632551, 71400685, 72170798, 72944710, 73724627, 74512034, 75306934, 76104501, 76905159, 77719118, 78533532, 79360655, 80189784, 81029512, 81876942, 82727637, 83579264, 84442120, 85322916, 86207641, 87096926, 87993617, 88890777, 89795747, 90705333, 91620587, 92543439, 93479134, 94416959, 95355835, 96315772, 97277125, 98241982, 99212209, 100188565, 101169146, 102155945, 103164051, 104173886, 105190792, 106211098, 107239710, 108272952, 109308964, 110351782, 111402663, 112454446, 113515290, 114601692, 115693735, 116789897, 117893353, 119016817, 120150874, 121287284, 122431364, 123576516, 124724290, 125880977, 127045255, 128211510, 129386261, 130573318, 131768634, 132969896, 134177241, 135389895, 136608505, 137833524, 139061411, 140302188, 141549259, 142807494, 144072956, 145347045, 146626560, 147915173, 149214153, 150520401, 151847319, 153181128, 154522318, 155865800, 157233280, 158606014, 159980793, 161365745, 162753892, 164148132, 165543478, 166953090, 168370426, 169789369, 171212665, 172658874, 174107368, 175569967, 177038900, 178513598, 180009708, 181511925, 183020260, 184534204, 186083897, 187636258, 189194562, 190762288, 192340595, 193934138, 195528508, 197125060, 198729627, 200341282, 201979483, 203637387, 205298936, 206967280, 208651933, 210352781, 212056842, 213769060, 215502208, 217246608, 219003567, 220769753, 222540050, 224314690, 226098472, 227889276, 229686462, 231505629, 233327724, 235163514, 237002201, 238842449, 240685714, 242544201, 244415902, 246290351, 248197506, 250130725, 252072598, 254025706, 255986670, 257956756, 259952141, 261957667, 263964055, 265976462, 267998881, 270026325, 272058396, 274104744, 276154435, 278235653, 280320698, 282427703, 284538714, 286655861, 288784665, 290915399, 293048964, 295212033, 297377676, 299561074, 301747656, 303948522, 306177355, 308416112, 310676509, 312964506, 315268196, 317574406, 319885485, 322205142, 324552319, 326900664, 329265293, 331645950, 334032641, 336424944, 338838313, 341267958, 343703819, 346149726, 348604329, 351065485, 353546692, 356039961, 358536519, 361062789, 363612063, 366171147, 368736748, 371308741, 373883363, 376472948, 379075684, 381681736, 384317314, 386953370, 389603082, 392270257, 394968170, 397673768, 400390240, 403116865, 405857505, 408605537, 411374854, 414148491, 416925666, 419722120, 422530261, 425348311, 428170520, 430998855, 433851903, 436710857, 439589860, 442488559, 445394785, 448322920, 451258388, 454208555, 457163785, 460122989, 463104198, 466104190, 469117296, 472133481, 475150209, 478183694, 481224981, 484271386, 487357228, 490454591, 493583639, 496720740, 499869714, 503022740, 506188165, 509360365, 512548014, 515756809, 518984837, 522224634, 525489987, 528771524, 532081914, 535412053, 538761969, 542113713, 545474663, 548841261, 552217171, 555600166, 559011941, 562450142, 565897282, 569351093, 572822613, 576307740, 579830488, 583399900, 586975590, 590553888, 594139450, 597732787, 601357524, 604983722, 608635223, 612302747, 615977181, 619653088, 623391704, 627145890, 630911731, 634698061, 638505442, 642323485, 646153020, 649984894, 653823267, 657685775, 661596388, 665539077, 669489261, 673443726, 677422195, 681414962, 685429663, 689461882, 693495806, 697561174, 701639178, 705728784, 709830430, 713949434, 718104532, 722270861, 726447765, 730630710, 734828458, 739040051, 743258779, 747512016, 751787457, 756076092, 760374781, 764676753, 769006619, 773364259, 777756589, 782159916, 786575459, 791010116, 795464896, 799925713, 804392952, 808882493, 813401257, 817928148, 822469468, 827030425, 831598515, 836180547, 840789888, 845421725, 850104807, 854793681, 859508643, 864236873, 868970827, 873714946, 878512709, 883332010, 888155447, 893006444, 897871926, 902758907, 907666727, 912597849, 917555631, 922561602, 927576280, 932607357, 937662259, 942721559, 947810218, 952930033, 958065713, 963219089, 968429191, 973642739, 978896323, 984153032]
a=[1, 2, 4, 8, 13, 21, 31, 45, 66, 81, 97, 123, 148, 182, 204, 252, 290, 361, 401, 475, 565, 593, 662, 775, 822, 916, 970, 1016, 1159, 1312, 1395, 1523, 1572, 1821, 1896, 2029, 2254, 2379, 2510, 2780, 2925, 3155, 3354, 3591, 3797, 3998, 4297, 4433, 4779, 4851, 5123, 5243, 5298, 5751, 5998, 6374, 6801, 6925, 7460, 7547, 7789, 8220, 8503, 8730, 8942, 9882, 10200, 10587, 10898, 11289, 11614, 11876, 12034, 12931, 13394, 14047, 14534, 14901, 15166, 15688, 15972, 16619, 17355, 17932, 18845, 19071, 19631, 19670, 20722, 21948, 22526, 23291, 23564, 23881, 24596, 24768, 25631, 26037, 26255, 27219, 28566, 29775, 30094, 31311, 32217, 32620, 32912, 34277, 35330, 35469, 36204, 38647, 39160, 39223, 39943, 40800, 41882, 42549, 43394, 44879, 45907, 47421, 47512, 48297, 50064, 50902, 52703, 52764, 54674, 55307, 56663, 58425, 59028, 60576, 60995, 62205, 63129, 64488, 66999, 67189, 68512, 68984, 70170, 71365, 75618, 76793, 77571, 79047, 80309, 83179, 84345, 87016, 87874, 88566, 89607, 91718, 92887, 93839, 95103, 97974, 99583, 101337, 102040, 103626, 104554, 106947, 107205, 108622, 111837, 112800, 113949, 114642, 116291, 117177, 121238, 125492, 126637, 129170, 130986, 131697, 134414, 134699, 136635, 139964, 143294, 144874, 146605, 147499, 148593, 150146, 152318, 152834, 156836, 157150, 160782, 163010, 163502, 164868, 170984, 172922, 174171, 177853, 180249, 182071, 185403, 188314, 190726, 190894, 193477, 196832, 199646, 201472, 202699, 205325, 206811, 208748, 214435, 217182, 218011, 225350, 226682, 229163, 231694, 233570, 234619, 235152, 238727, 240814, 247822, 253857, 254305, 260433, 261620, 262317, 266550, 269195, 271511, 274250, 274753, 280180, 284289, 290005, 293034, 295037, 296506, 298414, 302663, 305782, 308841, 317739, 321173, 323672, 324806, 329181, 331018, 336642, 340901, 343359, 347001, 348110, 348899, 362520, 366119, 368235, 370696, 371542, 377450, 380366, 382012, 382245, 384957, 387479, 390518, 391462, 399174, 403920, 411847, 412671, 416880, 417991, 422453, 433973, 434773, 440619, 441148, 443779, 446065, 456289, 458426, 462402, 470670, 474668, 475800, 481476, 482868, 498435, 501084, 508193, 511258, 514644, 524307, 527197, 535369, 536903, 538331, 542020, 555275, 564016, 566106, 567408, 572027, 582478, 583407, 585871, 593257, 596837, 598426, 599784, 607794, 610404, 621790, 624574, 627703, 633442, 640047, 648858, 659179, 663558, 667337, 672815, 673522, 686013, 691686, 693169, 694279, 696931, 703162, 711364, 723249, 729860, 731008, 739958, 740124, 744403, 753293, 768134, 770113, 773912, 779917, 787407, 794900, 797567, 800658, 813959, 814414, 827123, 829129, 839728, 847430, 850695, 851627, 862856, 880796, 884725, 889285, 896691, 897160, 904970, 909586, 915254, 922852, 935695, 937825, 938876, 959937, 961353, 964857, 970227, 976356, 980581, 986799, 1008106, 1009835, 1016906, 1020306, 1028612, 1033242, 1036012, 1042818, 1050881, 1051783, 1060844, 1086402, 1092043, 1096162, 1103456, 1123464, 1134057, 1136410, 1144080, 1145152, 1147774, 1156687, 1164278, 1166255, 1174751, 1187057, 1195316, 1201262, 1207345, 1212654, 1218610, 1225019, 1227887, 1240777, 1247071, 1258235, 1265462, 1274089, 1279515, 1288613, 1298980, 1306248, 1326918, 1333809, 1341190, 1343482, 1367480, 1372734, 1374779, 1384952, 1388147, 1394240, 1395346, 1409612, 1417336, 1418943, 1423296, 1446209, 1448494, 1462599, 1468933, 1474698, 1496110, 1502217, 1508335, 1513944, 1549693, 1552361, 1558304, 1567726, 1578307, 1593543, 1594370, 1596552, 1604567, 1611655, 1638201, 1657904, 1661549, 1668344, 1684653, 1700848, 1704061, 1712218, 1733148, 1744400, 1756959, 1766186, 1770297, 1774640, 1783782, 1790804, 1797186, 1819167, 1822095, 1835790, 1838687, 1840248, 1843265, 1858487, 1871701, 1874449, 1907155, 1933219, 1941873, 1953108, 1960964, 1970086, 1995385, 2005526, 2006388, 2012407, 2022419, 2027444, 2032071, 2046348, 2049691, 2081218, 2085045, 2107005, 2111011, 2117147, 2128804, 2130734, 2133565, 2163069, 2165643, 2183398, 2186582, 2200866, 2228833, 2238757, 2260397, 2287997, 2303690, 2306210, 2311079, 2319657, 2347177, 2348345, 2364629, 2380657, 2386691, 2392303, 2413369, 2429645, 2435861, 2445907, 2454603, 2461156, 2481207, 2493269, 2496558, 2526270, 2549274, 2559084, 2565601, 2571993, 2574622, 2589585, 2602736, 2606052, 2635578, 2636056, 2649712, 2667175, 2697913, 2705598, 2716472, 2726625, 2740640, 2748032, 2769317, 2773637, 2777175, 2796454, 2808141, 2818050, 2822209, 2828335, 2853048, 2858954, 2879003, 2898699, 2906226, 2928135, 2935468, 2950167, 2955230, 2959204, 2981209, 2999992, 3013106, 3016185, 3016728, 3033485, 3041287, 3046405, 3085842, 3097363, 3129048, 3137101, 3148974, 3153026, 3165425, 3172200, 3187649, 3208795, 3228028, 3239797, 3265353, 3281537, 3310390, 3330139, 3349916, 3351744, 3360950, 3366598, 3375910, 3382995, 3411775, 3438201, 3447140, 3453811, 3471520, 3485127, 3522748, 3569412, 3575690, 3578298, 3585562, 3593337, 3624737, 3626198, 3651501, 3667524, 3674434, 3675907, 3738616, 3754186, 3765841, 3786330, 3807381, 3818043, 3829535, 3831874, 3838373, 3862508, 3910613, 3942689, 3950184, 3954465, 3978469, 3992767, 4014701, 4032219, 4033924, 4065368, 4078004, 4089606, 4101646, 4119004, 4155098, 4166329, 4176904, 4182945, 4197748, 4211593, 4218728, 4253237, 4275441, 4288635, 4298689, 4301972, 4329866, 4357640, 4392330, 4403327, 4415543, 4434657, 4454780, 4460817, 4467239, 4489541, 4518764, 4526891, 4541320, 4560957, 4568090, 4582032, 4609341, 4631837, 4683082, 4688874, 4714962, 4728230, 4733954, 4744119, 4797763, 4819301, 4823437, 4850997, 4865482, 4886981, 4907820, 4931122, 4957782, 5005971, 5014678, 5031077, 5054902, 5059300, 5088659, 5119815, 5135680, 5153376, 5210102, 5213548, 5253584, 5256709]
t= int(input())
for _ in range(t):
n=int(input())

for i in range(n):
print(a[i],end=" ")
print()
print(sm[n-1])
``````

Problem: Weird list
Problem setter: @mishrakeshav
Tester: @phoenix_307

Logic (Explanation)

You are given 4 Integers, N on which you have to perform operations and A, B and C

Initially, N can take any value between 0 to 10^9 when it is divided by A. After that it can take any value between 0 to 9 You have to find a sequence that gets repeated from the step when N is divided by A. There will always be a sequence which will repeat itself after some iteration.

This can be proved using the pigeon hole principle. Since N can take values between 0 and 9 and also its initial Value. If after some iteration we get the value of N which was already divided by A then this is the point where the sequence starts repeating itself. You will have to keep track of the start of the repeating sequence in the list.

This can be better understood by an example,
If N = 1 and A = 2, B = 3, C = 4
N/ A = 0.5 then N = 5
N/ B = 1.6666666666666667 then N = 6
N/ C = 1.5 then N = 5
N/A = 2.5 then N = 5
N/ B = 1.6666666666666667 then N = 6
N/ C = 1.5 then N = 5
Since we have already divided 5 by A, So the sequence will repeat itself.
So the LIST = { 1, 5, 6, 5, 5, 6, 5 }

The sequence repeats itself from index 4 to 6.
nonrepeated_sequence = { 1, 5, 6, 5 }
repeated_sequence = {5, 6, 5 }
If the query is less than nonrepeated_sequence.length then
then LIST[ index ]
else
repeated_sequence[ (index - nonrepeated_sequence.length )%(repeated_seqence.length) ]

Solution in Python
``````    def query(i,arr,repeat):
if i < len(arr):
return arr[i]
else:
return (repeat[(i - len(arr))% len(repeat)])
def solve():
n = int(input())
a,b,c = map(int,input().split())
arr = []

mem = {}
while True:
if n in mem:
break
else:
arr.append(n)
mem[n] = len(arr)
n = n/a
s = str(n)
for i in range(len(s)):
if s[i] == ".":
if s[i+1] != '0':
n = int(s[i+1])
else:
n = int(s[0])
arr.append(n)
n = n/b
s = str(n)
for i in range(len(s)):
if s[i] == ".":
if s[i+1] != '0':
n = int(s[i+1])
else:
n = int(s[0])
arr.append(n)
n = n/c
s = str(n)
for i in range(len(s)):
if s[i] == ".":
if s[i+1] != '0':
n = int(s[i+1])
else:
n = int(s[0])

new_arr = arr[:mem[n]-1]
repeat = arr[mem[n]-1:]
#print(new_arr)
#print(repeat)
Q = int(input())
for q in range(Q):
i = int(input())
print(query(i, new_arr, repeat))

if __name__ == '__main__':
for t in range(int(input())):
solve()
``````

Problem: Genesis
Problem setter: @hk2098
Tester: @fallacy69

Logic (Explanation)

This question is based on permutations and combinations. Given N number of distinct pairs of matter and its corresponding anti-matter, we have to find the number of ways in which they can be arranged in a 2D-circular form regardless of the orientation of the arrangement, such that total annihilations of ALL particles doesn’t take place i.e., at least one pair remains un-annihilated after he arranges them in a circular pattern.

First of all, we calculate all the number of ways in which matter and antimatter are adjacent to each other, i.e we get n!(n-1)! in which, any of matter and antimatter gets arranged in (n-1)! ways and n! ways for the other.

Now, we subtract all the ways in which matter and its corresponding
antimatter in adjacent from the total number of ways, i.e 2!(n-1)!.

Hence we have ans = n!(n-1)! - 2(n-1)!
ans = (n-1)!(n (n-1)! - 2)
To compute the factorial in an optimal amount of time we use memorization, and store the value of the calculated factorial in a deque and use it if needed in further calculations of test cases. One more method is precomputation of the factorial array, i.e calculate the factorials of all the numbers x, 0<=x<=10^7 before taking the input, and fact[n-1] to find the value of factorial of (n-1), where fact[] is the pre-computed array.

Solution in Python
``````MOD = 1000000007
k = 1
ans = [1]*10000001
ans[0], ans[1] = 1, 1

def facM(n):
global ans
global k
if n == 0 or n == 1:
return 1
if ans[n] == 1:
for i in range(k+1, n+1):
ans[i] = (ans[i-1]*i)%MOD
k = i
return ans[n]
return ans[n]

for _ in range(int(input())):
n = int(input())
d = facM(n-1)
ans1 = (d*(((n*d)-2)%MOD))%MOD
if n == 0 or n == 1:
ans1 = 0
print(ans1)
``````

Problem setter: @phoenix_307
Tester: @vedant_k07

Logic (Explanation)

After converting all the values in the matrix into probabilities, the new matrix formed is called a ‘Markov Matrix’. In this matrix, the value at (i, j) denotes the probability of going from state i to state j.
We can form a vector of zeros of dimension (N x 1) and mark the initial position of the person at place i (0 <= i < N) by marking ith position as 1. This means that there is 100% probability that the person is in place ‘i’ Now, after a single transition the new probabilities can be obtained by Multiplying the Markov Matrix and the vector. However there can be multiple transitions. In this case we again have to multiply the previously obtained vector with the matrix.
For ‘k’ transitions we have to do this ‘k’ times.

Now lets denote the probability vector after k transitions as ‘vk’.
v0 - Initial probability vector
M - Markov matrix
Then v1 can be written as:
v1 = M * v0
Similarly v2 can be written as:
v2 = M * v1
But v1 = M*v0
Therefore,
v2 = M * M * v0
v2 = M^2 * v0
Similarly after k transitions:
vk = M^k * v0
In our question the no. of transitions is not defined, thus there can be n number of transitions.
We will take the matrix raised to a high power so that after applying further transitions it wont make any difference to the probabilities.

Solution in Python
``````def matMul(matA, matB, rA, cA, rB, cB):
if rB != cA:
raise ValueError()

matC = [[0 for i in range(cB)]for j in range(rA)]
for i in range(rA):
for j in range(cB):
for k in range(rB):
matC[i][j] += matA[i][k]*matB[k][j]

return matC

def matPow(mat, pow, dim):
res = [[0 if i!=j else 1 for i in range(dim)] for j in range(dim)]
while(pow):
if pow&1:
res = matMul(res, mat, dim, dim, dim, dim)
mat = matMul(mat, mat, dim, dim, dim, dim)
pow >>= 1
return res

def matTransporse(m):
M=[[0 for i in range(len(m))] for j in range(len(m))]
for i in range(len(m)):
for j in range(len(m)):
M[i][j]=m[j][i]
return M

power = 10**3
for t in range(int(input())):
n = int(input())
mat = []
for i in range(n):
arr = list(map(int, input().split()))
temp = sum(arr)
arr = list(map(lambda x: x/temp, arr))
mat.append(arr)
mat = matTransporse(mat)
mat = matPow(mat, power, n)

arr = [[0] for i in range(n)]
best = 0
idx = 0
for i in range(1, n):
arr[i][0] = 1
ans = matMul(mat, arr, n, n, n, 1)
arr[i][0] = 0
if ans[0][0] > best:
best = ans[0][0]
idx = i

print(idx)
``````

Problem: Space Wrap
Problem setter: @vedant_k07
Tester: @fallacy69

Logic (Explanation)

The first Subtask can be solved with brute force. As the starting position is unknown, we check the probability of getting out when started from all N^3 possibilities.
We then check all the different paths we and co-ordinates we could go to. Given a string of length “L”, There would be 2^L different possibilities as every character has a 50% probability of changing into the corresponding character.

The probability of reaching a point would become half with every step
For Eg: for string “UW” can become “DW”, ”UE” and ”DE”, and the probability of going up or down is 50% and the probability of then going east or west would be 50% of 50% i.e 25%.
Time complexity would be O( N^3X2^L)

For the second subtask, we use memoization, i.e. we save every time the probability of getting out from when started from a given point with a given string.
For example, for N=10 and string = ”USE”
If we check the probability of getting out when started from co-ordinates ( 0 0 0 ) we would also get the probability of getting out when started from (1 0 0) for the string “SE”.
So, when we start from a point (2 0 0), we end up at (1 0 0) after one step( as U can be D).
This time we do not check for the remaining paths, we just use the probability saved during previous travel.

Solution in Python
``````import math
import time
def calc_prob(i, j, k, s, n, prob):
if math.ceil(math.sqrt(i*i+j*j+k*k))==math.floor(math.sqrt(i*i+j*j+k*k)):
return prob
if len(s)==0:
return 0
if (i,j,k,s) in d:
return d[(i,j,k,s)]
c=s[0]
if c=='N' or c=='S':
prob=calc_prob((i+1)%n,j,k,s[1:],n,prob/2)+calc_prob((i-1)%n,j,k,s[1:],n,prob/2)
if c=='E' or c=='W':
prob=calc_prob(i,(j+1)%n,k,s[1:],n,prob/2)+calc_prob(i,(j-1)%n,k,s[1:],n,prob/2)
if c=='U' or c=='D':
prob=calc_prob(i,j,(k+1)%n,s[1:],n,prob/2)+calc_prob(i,j,(k-1)%n,s[1:],n,prob/2)
d[(i,j,k,s)]=prob
return prob

#t=int(input())

#for T in range(t):
n=int(input())
l=int(input())
s=input()
start = time.time()
prob=0
d={}
for i in range(n):
for j in range(n):
for k in range(n):
prob+=calc_prob(i,j,k,s,n,100)
prob=prob/(n*n*n)
print(round(prob*10**5))
#print("--- %s seconds ---" % (time.time() - start))
``````

Congratulations to the Contest Winner!