Page 1 of 1

### Easy Coding Contest-14 Editorial

Posted: Mon Nov 06, 2017 12:18 pm
Standings: https://devskill.com/home/contestrankli ... d52054cd43

Problem A: Gang of Vowels
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=0for 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
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.

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
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
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) .
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)

Problem E: Sanvi and Brightest Bulb