### Easy Coding Contest 18 Editorial

Posted:

**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.

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.

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.

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.

Complexity: O(1)

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.

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.

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.

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.

Complexity: O(1)