### Coding Contest 21 Editorial

Posted:

**Sat Apr 28, 2018 2:19 pm**Contest Link: https://www.devskill.com/ContestArchive ... d5a905ecff

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

Problem A: Tweety String

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

Problem Setter: Bishal Gautam

Alternate Writer: Suman Bhadra, Shakil Ahmed, Bir Bahadur Khatri

In this problem, You are given a string of length N, say S. Your task is to determine whether the sum of ascii values of all characters in given string is divisible by 20.

We can easily get ascil value of a character by typecasting character to integer. Now, we calculate the summations of all these ascii values. Finally, we can use if/else condition to check whether the summation is divisible by 20 or not.

Problem B: Pile game 1

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

Problem Setter: Bishal Gautam

Alternate Writer: Bir Bahadur Khatri ,Bishal Gautam

In this problem, Alice and Bob are playing a new pile game. Initially on the table, there are N piles. Each time, the player has to take 2^i piles (i ≥ 0). The winner is the one who takes the last pile. Alice starts first, and you need to find the winner of the game.

This was a simple observation problem. If we observe the scenario, we can easily notice that if N is divisible by 3 then Bob will win the game, otherwise Alice will win it.

Overall Time Complexity: O( T )

Problem C: Boro vai ... trt chai..!!

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

Problem Setter: Md. Abul Kalam Azad

Alternate Writer: MD Musfiqur Rahman Sanim, Bir Bahadur Khatri , Bishal Gautam

In this problem, you have to find nth positive number such that it has at least 3 distinct prime factor.

It can be solved using the similar technique of Sieve of Eratosthenes. Take each prime number and try to see which number it divides. Increment the array value if a number if it is divided by a prime number. Then check which array value has greater than or equal to 3. This is our numbers which has three or greater distinct prime factors. Preprocess all the result and answer each test case in O(1).

Overall Time Complexity: O( n ) (asymptotic)

Problem D: Sanvi and Card Game 2

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

Problem Setter: Md. Tariqul Islam

Alternate Writer: Bir Bahadur Khatri, Mahmud Allahverdiyev , Bishal Gautam

The problem can be describes as , you're given an array , how many ways you can rearrange the array so the sum of absolute difference between adjacent item is maximum.

Let's assume given an array a of size n,Consider S={0,1,2,..,n-1} as a set of indices, and we can represent any subset of S by a binary mask mask.

I'll use the set notation bellow.

For simplicity we'll call score of a permutation of any set is the sum of absolute difference between adjacent item in the permutation. A set can have exactly |S|! different permutation. We're gonna find out how manys of them produce maximum score.

Consider a function F defined as, F(i,S)=Maximum score for the set S such that the permutation begin's with i'th element of the array and S does not include i.

It means given a First element, arrange the element from the set so the score is maximum. We can recursively define F.

The problem with the function is, we don't know which element to is begin with. We can try all element as First element so

Function F is not out solution , actually it's the solution for DCP-305: Sanvi and Card Game . But we need this function for our solution. Let's consider another function G,

G is our counting function, But not quite the solution. cause , as same as F, we don't know which index to begin with.But As same as F, we can try them all

Time Complexity: O( n*2^n)

Problem E: Prime Size Squares Inside Rectangle

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

Problem Setter: Fahim Shahriar Shakkhor

Alternate Writer: Mahmud Allahverdiyev, Bir Bahadur Khatri , Bishal Gautam

You have a rectangular grid of size n x m. Find the total number of different possible squares in it whose sides are aligned to the sides of the rectangular grid and the length of the side of the square is a prime.

Explanation: If we fix the length of the square to i,then there are (n-i+1)(m-i+1) such squares.

(n - i + 1)(m - i + 1)

= (nm + n + m + 1) - i(n + m + 1) + i ^2

Let x = min(m,n) be maximum length of any square in the grid. So, for the first term , we need to calculate the number of primes from 1 to x. For the second term, we need to calculate the sum of primes in the range. For the third term , we need to calculate the sum of squares of the primes in the range.

Complexity: O(N * log(N) * log(log (N)) + T)

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

Problem A: Tweety String

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

Problem Setter: Bishal Gautam

Alternate Writer: Suman Bhadra, Shakil Ahmed, Bir Bahadur Khatri

