MindSweepers Editorial

Codathon Editorial

PROBLEM LINK:

Practice Contest Author: Nitesh Singh Tester: Nitesh Singh

DIFFICULTY:

EASY-MEDIUM, MATHS

PREREQUISITES:

Coprime,multiplication,Logic

PROBLEM:

given positive integers x1, x2, . . . , xn with gcd(x1, x2, . . . , xn) = 1, compute the largest integer not representable as a non-negative integer linear combination of the xi . This largest integer is sometimes denoted g(x1, . . . , xn). The restriction gcd(x1, x2, . . . , xn) = 1 is necessary for the definition to be meaningful, for otherwise every non-negative integer linear combination is divisible by this gcd in that case answer would be infinity

EXPLANATION:

Given 2 numbers 'a' and 'b' there equation is ax+by,a and b are coprime So all number can be generate just plot ax+by=N find a and and but the condition here was that a and b cannot be negative,in that case only will there be a maximum number that cannot be generated. consider 7,9 7x+9y=k x=(k-9y)/7 multiples of 9 remainder with 7 Numbers not possible to Generate 9 2 2 18 4 4,4+7=11 27 6 6,6+7=13,20 36 1 1,8,15,22,29 45 3 3,10,17,24,31,38 54 5 5,12,19,26,33,40,47 so the biggest not not possible to generate: a*(b-1)+b*-1=a*b-a-b In the above table we see that with multiples of 9 we have generated all possible remainders of 7. so x=(k-9y)/7 here x can always be intere for any value of k because whatever value of k we take it will give a remainder 0 to 6 and we will put y accordingly to compensate that remainder like k=101 k%7=3 so put y=5 x=(101-9*5)/7 =8

AUTHOR'S AND TESTER'S SOLUTIONS:

Solution :c++ Python

Mr IDC and his Love - Editorial

PROBLEM LINK: Practice Contest Author: Rahul Johari Tester: Rahul Johari DIFFICULTY: EASY-MEDIUM, MATHS PREREQUISITES: Division, Summation of series, modular operation PROBLEM: Given a number N and another number MOD, you have to calculate the sum of numbers from 1 to N as: for ( i=1;i<=N;i++ ) sum += i % MOD; EXPLANATION: By the division algorithm, let N = qm+r with 0 ≤ r < m. Consider the sequence (1 % m),(2 % m), ...,(N % m). It looks like this: 1, 2, 3, ..., m − 1, 0, 1, 2, 3, ..., m − 1, 0, ... 1, 2, 3, ..., m − 1, 0, 1, 2, 3, ..., r There are q layers, each with m elements and a final layer with r elements. We know that sum of first N terms is N(N+1)/2 therefore the sum the numbers in each of the q layers is m(m−1)/2 and the sum of the numbers in the last layer is r(r+1)/2. Therefore using this you can easily calculate sum of large values of N also is O(1) complexity. AUTHOR'S AND TESTER'S SOLUTIONS: Solution can be found here. Mr IDC and his Message - Editorial Practice Contest Author: Rahul Johari Tester: Rahul Johari DIFFICULTY: CAKEWALK PREREQUISITES: String handling, typecasting PROBLEM: Mr.IDC wants to send letter to his girlfriend but the problem is he has encrypted the letter and his girlfriend doesn't know how to decrypt. So she needs your help in decrypting the letter using a key K given as input. EXPLANATION: Mr.IDC has replaced each character with a new character (Ci - K) mod 26 where ( i = [ 0,|message| ] ). So you just have to do: l = len(s) ans = [] for i in range(l): ans.append((ord(s[i])-97+k)%26) You will get the final string which is the output.