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.

For Subtask
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')
#c = f1.readlines()
#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.
To know more about Floyd Warshall please refer here

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: The Walking Dead
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!

  1. @uwi
  2. @EgorK
  3. @mipletsplay

Please share your valuable Feedback , about the Contest.

7 Likes

Thanks, was waiting for it

4 Likes

@vedant_k07 @mohilllll when you guys will mail the rank certificate. As you guys, had mentioned
the certificates will be provided by sunday.

Sorry for the delay, we’ll send you certificates as soon as possible. Expect it within a couple of days.