Transcript Slides

Solving Adhoc and Math related
problems
- ABHRA DASGUPTA
Problem 1
 Suppose you are given a pile of n coins. A player can
pick up either 1/2/3 coins. Two players play the
game taking moves alternately. The player to pick up
the last coin wins the game. Both players play
optimally. If player 1 can win print his first move or
else print -1.
Solution 1
 In base case if number of coins is <=3 player 1 just
picks all coins.
 If n is multiple of 4 player 1 always loses.
 Else player 1 in 1st move makes it a multiple of 4, i.e.,
1st move is n%4.
Problem 2
 You are given four 3-dimensional points, check whether
they all lie in the same plane.
 Input Format
First line contains T, the number of testcases.
Each test case consists of four lines. Each line contains
three integers, denoting xi yi zi.
 Output Format
For each test case, print YES or NO whether all four points
lie in same plane or not, respectively.
Solution 2
 Suppose we have 3 points A, B, C, D.
 We fix the first point and form 3 vectors say AB, AC, AD;
where
AB = B - A
AC = C - A
AD = D - A
 Now we find V= AB x AC
 V will be perpendicular to the plane of A, B and C.
 If D lies in same plane the vector V must be
perpendicular to AD. So if AD . V = O, then we could say
A, B, C, D are in same plane.
Problem 3
 You are given a string of digits(0-9) of length N. Now
each substring of the string is to be considered as a
number. You need to find the sum of all substrings of
the given string.
 Input Format
A single line containing a string of digits.
 Output Format
A single line which is the sum, T % (109+7).
 Constraints
1 ≤ N ≤ 2*105
Solution 3
 Let us consider an example to consider the problem.
 Given string S=478. S is of length 3, i.e., N=3.
Subsets are:
Lets sort for each position and see.
4
4
7
8
47
78
478
7
7
48
78
478
So we have (4*102)+((4+(2*7))*101)+((4+(2*7)+(3*8))*100)
Solution 3
 So the algorithm for string S of length N will be:
 Preprocessing:
 Temp <- 1
 Mod <- 1000000007
 for i in 0 to 200000


Pow[i] <- Temp
Temp <- ( Temp * 10 ) % Mod
 Main Algorithm:
 M <- 0;
 Ans <- 0;
 for i in 0 to n-1



M <- (M + ( (i+1) * (S[i] – ‘ 0 ’ ) )) % Mod
Ans <- ( Ans + ( M * Pow[n-1-i] ) % Mod ) % Mod
Return Ans
Problem 4
 You are given a string of digits(0-9) of length N. Now
each sub-sequence of the string is to be considered as
a number. You need to find the sum of all subsequence of the given string.
 Input Format
A single line containing a string of digits.
 Output Format
A single line which is the sum, T % (109+7).
 Constraints
1 ≤ N ≤ 2*105
Solution 4
 Suppose you are given a string S=wxyz.
 Length of string is 4, so N=4.
 Now let us see all possible subsequence in order of thier size.
(1) -> w, x , y, z
 (2) -> wx, wy, wz, xy, xz, yz
 (3) -> wxy, wxz, wyz, xyz
 (4) -> wxyz
Now we actually need to first the weightage of digit at each position and
find the sum.
Sum = (w*(1*100 + 3*101 + 3*102 + 1*103)) + (x*(1*100 + 4*101 +
2*102)) + (y*(4*100 + 4*101)) + (z*(8*100))
So let us rewrite it in a good way
Sum = (w*(20)*(113)) + (x*(21)*(112)) + (y*(22)*(111)) + (z*(23)*(110))





Solution 4
 So the algorithm for string S of length N will be:
 Preprocessing:
 Temp_two <- 1 ; Temp_eleven <- 1;
 Mod <- 1000000007
 for i in 0 to 200000




Pow_two[i] <- Temp_two
Pow_eleven[i] <- Temp_eleven
Temp_two <- ( Temp * 2 ) % Mod
Temp_eleven <- (Temp * 11) % Mod
 Main Algorithm:
 Ans <- 0;
 for i in 0 to n-1




Temp <- ( Pow_two[i] * Pow_eleven[n-i-i] ) % Mod
Temp <- ( S[i] * Temp ) % Mod
Ans <- ( Ans + Temp ) % Mod
Return Ans
Problem 5
 You are given a list of N numbers. You can obviously
form 2N-1 non empty sub-lists. Consider the sum of all
sub-lists, let them be S1, S2, …, Sk ; where k=2N-1. Now
you task is to return special_sum defined as Σ 2Si .
 Input Format
The first line contains an integer N, i.e., the size of list A.
The next line will contain N integers, each representing
an element of list A.
 Output Format
Print special_sum modulo (109 + 7).
 Constraints
1 ≤ N ≤ 105
0 ≤ ai ≤ 1010 , where i ∈ [1 .. N]
Solution 5
 Let us denote the special_sum of list A as f(A).
 We know f(∅)=1.
 If S’ = S∖{x} for some x ∈ S, then f(S) = f(S′)⋅(1+2x)
