### Coding Contest 19 Editorial

Posted:

**Mon Feb 05, 2018 1:00 pm**Contest Link: https://www.devskill.com/ContestArchive ... d55bd16668

Contest Ranklist: https://www.devskill.com/home/contestra ... d55bd16668

Problem A: Gain Dev Shop Coin

Link: https://devskill.com/CodingProblems/ViewProblem/313

Problem Setter: Bishal Gautam

Alternate Writer: Suman Bhadra, S.M Shaheen Sha, Bir Bahadur Khatri

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.

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?

Link: https://devskill.com/CodingProblems/ViewProblem/418

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

Link: https://devskill.com/CodingProblems/ViewProblem/386

Problem Setter: Suman Bhadra

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:

So, the Answer will be:

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

Link: https://devskill.com/CodingProblems/ViewProblem/386

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.

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

Problem E: Gold is real returns

Link: https://devskill.com/CodingProblems/ViewProblem/460

Problem Setter: Bir Bahadur Khatri

Alternate Writer: Mahmud Allahverdiyev, Md. Tariqul Islam , Bishal Gautam

We know there will be at most 15 root nodes. Simply we can solve this problem using bitmask dp. Dp[Msk][prv], stores the maximum GoldValue possible in all possible permutation of current mask (Msk, stores the details of used root nodes), where last used root is prv. Now we can choose any root from remaining ones.

We need to pre calculate that Pre [ Msk ] [ nxt ], which means number of gold collected if taken root’s mask is Msk and next node is nxt. We can calculate this as, Number of gold collected using all root nodes of Msk and nxt MINUS Number of gold collected using all root nodes of Msk. This precalculation can be done in 2^15*N, Where N is number of nodes in DAG.

For each of the test cases:

Time complexity: O (2^15 * N) + O (2^15 * 15)

Memory complexity: O (2^15 * N).

Contest Ranklist: https://www.devskill.com/home/contestra ... d55bd16668

Problem A: Gain Dev Shop Coin

Link: https://devskill.com/CodingProblems/ViewProblem/313

Problem Setter: Bishal Gautam

Alternate Writer: Suman Bhadra, S.M Shaheen Sha, Bir Bahadur Khatri

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?

Link: https://devskill.com/CodingProblems/ViewProblem/418

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

Link: https://devskill.com/CodingProblems/ViewProblem/386

Problem Setter: Suman Bhadra

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.

So, the Answer will be:

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

Link: https://devskill.com/CodingProblems/ViewProblem/386

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

Link: https://devskill.com/CodingProblems/ViewProblem/460

Problem Setter: Bir Bahadur Khatri

Alternate Writer: Mahmud Allahverdiyev, Md. Tariqul Islam , Bishal Gautam

We know there will be at most 15 root nodes. Simply we can solve this problem using bitmask dp. Dp[Msk][prv], stores the maximum GoldValue possible in all possible permutation of current mask (Msk, stores the details of used root nodes), where last used root is prv. Now we can choose any root from remaining ones.

We need to pre calculate that Pre [ Msk ] [ nxt ], which means number of gold collected if taken root’s mask is Msk and next node is nxt. We can calculate this as, Number of gold collected using all root nodes of Msk and nxt MINUS Number of gold collected using all root nodes of Msk. This precalculation can be done in 2^15*N, Where N is number of nodes in DAG.

For each of the test cases:

Time complexity: O (2^15 * N) + O (2^15 * 15)

Memory complexity: O (2^15 * N).