### Happy New Year 2018 Contest-Editorial

Posted:

**Tue Jan 02, 2018 6:41 pm**Contest Link: https://devskill.com/ContestArchive/Con ... d54cde8368

Contest Ranklist: https://devskill.com/home/contestrankli ... d54cde8368

Problem A: Very Happy New Year++

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

Problem Setter: Bishal Gautam

Alternate Writer: Suman Bhadra, S.M Shaheen Sha, Mahmud Allahverdiyev

This is a very easy give away problem provided to get at least one submission from all users. In this problem, you are given a string of the form "HappyNewYearX" always , where X means zero or more "+" signs. Your task is to increase the current year value depending upon numbers of "+" signs and print the answer in following format : Happy New Year-Y , Here Y means updated year value after adding numbers of "+" sign with current year 2018.

You just need to iterate over given string and increase counter whenever you find a character '+'.

Final answer will be an integer: 2018 + total counter value.

Complexity:O(N)

Problem B: Match counter

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

Problem Setter: Mahmud Allahverdiyev

Alternate Writer: Bishal Gautam , S.M Shaheen Sha

Since the constraints are so small, this is also a easy implementation type of problem. In this problem, you need to count the number of substrings of the first string which are also substring of the second string. For each query,you can easily solve this problem just finding evey substring of query length and checking it on another string.

Complexity: O(TC*Q*N*M*50)

Problem C: Square of Subsequence

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

Problem Setter: Bir Bahadur Khatri

Alternate Writer: Bishal Gautam, Mahmud Allahverdiyev

To be clear about problem please read the problem carefully.

For each prefix we can store the minimum and maximum square value which subsequence ended before or at this position.

Similarly we can store that for each suffix.By using a loop we can answer the maximum absolute difference.

How to calculate minimum/maximum for each prefix and suffix?

->>> using recursion we can store that.

Complexity: O(2^N) per testcase

Problem D: Names-2

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

Problem Setter: Monikrishna Roy

Alternate Writer: Bishal Gautam, S M Shaheen Sha, MD Musfiqur Rahman Sanim

You are given the length of names L and a set string S. You have to find the number of distinct names of given length which have any string from set as a suffix.

We need to count the number of names that match at least one of the given string from set. Let begin with a single example:

Given length 4, and string “ab” from set. Lets calculate the number of names. Here, 2 place are occupied with string "ab". So, there are only 2 places to change and on every place we can place 26 different characters. So total: 26*26=676 ways.

So, we can generalize this into 26(L-|S[i]|).

There may be more than one same names in output. We have to count only unique names. For example:

Given length 4, set of string {“a”,”aa”}. We have to calculate names for two string. But when we calculate number of names for “a”, it is also done calculation for “aa”. Because every name that ends with “a” will also end with “aa”. It is possible to only consider “a”, when counting the tickets that end with “a” we will also implicitly include the tickets that end with “aa”, because “a” is a suffix of “aa”.

Note: If there is one string in the set contains many times we have to calculate for one time.

So, we can sum up the solution in three steps:

1. Remove the duplicate string from set of string.

2. Remove unnecessary string from set ( For every string i, if there is a string j such that s[i] is a proper suffix of s[j], then remove s[j])

3. For each remaining string i: Add 26(L-|s[i]|) to the count of names.

The answer may be very large. So, you have to use bigInteger libraries. You can look at the implementation for C++ in indy256’ blog, Jane-Alam Jan Lightoj.

Complexity: O(T*N*N)

Problem E: Balanced array

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

Problem Setter: Bir Bahadur Khatri

Alternate Writer: Bishal Gautam, Mahmud Allahverdiyev

Given a balanced array of numbers ( see problem for definition) . We need to change the sign of one value at given position in a query and we are allowed to change sign of at most one other value to make the array balanced again. We need to know, just possible or not.

First of all, if it is possible to make the array balanced again after changing the sign at position POS, changing the sign of two same value (absolute) is enough. As we need to change the value at position POS to negative, next value( let position is NEXT), we need to change the sign should be:

In right position from POS i.e POS<NEXT<=N.

Value at position NEXT is negative of value at position POS.

Hence, we need to know find the position NEXT.

Example

Let’s see an example.

It is possible to change the sign of 2 at position 6, because NEXT=9 and array from 7 to 9 is balanced.

It is not possible to change the sign of 3 at position 3, because NEXT=7 and array from 4 to 6 is not balanced.

It is not possible to change the sign of 2 at position 10, because NEXT position not found.

To find the position NEXT for each position, we can use Persistence segment tree or we can use set with stack.

Complexity : O(N*Log(N) )

