Editorial of Bangladesh 2.0 Round

String Algorithm

Tutorial

Only an odd position is available for the for the string S, when the length of the string is 1. Because if length is greater than 1, then always even positions exist. You need to just print the first character of the string S.
Time Complexity : O(1)

Code(C++)

solution

Pair sum

Tutorial

No matter what is N, there is always N/2 pair exist.
But when N is even, we should decrease (N/2) by 1. Because there is a pair (i == j) that exists, which reflects our condition (i < j).
Time Complexity: O(1)

Code(C++)

solution

KuZ the Position

Tutorial

Soon we will update

Code(C++)

solution

Number concatenation

Tutorial

we know that any number A>B if A has more digit than B. If both number has same number of digits then the number which is lexicographically larger is greater among them. so our first target is to concatenate a subarray of length K+1 to make the longest string. if there are more than one longest string possible take the lexicographically maximal one. to do so, we can iterate over all K+1 length subarray and find the maximum length possible.
Time complexity: O(N∗(N−k))

Code (C++)

solution

Sorted or !Sorted

Tutorial

lets make another array B[] of length N. Elements of B[] will be either 0,1 or 2. if the i-th element of the given array is greater than or equal to the previous (i-1 th) element make B[i] = 1 if the i-th element of the given array is less than or equal to the next (i+1 th) element make B[i] = 1 if it satisfy both conditions above then make B[i] = 2 else make B[i] = 0 Now we can calculate the sum of any range of B[] using segment tree or similar. if the sum of any range is 2*range then it means all elements are 2 in the range. which indicates that all the elements in the range are greater than or equal to the previous element and less than or equal to the next element. so the range is definitely sorted. A range can still be sorted if the B[l] and/or B[r] is 1. in this case range sum value 2range-1 or 2range-2 can also indicate a sorted range included some conditions. range sum lower than 2*range-2 can be proved as a unsorted range because there must have at least one B[i]==0 or three B[i] that is 1. in update operation , updating any index i effects three indexes B[i-1],B[i],B[i+1].
Time complexity :O( N * log(N)).

Code (C++)

solution

Apple on Tree

Tutorial

We can start from any node where node has an apple and only travel those nodes where apple is available.
Let’s see if we start traveling from node 3 and again back to this node:

Let’s see if we start traveling from node 4 and again back to this node:

We can clearly see that, no matter which apple node we have selected, the total traveling time is always the same.
In case, you don't know how to calculate minimum traveling time required if you choose a fixed node : Minimum Traveling Time

Can we need to return the starting node? Answer is no. Once we have collected all apples, we can stop any node. So we need to choose the stop apple node, which is the farthest from the start node. Find the distance between two farthest nodes and subtract it from the total traveling time. Because this extra time we have already calculated when we find total traveling time.
Let's see an example , farthest node from 3:

In case, you don't know how to find farthest node: Find Farthest node
Time Complexity : O(E+V)

Code(C++)

solution

Even Odd GCD (Easy + Hard) Version

Hint 1

Let’s see, X = smallest element of the array. All possible divisors of X are fixed for either an even or odd index.

Hint 1 Full explaination

Hint 2

If any of the divisors of X divide by at least half of the array element, then pick any element that is not divided by the divisor of X.

Hint 2 Full explaination

Hint 3

Let see this element Y, which is not divided by a divisor of X. Now check any divisor of Y, divide at least remaining all of the elements, and at least divide half of the elements; we can find an answer (divisor of X + divisor of Y). Find this way as maximum as possible answer

Hint 3 Full explaination

Hint 4

If the divisor of X is divided by the whole array element, then we should find the largest number that is divided by at least half of the elements. In this case, answer = (Divisor of X + Largest divisor, which is divided by at least half elements).

Hint 4 Full explaination

Time Complexity : O( Divisor of smallest Element * N).

Code (C++)

solution