In this problem, You are given a string of length N, say S. Your task is to determine whether the sum of ascii values of all characters in given string is divisible by 20.

We can easily get ascil value of a character by typecasting character to integer. Now, we calculate the summations of all these ascii values. Finally, we can use if/else condition to check whether the summation is divisible by 20 or not.

Problem B: Pile game 1

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

Problem Setter: Bishal Gautam

Alternate Writer: Bir Bahadur Khatri ,Bishal Gautam

In this problem, Alice and Bob are playing a new pile game. Initially on the table, there are N piles. Each time, the player has to take 2^i piles (i ≥ 0). The winner is the one who takes the last pile. Alice starts first, and you need to find the winner of the game.

This was a simple observation problem. If we observe the scenario, we can easily notice that if N is divisible by 3 then Bob will win the game, otherwise Alice will win it.

Overall Time Complexity: O( T )

Problem C: Boro vai ... trt chai..!!

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

Problem Setter: Md. Abul Kalam Azad

Alternate Writer: MD Musfiqur Rahman Sanim, Bir Bahadur Khatri , Bishal Gautam

In this problem, you have to find nth positive number such that it has at least 3 distinct prime factor.

It can be solved using the similar technique of Sieve of Eratosthenes. Take each prime number and try to see which number it divides. Increment the array value if a number if it is divided by a prime number. Then check which array value has greater than or equal to 3. This is our numbers which has three or greater distinct prime factors. Preprocess all the result and answer each test case in O(1).

Overall Time Complexity: O( n ) (asymptotic)

Problem D: Sanvi and Card Game 2

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

Problem Setter: Md. Tariqul Islam

Alternate Writer: Bir Bahadur Khatri, Mahmud Allahverdiyev , Bishal Gautam

The problem can be describes as , you're given an array , how many ways you can rearrange the array so the sum of absolute difference between adjacent item is maximum.

Let's assume given an array a of size n,Consider S={0,1,2,..,n-1} as a set of indices, and we can represent any subset of S by a binary mask mask.

I'll use the set notation bellow.

For simplicity we'll call score of a permutation of any set is the sum of absolute difference between adjacent item in the permutation. A set can have exactly |S|! different permutation. We're gonna find out how manys of them produce maximum score.

Consider a function F defined as, F(i,S)=Maximum score for the set S such that the permutation begin's with i'th element of the array and S does not include i.

It means given a First element, arrange the element from the set so the score is maximum. We can recursively define F.

- Code: Select all
`F(i,S)= 0 if S is empty`

max{abs(a[i]-a[j]) + F(j,S-{j})} for all j in S Otherwise

The problem with the function is, we don't know which element to is begin with. We can try all element as First element so

- Code: Select all
`S={0,1,2,...,n-1}`

optimal score for input array = max{F(i,S-{i})} for i= 0 to n-1

Function F is not out solution , actually it's the solution for DCP-305: Sanvi and Card Game . But we need this function for our solution. Let's consider another function G,

- Code: Select all
`G(i,S)=1 if S is empty`

sum{G(j,S-{j})} for those j in S for which F(i,S) is optimal, ie abs(a[i]-a[j]) + F(j,S-{j})==F(i,S)

G is our counting function, But not quite the solution. cause , as same as F, we don't know which index to begin with.But As same as F, we can try them all

- Code: Select all
`res=sum{G(i,S-{i})} for those i for which F(i,S-{i}) is optimal.`

Time Complexity: O( n*2^n)

Problem E: Prime Size Squares Inside Rectangle

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

Problem Setter: Fahim Shahriar Shakkhor

Alternate Writer: Mahmud Allahverdiyev, Bir Bahadur Khatri , Bishal Gautam

You have a rectangular grid of size n x m. Find the total number of different possible squares in it whose sides are aligned to the sides of the rectangular grid and the length of the side of the square is a prime.

Explanation: If we fix the length of the square to i,then there are (n-i+1)(m-i+1) such squares.

(n - i + 1)(m - i + 1)

= (nm + n + m + 1) - i(n + m + 1) + i ^2

Let x = min(m,n) be maximum length of any square in the grid. So, for the first term , we need to calculate the number of primes from 1 to x. For the second term, we need to calculate the sum of primes in the range. For the third term , we need to calculate the sum of squares of the primes in the range.

Complexity: O(N * log(N) * log(log (N)) + T)