Page 1 of 1

### Coding Contest 19 Editorial

Posted: Mon Feb 05, 2018 1:00 pm
Contest Ranklist: https://www.devskill.com/home/contestra ... d55bd16668

Problem A: Gain Dev Shop Coin
Problem Setter: Bishal Gautam

Actually, This problem was based upon rules of Dev Skill for awarding any problem contributor in Dev Skill. As said in the problem statement, anyone can submit problem and if it becomes ready for the contest, then problem setter will get Shop Coin based upon the complexity of problem.

Easy Problem - 20 Dev Coin.
Medium Problem - 40 Dev Coin.
Hard Problem - 68 Dev Coin.

Since, every input string are separated by a space between two words. So, you have to scan a line of string. Then, check 3 conditions for Dev Coin based upon above given information.

Problem B: Can You Answer Me?
Problem Setter: Bishal Gautam
Alternate Writer: Shakil Ahmed, Mahmud Allahverdiyev , Bir Bahadur Khatri

In this problem, you are given an array A of length N. You have to count total pairs whose multiplication value will be a perfect square number. Perfect Square is a number N such that there exists two integer numbers X and Y, not necessarily different, such that X*Y=N.
The key thing in this problem is that every values are less than or equal to 100 . So, for every positions , you may easily iterate over possible value of perfect numbers(total 100) and count how many pairs are there to the left which would help current number to be that particular perfect number. We can easily use an array for storing frequency of every values.

Overall Time Complexity: O( T*N*100 )

Problem C: Lucky Number
Alternate Writer: MD Musfiqur Rahman Sanim, Mahmud Allahverdiyev , Bishal Gautam

In this problem you are given two integer value A and B where A≤B. How many numbers are between them which are lucky numbers. An integer number N is a lucky number if it is neither a square nor a cube of any integer number.
Basically, you have to find the number of number from A to B where they are not cube or square.
We can do this problem by following steps:

Find Number of integers between A and B.
Find numbers of square number between them
Find numbers of Cubic numbers between them.
Finally we have to calculate the numbers of square and cubic number at a time.

Answer = B - A + 1 - number of square number - number of cube number + number of cube and square numbers.

You have to apply binary search properly in the intermediate calculations.

Overall Time Complexity: O( T*LogN )

Problem D: Rectangle
Problem Setter: Md. Tariqul Islam
Alternate Writer: MD Musfiqur Rahman Sanim, Mahmud Allahverdiyev , Bishal Gautam

In this problem, you have given N sticks of various length. you have to make a rectangle with maximum possible area with given constraints. Please read the problem statement fully and try to utilize the constraints given in problem.

Constraint of this problem leads to an easy solution . A 5 stage dp will pass easily.
Assume sticks are numbered from 0 to n-1.
Lets Define dp(i,a,b,c,d) is the solution where i have stick i to n-1 and a,b,c,d are four side I currently have. I can add ith stick to any of these four side or I can completely ignore ith stick.
since these design guarantee that each four side will have every possible length including 0 and the total sum of all length.(Actually each side is a subset sum, like traditional knapsack problem) So we can safely assume a and b is parallel and c and d is parallel. so the base case will be when i=n , we got four side, if two parallel side is equal we can make our rectangle otherwise not.

According to this design dp(0,0,0,0,0) is our solution to the main problem.

Code: Select all
`dp(i,a,b,c,d)= a*c           if i==n and a==b and c==d         = 0             if i==n but a!=b or c!=d         = max(dp(i+1,a+s[i],b,c,d),dp(i+1,a,b+s[i],c,d),dp(i+1,a,b,c+s[i],d),dp(i+1,a,b,c,d+s[i]),dp(i+1,a,b,c,d)) otherwise`

Time Complexity: O( n*SUM^4 ) , where SUM is the total length of all sticks.

Problem E: Gold is real returns