CodeChef Contest - UIET2020


EDITORIAL
PROBMLEM SETTERS @anon79686295 @dcpandey

SOLUTION

1.Binod and Chocolates(ZEN1)- Check if any of A, B, or A + B is divisible by 3. The answer is Impossible only for A ≡ B ≡ 1 mod 3 or A ≡ B ≡ 2 mod 3.

2.Neha and Destination(ZEN2)- She can take steps from (x,y) to (x+1,y) .So She can take steps from (0,0) to (1,0). Number of moves is 1 and is the optimal solution.

3.Alien and Primes(ZEN3)- Every Number can be represented in the form of (6k+i) where i is in between 0 to 5.So any number can be represented in atleast one of the forms 6k , 6k+1 , 6k+2 , 6k+3 ,6k+4 , 6k+5. Out of these numbers 6k +2 , 6k+4 are divisible by 2 and 6k +3 , 6k are divisible by 3. So the remaining are 6k+1 and 6k+5. 6k+5 can also be represented by 6k-1. So we can check first that the number is visible by 2 or 3,if so then return false.else check further starting from i=5(for, k==1, 6k-1=5) and till sqrt(n) that n%i is zero or n%(i+2) is zero or not.if yes at some time then return false.else increment i by 6.time complexity for checking a number prime or not is O(√(n/6))

4.Save the Mumbai(ZEN4)- 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.

5.Interesting Game(ZEN5)- If you are at position ‘x’, then you can win by forcing the opponent to be in a losing position if any of the set elements lead to a position ‘x-a[i]’ where he loses(or not wins). Thus we obtain a recursion in which memorisation would help.

6.Zenny and Segments(ZEN6)- Sort the segments by the left end in non-decreasing order and if the left end is the same, sort by the right end in non-increasing order.
Fix the starting point, say SS, and considering all segments starting before or at SS, suppose we have the endpoints of these segments. Then K-th from the rightmost direction is the maximal right end, say EE for the given starting point. Fix the left end of all segments as the starting point and find out K-th rightmost end. The answer is just max(S-E)max(S−E) for all values of SS.

MOVE PROBLEMS TO PRACTISE SECTION
@admin