Everything about Segmented Tree and alike Data Structure

Important Links:

1. everything about segmented tree Prince of Persia's blog CF
2. kartik kukreja's blog
3. e max site
4. http://letuskode.blogspot.in/search/label/segment%20tree
5. To read and To solve
6. http://theoryofprogramming.com/2015/01/27/segment-trees/
7. https://codeextractor.wordpress.com/2016/07/11/playing-with-ranges-segment-tree/
8. Topcoder's
9. Advanced: efficient way CF blog

Important and Unimportant Links

1. top 10 algorithms and data structure geeksforgeeks
2. An awesome List for Competitive Programming
3. 145+ algorithm and c++ implementation
4. http://geomalgorithms.com/

To be continued...

Competitive Programming In Python 3.x

Though I prefer C++ for competitive programming and problem solving, but sometimes python can be of great help.Specially when big data needs to be handled. So I felt an urge to note down basic input-output or other things in python.

Here I will use python 3.x.

Input-Output:

#Take input while End Of File:

while True:
        try:
             n=input()
        except EOFError:
             break;

#Take space separated int inputs:

while True:

        try:
             inp=input()
        except EOFError:
             break;
        n,m=inp.split()
        n=int(n)
        m=int(m)
#Take input while a certain conditions are met.
while True:

        inp=input()
        n,m=inp.split()

        n=int(n)
        m=int(m)
        if n==0 and m==0:
                break


Array related:

Two dimensional Array initialized with zero:

array=[[0 for x in range(102)] for y in range(102)]

Two pointers a.k.a Sliding Window

Well this is a very common topic specially in Codeforces. It's merely an algorithm rather I like to call it a technique and quite an useful one.

The CP3 ( Competitive Programming 3) states 4 variants of this technique.But before we look into those first lets take a look into an easier problem which will motivate towards the technique.

Suppose we have an array A of length upto 10^5. and we want to know if a pair of this array can make a certain value S.

Obviously we can iterate all possible pair. But that'a too timid and yield to a complexity of O(n^2).

So if we sort the array. Then take two pointer one left and right pointing to the first and last element of the array.if A[left] + A[right] > S , then we can say for sure we have to move the right pointer. because otherwise our purpose would not be served as A[left] < A[left+1]. But as       

A[right]> A[right-1] , So we have to move the right pointer.

Similarly if at some point A[left] + A[ right] < S , then we have to move the left pointer. As we are seeking a larger value which can only be found if we move the left pointer.The code would look like this-

Variant - 00:

Find if there exists a pair whose sum is S.

bool two_pointer_variation_0(int sum)

{

    int left=0,right=n-1;

    while(left<right)

    {

        if(a[left]+a[right]==sum)

            return 1;

        else if(a[left]+a[right]>sum)

            right--;

        else

            left++;

    }

    return 0;

}

#Variant-01:

Find the largest sum possible in an Array but not greater than M;

int left=0,right=0; int sum=0; int ans=0; while(left<=right) { while(right<n && sum+a[right]<=M) { sum+=a[right]; right++; } ans= max(ans,sum); sum-=a[left]; left++; } cout<< ans <<endl;

#Variant - 02: (cp3 variation 1)

Find the smallest sub array size so that the sum of sub array is greater than or equal to a certain value S;

int left=0,right=-1; int ans=INF; int temp_sum=0; while(left<n) { right++; temp_sum+=a[right]; if(temp_sum>=sum) { ans= min( ans , abs( right - left ) ); } while(left<n && temp_sum-a[left]>=sum) { temp_sum-=a[left]; left++; } } cout<< ans <<endl;

#Variant - 03 :

Find the largest sum possible in an array but not greater than M; int left=0,right=0; int sum=0; int ans=0; while(left<=right) { while(right<n && sum+a[right]<=M) { sum+=a[right]; right++; } ans= max(ans,sum); sum-=a[left]; left++; } cout<< ans <<endl;

#Variant - 04 : ( cp3 variation - 03 )

find the maximum sum of a certain subarray with size k cp3 variation 3 int left=0,right=0; int sum=0; int ans=0; while(left<n) { while(right<n && right-left<k) { sum+=a[right]; right++; } if(right-left==k) { ans = max ( ans , sum ); } sum -= a[left]; left++; } cout<< ans << endl;

#Variant - 05 : (cp3 variation -02 similar)

smallest sub array size so that the sub array contains at least k distinct

values;

set <int> s; map <int, int> mp; mp.clear(); s.clear(); int left=0,right=0; int ans=INF; while(left<n) { while(right<n && s.size()< k) { s.insert(a[right]); mp[a[right]]++; right++; } if(s.size()>=k) { ans = min( ans , abs( right - left ) ); debug( left , right ) } if(mp[a[left]]==1) s.erase(a[left]); mp[a[left]]--; left++; } cout<< ans << endl;

