Contest Link: https://devskill.com/ContestArchive/Con ... d4b01832d1

Contest Ranklist: https://devskill.com/home/contestrankli ... d4b01832d1

Problem A: Smallest Palindromic Substring

Link: http://devskill.com/CodingProblems/ViewProblem/375

Problem Setter: Bishal Gautam

In this problem, you have given a string , say - S. Your task is to print the smallest palindromic substring in the given string.

If there are more than one solution, print the one which is lexicographically largest . A word is lexicographically larger than

another if it comes later in dictionary order.

We may easily notice that, every single character in the string are itself a palindrome.

So, idea is to iterate over string and find out a single character which have higher ascii value.

Complexity: O(TC*N)

Problem B: SUMMATION

Link: http://devskill.com/CodingProblems/ViewProblem/379

Problem Setter: Suman Bhadra

In this problem you have to find the summation of all possible sub sequence summation of the given array. We know that,

Subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order

of the remaining elements. there will be total 2^n subsequences of an array of length n. Here, every number should be

added to the answer 2^(n-1) times because with the help of (n-1) elements 2^(n-1) sub sequences are possible.

Complexity: O(n)

Problem C: Cheat the Lottery

Link: http://devskill.com/CodingProblems/ViewProblem/356

Problem Setter: MD Musfiqur Rahman Sanim

We know there are N people. So when organizer starts giving prize the probability of getting each ticket buying person is 1/N.

When one prize is given the probability of getting each ticket buying person remaining N-1 people is 1/ (N – 1).

Suppose after giving M prize the probability of each person winning next prize is greater than P.

That’s means,

So you can get the (M+1)th prize. To find M we can normalize the upper equation,

M should be an integer so M should be,

So minimum number of prize need to give is M + 1.

This can also be solve using binary search. But, you should be careful while handling overflow and calculations.

Complexity: O(1) per testcase

Problem D: Sanvi and String Flow

Link: http://devskill.com/CodingProblems/ViewProblem/364

Problem Setter: Bishal Gautam

In this problem you are given a string- S. Two players Sanvi and Manvi are playing game on it. In each move, they select a particular index then changes the character of that index to another one depending upon power of that character but tries to skip the character which may lead to incompletion of game. One who got the string consisting of all characters with alphabet -'a' will loss the game. Sanvi starts playing game first. Your task is to determine the winner of this game If both of them play optimally well. If there arise a situation that nobody can win the game ,then the game will be "Tie".

So, basically they always want Game to be Finished unless there arise a situation that game could not be finished anyhow.

Now, before discussing solution, i recommend to read this article:

https://www.hackerrank.com/topics/game- ... dy-numbers

We may see that Game will be unfinished only if there are some character in the given string which are not reachable to character 'a' at any moves. Only, this is the case for printing "TIE". We can check this easily using BFS/DFS from every character on given string-S.

If we observe carefully, we may see that ascii value of every characters is decreasing by some amount in every moves also relationship among these characters form a directed acyclic graph.We may relate this behaviour to NIM piles where moves for different pile size are different. Since, there are different moves for differnt characters, we have to apply Sprague–Grundy theorem here.

So, we calculate grundy values for each character. Finally, grundy value of character at every index represent nim piles. we determine, winner of the game by applying NIM theory and performing XOR of all values. If XOR is nonzero, first player-Sanvi will win otherwise Manvi will win.

Complexity: O(TC*26*26)

Problem E: CarryCount

Link: http://devskill.com/CodingProblems/ViewProblem/364

Problem Setter: Bir Bahadur Khatri

In this problem, you have to find the number of elements from 1 to N , if we try to add this number to X we will get carry 1 k times.

The problem can be classified as digit dp. If you did not solved any digit dp problem before then please solve some basic digit dp problems first.

To add two numbers, first we will make every number length in string upto 20 . For example add (21,49),

For every number from 1 to N , we will add with x and check how many carry will be created with every numbers with above procedure. So we will start from last position to position zero. Dp states will be ( position, IsnumberIsBig, Previouscarry,RemainingK).

Where

1. Position = Current position

2. IsnumberIsBig = The number we made till this position is Big or not. Number is considered Big if we use big digit at least one position and remaining digits are equal with digits of N.

3. Previouscarry = Last Carry at position=position+1

4. RemainingK = number of remaining carry we have to make.

Base Case (position==-1)

1. return 1 if ( RemainingK==0 && IsnumberIsBig==0) else return 0;

Complexity : O(20*2*2*K ) per test case, here 20 can be handled with 18 also.