Easy Coding Contest-14 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)

Easy Coding Contest-14 Editorial

by BishalG » Mon Nov 06, 2017 12:18 pm

Contest Link: https://devskill.com/ContestArchive/Con ... d52054cd43
Standings: https://devskill.com/home/contestrankli ... d52054cd43

Problem A: Gang of Vowels
Link: https://devskill.com/CodingProblems/ViewProblem/439
Problem Setter: Emrul Chowdhury

In this problem,you are given a string s consisting only lowercase letters. Count how many Gang of Vowels in the given string exists.
All the vowels in consecutive indexes of a string is a single Gang of Vowels.
You can solve this problem simply looping over the string and whenever you get a vowel try to take as many as vowels letters continuously and count them as a segment(Gang). The answer is total counts. :)

Pseudocode:
Code: Select all
 
var N=Length(s)
var Count=0
for i from 1 to N:
        if s[i] is vowel:
                Count++;
                while( i<N and IsVowel( s[i] ) ):
                    do
                        i++;
                end while
        end if
 end for

Complexity: O(N)



Problem B: Square of N
Link: http://devskill.com/CodingProblems/ViewProblem/394
Problem Setter: Mohibur Rahman

In this problem input only one number N that contains only digit 9 and length of number could be upto 100. Output should be the square of the number N.That means if input is 99 then output is 9801( 99*99) . If input is 9999 then output is 99980001.
Here N can have at most 100 digits. so, at first you have to take input in a string rather than other data types.
After that a simple observation pattern will work here. :geek: :geek:

That means , If the input has n digit then the answer will be:
first n-1 digit 9 -> next one digit 8 -> next n-1 digit 0 -> last one digit 1



Problem C: Page Number
Link: http://devskill.com/CodingProblems/ViewProblem/441
Problem Setter: Monikrishna Roy

In this problem, Given N as the number of pages of first day he read, And have to find the day which day he read the Kth page.
You can just simulate the process as mentioned in the problem statement. Calculate the final page number after each day. After each day check the final page is it equal or large to the given page? If yes, then this day is our required answer. :)

Pseudocode:
Code: Select all
 
input n,k;
  final = n;
  last_day = n;
  days = 1;
  while(final < k):
        final  = final + last_day *2;
        days = days +1;
        last_day  = last_day*2;
  print days;

Complexity: O( T*logN )



Problem D: Want a Bride in This Winter
Link: http://devskill.com/CodingProblems/ViewProblem/442
Problem Setter: Avik Sarkar

In this problem, You need to tell whether it is possible to have exactly K numbers between 1 to N such that A^2 + A^3 will be a square number where 1<= A <= N.

Idea 1: Run a loop from A = 1 to 10^5 and calculate A^2 + A^3 and save in an array if the sum is a square number. Now, check whether the location of N in that array . If the location is at K then print "I am married now" else print "Baba amar ki biye hobe na" . :)

Complexity: O(T*315)

Idea 2: Pre-calculate for each A from 1 to 10^5 and print result for each N at O(1) . 8-)
Complexity: O(10^5) + O(T)

Idea 3: As given, A^2+ A^3 you can simplify it as A^2*(1 + A ). As the result should be a Square Number then (1 + A ) should be a square number. So, do square root of (1 + A) and decrease once. If the result is equal to K print as stated in the statement else print the otherwise. Why we need to decrease 1. As (1 + A) is square not just A that's why we need to reduce 1.
Complexity: O(T) :P



Problem E: Sanvi and Brightest Bulb
Link: http://devskill.com/CodingProblems/ViewProblem/419
Problem Setter: Bishal Gautam

In this problem, you are given the brightness power in watt (Wi) of each bulb from 1 to N. You have to determine the minimum distance she needs to walk on the right side of the corridor so that she could get the brightest bulb in the range from position i to N.
So, basically from each position i, you have to compute minimum distance to maximum value in the range from i to N.

A bruteforce approach may be for each i, loop from index i to N and find the minimum index of maximum element in that range. so, answer will be equal to that index minus i. The complexity of this approach will be O(T*N*N), which will certainly not pass within time limit. :roll:

So, expected solution is to looping from N to 1 and holding the index of current maximum encountered so far. Hence the answer will be equal to that index minus i for every i from 1 to N. :P
So, overall complexity will be: O( T*N ).
User avatar
 
Posts: 43
Joined: Tue Jan 17, 2017 10:10 pm

Who is online
Users browsing this forum: No registered users and 1 guest
cron