Contest Ranklist: https://devskill.com/home/contestrankli ... d54cde8368

Problem A: Very Happy New Year++

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

Problem Setter: Bishal Gautam

Alternate Writer: Suman Bhadra, S.M Shaheen Sha, Mahmud Allahverdiyev

This is a very easy give away problem provided to get at least one submission from all users. In this problem, you are given a string of the form "HappyNewYearX" always , where X means zero or more "+" signs. Your task is to increase the current year value depending upon numbers of "+" signs and print the answer in following format : Happy New Year-Y , Here Y means updated year value after adding numbers of "+" sign with current year 2018.

You just need to iterate over given string and increase counter whenever you find a character '+'.

Final answer will be an integer: 2018 + total counter value.

Complexity:O(N)

Problem B: Match counter

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

Problem Setter: Mahmud Allahverdiyev

Alternate Writer: Bishal Gautam , S.M Shaheen Sha

Since the constraints are so small, this is also a easy implementation type of problem. In this problem, you need to count the number of substrings of the first string which are also substring of the second string. For each query,you can easily solve this problem just finding evey substring of query length and checking it on another string.

Complexity: O(TC*Q*N*M*50)

Problem C: Square of Subsequence

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

Problem Setter: Bir Bahadur Khatri

Alternate Writer: Bishal Gautam, Mahmud Allahverdiyev

To be clear about problem please read the problem carefully.

For each prefix we can store the minimum and maximum square value which subsequence ended before or at this position.

Similarly we can store that for each suffix.By using a loop we can answer the maximum absolute difference.

How to calculate minimum/maximum for each prefix and suffix?

->>> using recursion we can store that.

Complexity: O(2^N) per testcase

Problem D: Names-2

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

Problem Setter: Monikrishna Roy

Alternate Writer: Bishal Gautam, S M Shaheen Sha, MD Musfiqur Rahman Sanim

You are given the length of names L and a set string S. You have to find the number of distinct names of given length which have any string from set as a suffix.

We need to count the number of names that match at least one of the given string from set. Let begin with a single example:

Given length 4, and string “ab” from set. Lets calculate the number of names. Here, 2 place are occupied with string "ab". So, there are only 2 places to change and on every place we can place 26 different characters. So total: 26*26=676 ways.

So, we can generalize this into 26(L-|S[i]|).

There may be more than one same names in output. We have to count only unique names. For example:

Given length 4, set of string {“a”,”aa”}. We have to calculate names for two string. But when we calculate number of names for “a”, it is also done calculation for “aa”. Because every name that ends with “a” will also end with “aa”. It is possible to only consider “a”, when counting the tickets that end with “a” we will also implicitly include the tickets that end with “aa”, because “a” is a suffix of “aa”.

Note: If there is one string in the set contains many times we have to calculate for one time.

So, we can sum up the solution in three steps:

1. Remove the duplicate string from set of string.

2. Remove unnecessary string from set ( For every string i, if there is a string j such that s[i] is a proper suffix of s[j], then remove s[j])

3. For each remaining string i: Add 26(L-|s[i]|) to the count of names.

The answer may be very large. So, you have to use bigInteger libraries. You can look at the implementation for C++ in indy256’ blog, Jane-Alam Jan Lightoj.

Complexity: O(T*N*N)

Problem E: Balanced array

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

Problem Setter: Bir Bahadur Khatri

Alternate Writer: Bishal Gautam, Mahmud Allahverdiyev

Given a balanced array of numbers ( see problem for definition) . We need to change the sign of one value at given position in a query and we are allowed to change sign of at most one other value to make the array balanced again. We need to know, just possible or not.

First of all, if it is possible to make the array balanced again after changing the sign at position POS, changing the sign of two same value (absolute) is enough. As we need to change the value at position POS to negative, next value( let position is NEXT), we need to change the sign should be:

In right position from POS i.e POS<NEXT<=N.

Value at position NEXT is negative of value at position POS.

- Initial array is balanced so that we can say that “It is possible to change the sign at position NEXT if array from POS+1 to NEXT-1 should be balanced. Note that this can be empty too, Which is also balanced”. If any such position exists then array can be balanced after the change.

Hence, we need to know find the position NEXT.

Example

Let’s see an example.

It is possible to change the sign of 2 at position 6, because NEXT=9 and array from 7 to 9 is balanced.

It is not possible to change the sign of 3 at position 3, because NEXT=7 and array from 4 to 6 is not balanced.

It is not possible to change the sign of 2 at position 10, because NEXT position not found.

To find the position NEXT for each position, we can use Persistence segment tree or we can use set with stack.

Complexity : O(N*Log(N) )