Coding Contest-16 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-16 Editorial

by BishalG » Wed May 31, 2017 10:37 am

Contest Link: ... d499a2b4f0
Ranklist of contest: ... d499a2b4f0

Problem A: Help Pritom Finding Prefix LCM
Problem Setter: UIU-Abdullah Al Rifat

The Problem was to find LCM but not just only 2 numbers but of multiple numbers in a range . so it's like prefix LCM.
we just have to implement the Prefix algorithm like the prefix sum . like consider there are 3 numbers in my array and they are 2 4 5 and there will be 3 queries and for every query we just have to find the lcm from index 1 to the k index .in the sample input first one is 1 and from index 1 to 1 there is only 1 number and that is 2 so the lcm of 2 is the output is 2. in 2nd line k=2 so from index 1 to 2 there is 2 numbers 2 and 4 .and the lcm of 2 and 4 is 4 so the output is 4 .just like that on 3rd line lcm of 2,4,5 is 20 so the output is 20.
we just have to save the lcm value from index 1 to kth index into the kth index Or one can simply iterate over 1 to k in each query and find the value of lcm. How to find LCM is left over you.

Complexity: O(nlogn)

Problem B: String Frequency Query
Problem Setter: Bishal Gautam

In this problem, you are given a string S, consisting of lowercase English alphabets. You should perform 2 types of quries:
1.)Change the character at index X to character Y
2.)Print the total number of occurrences of character Y in the string

As length of S is 10^5 and queries are also 10^5. So, iterating over string every time will cause time limit exceeds. So, what you
have to do is to Precalculate the frequency of each character from 'a' to 'z' initially.
And for every query of type-1,just decrease the frequency of character at index-X, and increase the frequency of character 'Y', also
do not forget to replace character at index-X to chracter 'Y'.
And, for every query of type-2, just print the frequency of character 'Y' from precalculated array.

Answering each query: O(1)
Complexity: O(n), where n is maximum among string's length and queries.

Problem C: Again Egg, Banana and Bread
Problem Setter: Bishal Gautam

This problem is a hard version of problem "Egg, Banana and Bread" ( ) used in Easy coding contest -11.

In this problem, you are given X,Y,Z and T. and we have to find the maximum amount which is less than or equal T, that can be made taking X,Y,Z in strictly increasing numbers. i.e number of ( X< Y < Z ).

In case, you can not fulfill above mentioned condition, you have to print -1.

So, If money T is less than 3*Z+2*Y+X ,then we can not buy maintaining above constraint. This is the case of -1.

Now, firstly we take 3 Z, 2 Y and 1 X. after that, we have 3 options, either take 1 Z, OR take 1 Y along with 1 Z, OR take 1 X along with 1 Y and 1 Z, which will ensure the condition of strictly increasing order.

so, we can simply assume X, X+Y and X+Y+Z as coins and perform a coin change DP on it .

Code: Select all
if t<0, print -1.
coin[0] <-- x+y+z,
coin[1] <-- y+z,
coin[2] <-- z,

dp[0]<-- 1.
for i=0 to 3
  for j=coin[i] to t
          dp[j] | =dp[ j- coin[i] ]
     end do
   end for
end for

for i=t to 0 dec
  if dp[ i ]:
     print t-i,
end for

Complexity: O( TC*3*T )

Problem D: Critical Encryption
Problem Setter: Mohammad Abdullah Matin Khan Zarzis

In this problem, you will be given a list of encrypted numbers, you are to decrypt them. Sometimes the transmitted message may become corrupted that is decrypted numbers might not be prime numbers, these are invalid messages. Also, If there exists only one number in the list, then you can not decrypt it.

Explanation: Core idea involved in this problem is to find the GCD of given sequence. This can be done using Euclid's GCD algorithm. If the GCD is 1 then the sequence is invalid according to the problem statement. If any divisor of GCD is chosen other than GCD itself, then decoded numbers will not be prime, so the multiplier must be the GCD of given sequence. Now, divide the sequence with their GCD, that's the decoded message. If any number in the decoded sequence is not prime then also the given sequence is invalid. Now, here comes the main challenge of our problem. You have to use Miller-Rabin primality test to check primality of big numbers.

Wikipedia: Miller-Rabin Primality Test=> ... ality_test
Implementation=> ... ler-rabin/"
Reviewer's Implementation:

Problem E: Reconstructing Blue Print of Life
Problem Setter: Md. Khairullah Gaurab

We can solve the problem with two steps. First let’s consider an M. Where for position i of string S in M[i] we will store the length of the longest substring of S[0-i] that we can add after position of S[i].

We can do it in (N/2)^2 for worst case scenario (a string containing all the same character) if we build a Suffix Automata of the Given string S provided it’s construction time is linear. [NB: Judge Input is constructed as such the calculation of array M requires not more than Nxlog2(N) ].

Now provided the array M we can use a dynamic programming approach to find the minimum amount with N complexity.

The DP will have only one parameter pos. From each pos we can jump to pos+1 adding a single character or jump to any of the positions from 2 to min(M[pos],K).

So the overall time complexity of judge solution is O(T x {Nxlog2(N) + N}) .
This problem can also be solved in O(T x N x (log2(N))^2 ) complexity.

Note: Few unexpected and randomized solutions passed within time limit.Sorry for that. If you are one of them, please try to upsolve them with expected complexity. 8-)
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