Coding Contest 21 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)

Coding Contest 21 Editorial

by BishalG » Sat Apr 28, 2018 2:19 pm

Contest Link: ... d5a905ecff
Contest Ranklist: ... d5a905ecff

Problem A: Tweety String
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
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..!!
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
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
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
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)
User avatar
Posts: 43
Joined: Tue Jan 17, 2017 10:10 pm

Re: Coding Contest 21 Editorial

by feodorv » Sun Apr 29, 2018 9:14 am

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

It seems to me that the correct value is
Code: Select all
(nm + n + m + 1) - i(n + m + 2) + i ^2

Let x = min(m,n) be maximum length

Seems you mean minimum length...
Posts: 11
Joined: Thu Jun 15, 2017 3:37 pm

Who is online
Users browsing this forum: No registered users and 1 guest