Page 1 of 1

### Easy Coding Contest 16 Editorial Posted: Mon Jan 15, 2018 10:27 am
Contest Link: https://devskill.com/ContestArchive/Con ... d551b2aef8
Contest RankList: https://devskill.com/home/contestrankli ... d551b2aef8

Problem A: Submission Verdict
Problem Setter: Bishal Gautam
Alternate Writer: Suman Bhadra, S.M Shaheen Sha, Mahmud Allahverdiyev

This was a give away problem of this contest. In this problem, you are given exactly one of the verdict in short format i.e. wa , ac, rte or tle. You have to print expanded form of this. You just need 4 if/else conditions.  Problem B: Black cat and Jumping Power
Problem Setter: Bishal Gautam
Alternate Writer: Shakil Ahmed, MD Musfiqur Rahman Sanim , Suman Bhadra

In this problem, you are given the distances of stones from the left side of the river. Initially, Bittu has jumping power of P. Your task is to determine least amount of jumping power Bittu needs to increase so that it can goes to right side of the river.
First of all, as distances are given arbitrary, you have to sort all the distances in ascending order. Then, find out the gap between every consecutive jumps that have to be made. Dont forget to take consideration of jump from point at distance-0 and jump to the last right side of river at distance- R. After that find out the maximum gap, say MAX. if MAX is greater than initial jumping power P, then answer will be MAX-P , otherwise answer will be 0.  Problem C: Sanvi and TreeMap
Problem Setter: Bishal Gautam
Alternate Writer: Suman Bhadra, S.M Shaheen Sha, Mahmud Allahverdiyev

This was an implementation type of problem.In this problem, you only given an image with a map in tree form with a list of cities where Sanvi is interested to visit including her current city. And, you have to answer Q quires where source and destination city are given. You have to find distance needed to travel in between them.
This can be solved either by writing a lots of if/else conditions or can be solved using well known DFS/BFS/FloyedWarshal algorithms.   Problem D: Next Perfect Square Number
Problem Setter: Kazi Sohan
Alternate Writer: Bishal Gautam, S.M Shaheen Sha

In this problem, you are given a positive integer n . You have to tell him the immediate next number which is a perfect square number.
As we know Perfect Square is a number (N) such that there exists an integer number (X) such that X*X=N.
We can do binary search in the range from 1 to 10^9 and in every step, if we find that (mid*mid) value is less or equal to n , then we shift our range to right side otherwise shift range to left side. Then, finally we get the value of (mid*mid) which is exactly greater then n.  Many contestants solved this problem using a simple maths: (sq+1)*(sq+1), where sq=square root of n.   Problem E: Dev Point
Problem Setter: Emrul Chowdhury
Alternate Writer: Bishal Gautam, S.M Shaheen Sha
( tutorial credit: Nafiul Adnan Chowdhury )

Let’s know about an awesome technique called partial sum. It’s a technique to sum up an array with some quarries.
Like you have an initial array with 5 elements: 1 2 3 4 5
now you are given that you have to increase some indexed values in a range by 1.
As example, take 3 update:
1 3 [index no. 1 to 3 have to be increase by 1]
2 5 [index no. 2 to 5 have to be increase by 1]
2 4 [index no. 2 to 4 have to be increase by 1]

After running a loop each time within the range L to R we can add 1 to each of the indexes, but in the worst case the update complexity becomes n*n. which is pretty bad.

Now let’s see the partial sum technique. You know the cumulative sum technique? That is adding the previous indexed value in the present index value:

it’s like in a loop through 1 to N:
Arr[i] = Arr[i] + Arr[i-1];

And we can find the sum between index a to b by: Arr[b] – Arr[a-1].
So now, what can we do with this?

In partial sum, what we do is, we add the value [value is 1 in my explanation] with the L’th index every times. Then if we do a cumulative sum after all the operation, what it does? It adds the value to the indexes which is greater than R too. So, what we do now is, after Adding the value with the Lth index, we also subtract the value from the R+1‘th index too. Such that that value doesn’t get added with the indexes greater than R.

It looks like Arr[L] += val ; Arr[R + 1] -= val;

Then After A cumulative sum we find the updated value in O(N).

So, for this problem you just need to know cumulative sum and partial sum technique.
Take all the user’s Dev Point on an array named DevPoint.

Next we do a cumulative on the Offer Array : Offer[i] += Offer[i-1].

Now comes the query, what does it say?

It says that Apply all offers indexed between X to Y (1 ≤ X ≤ Y ≤ M) to all users indexed between L to R (1 ≤ L ≤ R ≤ N).
Now, take A new array, which we call AddedDP[].

So, it says offer between X to Y, we get it from Offer[Y] – Offer[X-1],
And we have to add it to the users index L to R, so, add it now to the L, and as we will do a cumulative, Subtract it from the R,It will look like:

AddedDP[L] += Offer[Y] – Offer[X - 1]
AddedDP[R + 1] -= Offer[Y] – Offer[X - 1]

After performing the updates, do a cumulative sum on the AddedDP, Add the new AddedDP with the initial DevPoint Array, you got the answer.   