Coding Contest 17 - Editorial

All contest related discussion goes here. Both Dev Skill and Non Dev Skill contest related discussion is allowed. (But please keep the forum clean)

Coding Contest 17 - Editorial

by BishalG » Sun Jul 02, 2017 4:35 pm

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. :P
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. 8-)

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,
Image

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

M should be an integer so M should be,

Image

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. :roll:


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: :ugeek:
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),

Image


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). :geek:
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.
User avatar
 
Posts: 43
Joined: Tue Jan 17, 2017 10:10 pm

Re: Coding Contest 17 - Editorial

by arabin07 » Thu Jul 06, 2017 11:26 am

DCP-375: Smallest Palindromic Substring

My solution shows W/A can anyone help me please
Code: Select all
#include <stdio.h>
#include <string.h>
int main(int argc, const char * argv[]) {
   
    int T,i,j,k;
    scanf("%d\n",&T);
    char answer[T], string[21], ch, ch1, ans = 0;
   
    for (i = 0; i<T; i++) {
        fgets(string, 21, stdin);
        size_t len = strlen(string);
        //printf("%s%zu\n", string,len);
       
        ch = *(string);
        for (j = 1; j<len-1; j++) {
           
            ch1 = string[j];
           
            if (ch>=ch1) {
                ans = ch;
            }
            else{
                ans = ch1;
                ch = ch1;
            }
        }
        answer[i] = ans;
    }
    for (k = 0; k<T; k++) {
        printf("%c\n", answer[k]);
    }
   
    return 0;
}
 
Posts: 5
Joined: Wed Jul 27, 2016 11:04 pm

Re: Coding Contest 17 - Editorial

by BishalG » Wed Jul 12, 2017 2:25 pm

@arabin07 ,
You may test your code with following input:
2
a
z
User avatar
 
Posts: 43
Joined: Tue Jan 17, 2017 10:10 pm


Who is online
Users browsing this forum: No registered users and 0 guests
cron