Easy Coding Contest 18 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)

Easy Coding Contest 18 Editorial

by BishalG » Mon Apr 16, 2018 10:15 am

Contest Link: https://www.devskill.com/ContestArchive ... d59dcbfb73
Contest RankList: https://www.devskill.com/home/contestra ... d59dcbfb73


Problem A: #ReformQuotaBD
Link: https://devskill.com/CodingProblems/ViewProblem/528
Problem Setter: Bishal Gautam
Alternate Writer: Suman Bhadra, Mahmud Allahverdiyev

In this problem, you have to print "#ReformQuotaBD" without any quote. :lol:



Problem B: FIFA 2030
Link: https://devskill.com/CodingProblems/ViewProblem/517
Problem Setter: Humaun Kabir
Alternate Writer: MD Musfiqur Rahman Sanim, Bir Bahadur Khatri, Mahmud Allahverdiyev

In this problem, you have to find the highest goal achiever team name.
It's pretty straightforward. You have to find the maximum goal and respective team name. You can compare while taking input and define the highest goal achiever team. According to problem "It is guaranteed that there won’t be any tie." So, we will have unique answer. :) :)



Problem C: Gazor and City Hype
Link: https://devskill.com/CodingProblems/ViewProblem/504
Problem Setter: Avik Sarkar
Alternate Writer: Bishal Gautam, Bir Bahadur Khatri, Mahmud Allahverdiyev

In this problem, you have to find (1^N + 2^N + …. + P^N) modulo 5.
The problem can be solved in two ways.
The first one whose complexity O(TlgN) ( where T is the number of test cases ) can be solved by calculating summation the Nth power of each from 1 to P ( as P is smaller ) modulo 5. The Nth power can be calculated using Modular Arithmetic.
The better approach is whose complexity is O(T) ( where T is the number of test cases ) is to figure out a pattern. Just do a brute force calculation for P = 1 to 9 and iterate at most 8 times. That will give you the desired pattern which is just a bunch of if/else. :roll:




Problem D: Amazing string
Link: https://devskill.com/CodingProblems/ViewProblem/521
Problem Setter: Bir Bahadur Khatri
Alternate Writer: S.M Shaheen Sha, Bishal Gautam, Mahmud Allahverdiyev

In this problem, You are given a string S, find how many substrings of S are Amazing string.
Amazing string is a string whose all substrings are palindrome.
The good observation is that amazing string is possible only when all the characters in the string are same.
So, you have to find all the substrings which are formed by same characters. This can be done by iterating over strings and finding the substring with all same characters then paring in between them. :ugeek:


Problem E: Modular Inverse
Link: https://devskill.com/CodingProblems/ViewProblem/527
Problem Setter: Md. Tariqul Islam
Alternate Writer: Suman Bhadra, Mahmud Allahverdiyev, Bishal Gautam

In this problem, you just have to find modular inverse of 2 (mod m). there is some way for finding modular inverse in general cases like extended euclid algorithm. But our case is very special and easy.

As given in statement if gcd(2,m) ≠ 1 , then answer does not exist. and it's only the case when m is a even number.

now if m is a odd number , then gcd(2,m) = 1 , and answer exist . and the answer is (m+1)/2 with no exception.
why?

=> (m+1)=1 (mod m)
=> 2*((m+1)/2)=1 (mod m)


as m is a odd number so m+1 is even and always be divisible by 2.

But the constraint will not allow you to add 1 with m if you use 64 bit unsigned integer . but however m/2 +1 will always work because of integer division. That's same as dividing by 2 with taking floor value and then adding one. :ugeek: :roll:

Complexity: O(1)
User avatar
 
Posts: 43
Joined: Tue Jan 17, 2017 10:10 pm

Who is online
Users browsing this forum: No registered users and 2 guests
cron