because the subsets of S can be partitioned into those
not containing x (giving f(S′)) and those
containing x (where each corresponding summand is
multiplied by 2x). Therefore, one readily sees that
f(S) = ∏x∈S(1+2x).
Problem 6
 Suppose you are given a list of all numbers starting from 1 in
binary format, the list would be like 1,10,11,100,... and so on,
from which we remove any pattern having atleast two
consecutive ones and prepare a new list. The new list will be
like 1,10,100,101,... and so on. Now if a value N is given you
must return the value of the Nth element of the list.
 Input Format
The first line contains T(<=1000) test cases. The next T lines
each contain one integer N(<=10^15) .
 Output Format
Output T lines each containing the required answer.
 Constraints
T <= 103
N <= 1015
Solution 6
 This problem is solved by just writing the value of N
in ‘Fibonacci base’.
 How to evaluate Fibonacci base?




Find the nearest Fibonacci number(F) less than equal to N.
Subtract f from N and write 1(MSB of output).
Now check for the lower Fibonacci number, if it is greater than
N then print 0 as that bit, else print 1 and reduce the N by the
Fibonacci number.
Repeat the above step till all Fibonacci numbers less than F are
used.
Problem 7
 Given a number N, you must return the Nth
Fibonacci number.
 Input Format
One integer N.
 Output Format
Output Nth Fibonacci number modulo 109 +7
 Constraints
N<=1012
Solution 7
 Let us first look at technique of using exponentiation
to find AN in log(N) time, where A and N are
integers.
 Power(A,N):


Result <- 1
while (N)
if (N%2 == 1)
 Result *= A
 N=N/2
A=A*A


return Result;
Solution 7
 We will use matrix exponentiation to find the Nth
Fibonacci number.
 Consider the following 2 x 2 matrix:
A= 1 1
1 0
 The Nth Fibonacci number, denoted by FN can be
calculated as:
AN =
FN+1 FN
FN FN-1
Problem 8
 You’re given a number N and a positive integer K. Tell if N can
be represented as a sum of K prime numbers (not necessarily
distinct).
 Input Format
The first line contains a single integer T, denoting the number
of test cases.
Each of the next T lines contains two positive integers, N & K,
separated by a single space.
 Output Format
For every test case, output “Yes” or “No” (without quotes).
 Constraints
1 <= T <= 5000
1 <= N <= 1012
1 <= K <= 1012
Solution 8
 We are going to use Goldbach’s Conjecture to solve
this problem.
 Goldbach’s Conjecture states that :
 Every even integer greater than 2 can be represented as a sum
of two prime numbers.
 Any number greater than 5 can be represented as a sum of
three prime numbers.
Solution 8
 Now since we know the Goldbach’s Conjecture we device our
strategy accordingly:

N < 2K: The answer is “No”, because the sum of K primes is at least 2K.

N ≥ 2K and K = 1: The answer is “Yes” if N is prime, and “No” otherwise.

N ≥ 2K, K = 2 and N is even: The answer is “Yes” (by Goldbach’s conjecture).

N ≥ 2K, K = 2 and N is odd: The answer is “Yes” if N − 2 is prime, and “No”
otherwise. This is because the sum of two odd primes is even, and the only
even prime number is 2, so one of the prime numbers in the sum must be 2.

N ≥ 2K and K ≥ 3: The answer is “Yes”. This is because if N is even, then
N − 2(K − 2) is also even, so it is the sum of two primes, say p and q (by
Goldbach’s conjecture). Thus, N is the sum of the K primes 2, 2, 2, ..., p, q.
And if N is odd, then N − 3 − 2(K − 3) is even, so it is the sum of two primes,
say p and q. Thus, N is the sum of the K primes 3, 2, 2, ..., p, q.
Problem 9

Their current salaries of N employees are denoted by sequence of N integers A1, A2, A3 … AN .
Manager has decided to take action and make their salaries equal. He uses the following process until
all salaries are equal. This method is called as normalization:
 a) Select any two different values from A.
 b) Replace larger value with the difference of the two. Difference of two positive integers B and C is
defined as |B-C|.
 He knows that the final value will always be unique.
Now, Q queries are given. In each query you are given integer K. K is the amount to be added to
everyone’s salary as bonus, before the normalization.
 Input Format
First line contains, N and Q, the number of employees and the number of queries. Next line
contains N space separated positive integers denoting the array A. Next Q lines contain queries. Each
query consists of one integer per line denoting K.
 Output Format
For each query, print the normalized salary(which is same for everyone in the end) in one line.
 Constraints
1 ≤ N ≤ 105
1 ≤ Q ≤ 105
1 ≤ A[i] ≤ 1014
0 ≤ K ≤ 109
Solution 9
 Without loss of generality we can assume A1,A2,…,AN
are in sorted order.
 The normalization process is actually finding GCD of
all numbers.
 Now if we add K to all, the required answer is:



gcd(A1+K, A2+K, ..., An+K)
= gcd(A1+K, A2+K-(A1+K), A3+K-(A1+K)..., An+K-(A1+K))
= gcd(A1+K, A2 - A1, A3 - A1, ..., An-A1)
= gcd(A1+K, G)
where G = gcd(A2-A1, A3-A1..., An-A1)
G can be pre-calcualated and stored.