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

Easy Coding Contest 17 Editorial

by BishalG » Mon Mar 12, 2018 10:04 am

Contest Link: https://www.devskill.com/ContestArchive ... d5831aa4c1
Contest RankList: https://www.devskill.com/home/contestra ... d5831aa4c1

Problem A: Wink or Kick
Link: https://devskill.com/CodingProblems/ViewProblem/500
Problem Setter: Avik Sarkar
Alternate Writer: Bishal Gautam, Bir Bahadur Khatri, Mahmud Allahverdiyev

In this problem, you have to find whether A is divisible by B or not? If divisible print :wink: or print :kick: .
Just figure out whether A%B is equal to 0 or not ?
The only case you have to handle when the value of B will be 0. Then it will be :kick: . :lol:

Problem B: Mr. Typical
Link: https://devskill.com/CodingProblems/ViewProblem/483
Problem Setter: Humaun Kabir
Alternate Writer: Bishal Gautam, Bir Bahadur Khatri, Mahmud Allahverdiyev

In this problem, you have to check a word in a long string.
This problem is pretty straightforward. You should read the statement carefully and store the quote of Mr. Typical's grandfather in an array or in a string. You can parse strings using stringstream in c++ or you can do it manually.
After taking input search the word in the array or string. Check the word with a condition and if it is matched print "YES" and if not print "NO". :)

Problem C: Minimum Cost
Link: https://devskill.com/CodingProblems/ViewProblem/420
Problem Setter: Bishal Gautam
Alternate Writer: Suman Bhadra, Shakil Ahmed, Musfiqur Sanim

In this problem, you are given an array with N integer numbers. Your task is to make all the element value same. In each move, you may select any index and decreases the value of that index by 1. You have to print the minimum numbers of moves needed to make all the array element same.
Since, we can only decrease value of element , so we can easily see that making all elements equal to minimum element of the array will be beneficial idea. So, we just need to print the summation of difference of every element with minimum one. :roll:

Problem D: Fun With Fibonacci
Link: https://devskill.com/CodingProblems/ViewProblem/389
Problem Setter: Razibul Hasan Mithu
Alternate Writer: S.M Shaheen Sha, Bir Bahadur Khatri, Mahmud Allahverdiyev

In this problem, you have to find number of Odd and even number between a range in Fibonacci series.
Its a simple Fibonacci pattern.You have to find how many odd and even number between N to M. Here is a tricks, if you go to generate Fibonacci series, then you will get TLE :oops: . Every even number come back after two odd number, so it is enough to solve this problem with O(m-n). 8-) 8-)
There also exist a O( 1 ) solution. Think about it !!!

Problem E: Digit Sum Queries
Link: https://devskill.com/CodingProblems/ViewProblem/498
Problem Setter: Emrul Chowdhury
Alternate Writer: Bishal Gautam, Bir Bahadur Khatri, Mahmud Allahverdiyev

There are several ways to solve this problem as the time limit is not so strict.
We need to find the maximum Sum of Digit of a element between a range. For that, we may use two ways :-

Segment Tree : We can easily get the maximum SOD between any rang L-R. There is plenty of good tutorial about segment tree in internet.
Cumulative Sum : As the maximum SOD will not exceed 54, we can use 2D cumulative sum basis on Sum of Digit.

As segment tree solution is pretty common, let’s discuss about the second approach.

Let, CumulativeSOD as a 2D array, let build this array for 0 <= i <= 54 where i is all possible SOD and 1 <= j <= N which denotes all the indexes of the array.
Assume, CumulativeSOD[i][j] = 1 if the jth element of the array have the SOD equal to i, otherwise CumulativeSOD[i][j] = 0.

Now, you need to calculate cumulative sum of that array by using the formula CumulativeSOD[i][j] = CumulativeSOD[i][j] + CumulativeSOD[i][j-1].

For each query, for any i ( 0 <= i <= 54 ), if the partial sum, CumulativeSOD[i][R] - CumulativeSOD[i][L-1] is greater than or equal to 1, you simply observe that there is at least one index exists where the SOD of that index’s element is i. So you have to choose the maximum value which are existing for this query.

Now after finding the MaxSOD, you have to find the index where the MaxSOD exits. For that, we can apply Binary Search. Use a 2D vector to store indexes for the specific SOD. Then, for each query, find the smallest index holding the MaxSOD using Binary Search. :ugeek: :ugeek:
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