Authors, Testers and Editorialists :-
Omkar Prabhu , Ninad Chavan, Rahul Sawantdesai
1) TCQF19A - Turing During Elections
Difficulty - Cakewalk
Type - Implementation
Prerequisites - None
Explanation -
For each person’s dominance factor, take the absolute value of subtraction of dominance values with A and B respectively.
Increment the vote count of the candidate with whom the absolute value of subtraction is less.
In case if they are equal check which candidate has less votes and accordingly increment the count for the candidate with less vote counts.
In case if the counts are also equal, increment the vote count of candidate A.
Finally, print “A” if A’s vote count is greater. Else print “B” if B’s vote count is greater.
Else, print “tie”.
2) TCQF19B - Alan And Rotors
Difficulty - Cakewalk
Type - Math, Implementation
Prerequisites - None
Explanation -
Here, we run a loop until N/X>0 and M>0.
The machine can only use rotors in bundle of X, thus N/X > 0 ensures that the loop is not running when the remaining no. of rotors are less than X.
M>0 ensures that we are not running the loop when we run out of energy.
In the loop, in each iteration,
- Keep adding the Y hours to the total time
- Since X rotors are used change N to N-X
- Reduce 1 unit of energy from M
Solution Code Link
Alternate Fast Solution Link
3) TCQF19C - The Birthday Game
Difficulty - Easy
Type - Bitwise, Math
Prerequisites - Property of Bitwise XOR
Explanation -
Property of XOR used :-
If, A ^ B = C
Then, C ^ B = A
Here, X is N ^ 23061912.
Therefore, N=X ^ 23061912
You will get Y by, Y = N 10000
Remove the digits indicating the year from N by, N = N / 10000
You will get M by, M = N 100
Remove the digits indicating the month from N by, N = N / 100
The remaining digits are the date, therefore, D = N
Solution Code Link
Alternate Solution Link
4) TCQF19D - Connect The Dots!
Difficulty - Easy
Type - Geometry, Math
Prerequisites - None
Explanation -
For finding the no. of connecting lines:
If 2 * D = N, then there will be only one connecting line.
Else it can be observed that, the no. of connecting lines will be = N / GCD(N,D)
Where GCD stands for Greatest Common Divisor
For calculation GCD, you can use the inbuilt gcd functions in the language libraries or use the Euclidean GCD Algorithm
5) TCQF19E - Alan And Frames
Difficulty - Easy
Type - Sorting, Greedy
Prerequisites - O(N * logN) Sorting Algorithm/Function
Explanation -
Store the radii of rotors and circular frames after multiplying them by 2, since we are comparing sides of square frames with twice of radius.
Here, to store the values we use an array of pairs of size S+C. In the first field, we store all the side lengths of square frames and doubled radii of circular frames.
In the second field, for circular frames we store value 1 and for square frames we store value 2.
Now sort the array. This will help us find the least cost frames first and in case if the costs are equal, due to the second field, we will obtain circular frames first.
Now sort the array of rotors according to their doubled radii.
Now, Iterate through the rotors array and the frames array together assigning each rotor to a frame when eligible. This will always make sure that the least cost frame is used.
6) TCQF19F - Countries and Friends
Difficulty - Easy
Type - Sorting, Binary Search
Prerequisites - Binary Search Algorithm
Explanation -
It’s observable that the names of the countries is an useless data, so we can ignore it.
Create an array of pairs and store the data as follows.
For every friend, add the distance of each of his/her favourite country in the first field, add the friend’s name in the second field.
Sort this array so that it is sorted with respect to first field and then the second.
Perform a binary search for the first element in this array with distance greater than or equal to the distance given in the query. If found, print the friend’s name present in the second field of that element. If not found, print “NA”.
7) TCQF19G - The Enigma
Difficulty - Medium
Type - Substring Search, Dynamic Programming
Prerequisites - KMP search algorithm, DP - 0/1 Knapsack Problem
Explanation -
This Problem can be interpreted as the 0/1 Knapsack Problem.
The Power Capacity of the Machine can be taken as the Weight of the Knapsack.
The length of the Words as the Weights of the Objects.
The number of their occurrences as the Prices of the Objects.
The number of occurrences cannot be found using slow search algorithms since the constraints are large. So we use the KMP search Algorithm
The Minimum Power used with the same speed can be looked up in the DP table formed