#Variant - 06 : ( cp3 variation -04 )

find the minimum element of each possible sub array with a size k

cp3 variation 4

    deque<pii> window;

    for(int i=0;i<n;i++)

    {

        while(!window.empty() && window.back().first>=a[i])

        {

            window.pop_back();

        }

        ///this is to keep the array sorted

        ///window.front() is always the minimum element

        window.push_back(MP(a[i],i));

        ///now use the second part to see if the front elemt is still inside the window or pop it otherwise

        while(window.front().second<=i-k)

        {

            window.pop_front();

        }

        if(i+1>=k)

        {

            cout<< window.front().first <<endl;

        }

    }

References:

1. https://tp-iiita.quora.com/The-Two-Pointer-Algorithm#
2. http://shakilcompetitiveprogramming.blogspot.com/2015/06/two-pointer.html

Binary Search

this is an very good tutorial about binary search in the topcoder

General algorithm:

Finding a value in a sorted sequence:

binary_search(A, target):
  lo = 1, hi = size(A)
  while lo <= hi:
     mid = lo + (hi-lo)/2
     if A[mid] == target:
        return mid            
     else if A[mid] < target:
        lo = mid+1
     else:
        hi = mid-1
           
  // target was not found

Upper Bound:

Return iterator to upper bound

Returns an iterator pointing to the first element in the range [first,last) which compares greater than val.

C++ STL - upper_bound()

Lower Bound:

Return iterator to lower bound

Returns an iterator pointing to the first element in the range [first,last) which does not compare less than val.

C++ STL - lower_bound()

Binary_Search :

Returns true if any element in the range [first,last) is equivalent to val, and false otherwise.
C++ STL - binary_search()

Implementing upper_bound and lower_bound :
While implementing upper_bound or lower_bound on your ownself may arises some tedious problems. Such as depending on your implementation the ans can be sometimes in the low pointer and sometimes in the high pointer. It was a very disturbing thing. Then one day my coach has given me an amazing solution of this problem. It's kindaa generic. So remembering it won't be an issue.

lower_bound:

int low=0,high=n;
while(low<=high)
{
int mid = (low + high ) / 2;

if(arr[mid]>=x) high = mid -1;          ///so at first try to eliminate the second portion and do not break                                                                 if equal
else
low = mid + 1;
}

If you implement this method the answer will always be in low pointer.
P.S: sometimes you may need to check one more time if the low actually is the answer, in case of not found.

upper_bound:

int low=0,high=n;
while(low<=high)
{
int mid = (low + high ) / 2;

if(arr[mid]<=x) low = mid + 1;          ///so at first try to eliminate the first portion and do not break                                                                      if equal
else
high = mid -1;

}

And most amazingly in this method of implementation the answer will also be in the low pointer. :) quite easy i guess. Thanx to Mr. forthright48 for this amazing solution. :)

Dynamic Programming - Table Of Content

#<links>

1. quora links
1. Are-there-any-good-resources-or-tutorials-for-dynamic-programming-besides-the-TopCoder-tutorial
2. How-can-I-effectively-practice-Dynamic-Programming-to-improve-my-skills
3. What-are-systematic-ways-to-prepare-for-dynamic-programming/answer/Michal-Danil%C3%A1k
2. DP problems on codeforces
3. DP problems categorized in codeforces
4. Dynamic Programming Optimizations
5. non trivial dp tricks by zscoder
6. Everything about dp
7. TOPCODER TUTORIAL
1. https://community.topcoder.com/tc?module=Static&d1=features&d2=040104
2. https://www.topcoder.com/community/data-science/data-science-tutorials/dynamic-programming-from-novice-to-advanced/
8. shakil vaia's blog
9. shafaet's planet

#<knapsack, coin change or similar>

Problems:

lightoj:

1. 1047
2. 1200
3. 1231
4. 1232
5. LOJ 1017 - Brush (III)

uva:

1. 147
2. 357
3. 562
4. 674
5. 990
6. 1213
7. 10130
8. 10664
9. 11137

SPOJ:

1. KNAPSACK- knapsack problem
2. RPLB - blueberries

#<bitmask>

Problems:

Lightoj:

1. 1011
2. 1018 *
3. 1021
4. 1037
5. 1057
6. 1061 *
7. 1158
8. 1264 *
9. 1316 *
10. 1327

#<Longest Common Subsequence>

Problems:

lightoj:

