Editorials - C For Code 01 - Coding Club - ISM Dhanbad

Problem: Easy One For Cartman

This problem was a cakewalk. We know the first term A, second term B and the no. of terms N. So common difference is D=B-A.

Formula for sum of A.P. is
Sum = ( N * ( 2 * A + (N-1) * D ) ) / 2

So, Here is the code for this problem:

http://www.codechef.com/viewplaintext/2388336




Problem: Butters Counting Problem

Prerequisite: Binary Search.

Ok, for the beginners just assume that a computer can perform around 10^8 operations per second. From this you will get an idea of Time Limit. Time Limit for this problem was 1 second.
There were "Q" queries and "N" numbers. If you perform a linear search for every query, the time complexity will be O(Q * N)
Maximum possible value of Q * N is (10^5)*(10^5) i.e. 10^10, so this is for sure that this approach will give time limit exceeded.
On the other hand, if we perform Binary Search on the N numbers for each query, the time complexity will be O(Q * log N), its maximum value will be (10^5)*log(10^5), i.e. around 2 * 10^6, so it should run within the time limit.
So we have to use Binary Search here. Since the numbers are given in sorted order, we can directly perform binary search on it. We should search for the smallest element that is greater than "L" in the list. But there can be a case when such element does not exist, i.e. all the elements are less than or equal to "L". So we can make a separate code for this case, and all the other cases can be solved by binary search.

Here is the code for this problem:

http://www.codechef.com/viewplaintext/2389023

For more help on binary search you can read this tutorial:

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearch




Problem: Kyle Makes a List

Prerequisite: Longest Increasing Subsequence Problem, Dynamic Programming

if (x,y) and (a,b) are two consecutive pairs in the list then, y<a, also for every pair x<y and a<b
So, we conclude that x<a for every consecutive pairs. So our first step must be to sort the given pairs according to their first co-ordinate, and if first co-ordinates are same, then according to second co-ordinates.

After this we perform a variation of Longest Increasing Subsequence. A very nice explanation is given here:

http://www.geeksforgeeks.org/dynamic-programming-set-20-maximum-length-chain-of-pairs/

For Longest Increasing Subsequence Problem, read this:

http://www.geeksforgeeks.org/dynamic-programming-set-3-longest-increasing-subsequence/

Here is the solution to this problem: (I have used vectors and pairs in this solution, those who are not familiar with them, I recommend you to learn about vectors atleast as they are very powerful templates to solve problems easily on online algorithmic contests)

http://www.codechef.com/viewplaintext/2389120