1. 1110
2. 1159
3. 1013 love calculator

#<Longest Increasing Subsequence>

Problems:

uva:

1. 111
2. 231
3. 481
4. 497
5. 10131

#<Digit DP>

Problems:
Lightoj:

1. 1032
2. 1068
3. 1140
4. 1205

uva:

1. uva 10036

#<Interval DP>

1. LOJ 1031 - Easy Game

#<Probability and Expected Value>

Problems:

Lightoj:

1. 1030
2. 1027 discovering maze
3. 1050 marbles
4. 1038 race to 1 again
5. lightoj 1064 throwing dice

#<String Edit>

1. LOJ 1033 - Generating Palindromes
2. LOJ 1051 - Good or Bad

#<Prefix DP>

Problems:

1. SPOJ  Alphacode - Counting DP
2. LOJ 1044 - Palindrome Partitioning

#<Grid Reduction/Traversal DP>

Problems:
Lightoj:

1. 1036
2. LOJ 1004 - Monkey Banana Problem
3. LOJ 1071 - Baker Vai
4. LOJ 1005 - Rooks

SPOJ:

1. SPOJ Philosophers Stone
2. SPOJ Martian

#<Palindrome related>

Problems:

Lightoj:

1. 1025
2. 1033

#<Non Classical>

Problems:

Lightoj:

1. 1005
2. 1057
3. 1122
4. 1191

uva:

1. 10721
2. 10910
3. 10943
4. 11407

#<DP on Tree>

#<Edit Distance>

#<Subset Mask>

#<Loop Reduction DP>

#<Space Reduction DP>

Dynamic Programming - Table Of Content

#<links>

1. quora links
1. Are-there-any-good-resources-or-tutorials-for-dynamic-programming-besides-the-TopCoder-tutorial
2. How-can-I-effectively-practice-Dynamic-Programming-to-improve-my-skills
3. What-are-systematic-ways-to-prepare-for-dynamic-programming/answer/Michal-Danil%C3%A1k
2. DP problems on codeforces
3. DP problems categorized in codeforces
4. Dynamic Programming Optimizations
5. TOPCODER TUTORIAL
1. https://community.topcoder.com/tc?module=Static&d1=features&d2=040104
2. https://www.topcoder.com/community/data-science/data-science-tutorials/dynamic-programming-from-novice-to-advanced/
6. shakil vaia's blog
7. shafaet's planet

#<knapsack, coin change or similar>

Problems:

lightoj:

1. 1047
2. 1200
3. 1231
4. 1232
5. LOJ 1017 - Brush (III)

uva:

1. 147
2. 357
3. 562
4. 674
5. 990
6. 1213
7. 10130
8. 10664
9. 11137

SPOJ:

1. KNAPSACK- knapsack problem
2. RPLB - blueberries

#<bitmask>

Problems:

Lightoj:

1. 1011
2. 1018 *
3. 1021
4. 1037
5. 1057
6. 1061 *
7. 1158
8. 1264 *
9. 1316 *
10. 1327

#<Longest Common Subsequence>

Problems:

lightoj:

1. 1110
2. 1159
3. 1013 love calculator

#<Longest Increasing Subsequence>

Problems:

uva:

1. 111
2. 231
3. 481
4. 497
5. 10131

#<Digit DP>

Problems:
Lightoj:

1. 1032
2. 1068
3. 1140
4. 1205

uva:

1. uva 10036

#<Interval DP>

1. LOJ 1031 - Easy Game

#<Probability and Expected Value>

Problems:

Lightoj:

1. 1030
2. 1027 discovering maze
3. 1050 marbles
4. 1038 race to 1 again
5. lightoj 1064 throwing dice

#<String Edit>

1. LOJ 1033 - Generating Palindromes
2. LOJ 1051 - Good or Bad

#<Prefix DP>

Problems:

1. SPOJ  Alphacode - Counting DP
2. LOJ 1044 - Palindrome Partitioning

#<Grid Reduction/Traversal DP>

Problems:
Lightoj:

1. 1036
2. LOJ 1004 - Monkey Banana Problem
3. LOJ 1071 - Baker Vai
4. LOJ 1005 - Rooks

SPOJ:

1. SPOJ Philosophers Stone
2. SPOJ Martian

#<Palindrome related>

Problems:

Lightoj:

1. 1025
2. 1033

#<Non Classical>

Problems:

Lightoj:

1. 1005
2. 1057
3. 1122
4. 1191

uva:

1. 10721
2. 10910
3. 10943
4. 11407

#<DP on Tree>

#<Edit Distance>

#<Subset Mask>

#<Loop Reduction DP>

#<Space Reduction DP>