- everything about segmented tree Prince of Persia's blog CF
- kartik kukreja's blog
- e max site
- http://letuskode.blogspot.in/search/label/segment%20tree
- To read and To solve
- http://theoryofprogramming.com/2015/01/27/segment-trees/
- https://codeextractor.wordpress.com/2016/07/11/playing-with-ranges-segment-tree/
- Topcoder's
- Advanced: efficient way CF blog
This blog is merely about to teach anyone anything rather than to collect thoughts of my random minds and a collection of topics I have learned recently. To be more precise while taking preparation for various programming contests and other academics I found an impulse to make notes. Any suggestions or correction is highly appreciated. :)
for code snippets
Sunday, February 5, 2017
Everything about Segmented Tree and alike Data Structure
Important Links:
Monday, November 21, 2016
Wednesday, November 16, 2016
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;
while True:
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()
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:
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)]
Saturday, May 28, 2016
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:
Binary Search
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
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. :)
Friday, May 13, 2016
Dynamic Programming - Table Of Content
#<links>
#<knapsack, coin change or similar>
Problems:
lightoj:
#<bitmask>
Problems:
Lightoj:
#<Longest Common Subsequence>
Problems:
lightoj:
#<Longest Increasing Subsequence>
Problems:
uva:
#<Digit DP>
Problems:
Lightoj:
#<Interval DP>
#<Probability and Expected Value>
Problems:
Lightoj:
#<String Edit>
#<Prefix DP>
Problems:
#<Grid Reduction/Traversal DP>
Problems:
Lightoj:
#<Palindrome related>
Problems:
Lightoj:
#<Non Classical>
Problems:
Lightoj:
- quora links
- Are-there-any-good-resources-or-tutorials-for-dynamic-programming-besides-the-TopCoder-tutorial
- How-can-I-effectively-practice-Dynamic-Programming-to-improve-my-skills
- What-are-systematic-ways-to-prepare-for-dynamic-programming/answer/Michal-Danil%C3%A1k
- DP problems on codeforces
- DP problems categorized in codeforces
- Dynamic Programming Optimizations
- non trivial dp tricks by zscoder
- Everything about dp
- TOPCODER TUTORIAL
- https://community.topcoder.com/tc?module=Static&d1=features&d2=040104
- https://www.topcoder.com/community/data-science/data-science-tutorials/dynamic-programming-from-novice-to-advanced/
- shakil vaia's blog
- shafaet's planet
#<knapsack, coin change or similar>
Problems:
lightoj:
- 1047
- 1200
- 1231
- 1232
- LOJ 1017 - Brush (III)
uva:
- 147
- 357
- 562
- 674
- 990
- 1213
- 10130
- 10664
- 11137
SPOJ:
- KNAPSACK- knapsack problem
- RPLB - blueberries
#<bitmask>
Problems:
Lightoj:
#<Longest Common Subsequence>
Problems:
lightoj:
- 1110
- 1159
- 1013 love calculator
#<Longest Increasing Subsequence>
Problems:
uva:
- 111
- 231
- 481
- 497
- 10131
#<Digit DP>
Problems:
Lightoj:
- 1032
- 1068
- 1140
- 1205
uva:
- uva 10036
#<Interval DP>
#<Probability and Expected Value>
Problems:
Lightoj:
- 1030
- 1027 discovering maze
- 1050 marbles
- 1038 race to 1 again
- lightoj 1064 throwing dice
#<String Edit>
#<Prefix DP>
Problems:
- SPOJ Alphacode - Counting DP
- LOJ 1044 - Palindrome Partitioning
#<Grid Reduction/Traversal DP>
Problems:
Lightoj:
SPOJ:
#<Palindrome related>
Problems:
Lightoj:
- 1025
- 1033
#<Non Classical>
Problems:
Lightoj:
- 1005
- 1057
- 1122
- 1191
uva:
- 10721
- 10910
- 10943
- 11407
#<DP on Tree>
#<Edit Distance>
#<Subset Mask>
#<Loop Reduction DP>
#<Space Reduction DP>
#<Subset Mask>
#<Loop Reduction DP>
#<Space Reduction DP>
Dynamic Programming - Table Of Content
#<links>
#<knapsack, coin change or similar>
Problems:
lightoj:
#<bitmask>
Problems:
Lightoj:
#<Longest Common Subsequence>
Problems:
lightoj:
#<Longest Increasing Subsequence>
Problems:
uva:
#<Digit DP>
Problems:
Lightoj:
#<Interval DP>
#<Probability and Expected Value>
Problems:
Lightoj:
#<String Edit>
#<Prefix DP>
Problems:
#<Grid Reduction/Traversal DP>
Problems:
Lightoj:
#<Palindrome related>
Problems:
Lightoj:
#<Non Classical>
Problems:
Lightoj:
- quora links
- Are-there-any-good-resources-or-tutorials-for-dynamic-programming-besides-the-TopCoder-tutorial
- How-can-I-effectively-practice-Dynamic-Programming-to-improve-my-skills
- What-are-systematic-ways-to-prepare-for-dynamic-programming/answer/Michal-Danil%C3%A1k
- DP problems on codeforces
- DP problems categorized in codeforces
- Dynamic Programming Optimizations
- TOPCODER TUTORIAL
- https://community.topcoder.com/tc?module=Static&d1=features&d2=040104
- https://www.topcoder.com/community/data-science/data-science-tutorials/dynamic-programming-from-novice-to-advanced/
- shakil vaia's blog
- shafaet's planet
#<knapsack, coin change or similar>
Problems:
lightoj:
- 1047
- 1200
- 1231
- 1232
- LOJ 1017 - Brush (III)
uva:
- 147
- 357
- 562
- 674
- 990
- 1213
- 10130
- 10664
- 11137
SPOJ:
- KNAPSACK- knapsack problem
- RPLB - blueberries
#<bitmask>
Problems:
Lightoj:
#<Longest Common Subsequence>
Problems:
lightoj:
- 1110
- 1159
- 1013 love calculator
#<Longest Increasing Subsequence>
Problems:
uva:
- 111
- 231
- 481
- 497
- 10131
#<Digit DP>
Problems:
Lightoj:
- 1032
- 1068
- 1140
- 1205
uva:
- uva 10036
#<Interval DP>
#<Probability and Expected Value>
Problems:
Lightoj:
- 1030
- 1027 discovering maze
- 1050 marbles
- 1038 race to 1 again
- lightoj 1064 throwing dice
#<String Edit>
#<Prefix DP>
Problems:
- SPOJ Alphacode - Counting DP
- LOJ 1044 - Palindrome Partitioning
#<Grid Reduction/Traversal DP>
Problems:
Lightoj:
SPOJ:
#<Palindrome related>
Problems:
Lightoj:
- 1025
- 1033
#<Non Classical>
Problems:
Lightoj:
- 1005
- 1057
- 1122
- 1191
uva:
- 10721
- 10910
- 10943
- 11407
#<DP on Tree>
#<Edit Distance>
#<Subset Mask>
#<Loop Reduction DP>
#<Space Reduction DP>
#<Subset Mask>
#<Loop Reduction DP>
#<Space Reduction DP>
Friday, April 15, 2016
2nd best shortest path
Well this problem is really an interesting one.Determining the shortest path is very easy using dijkstra's Algorithm.But to determine the 2nd best shortest path needs more pruning.
To solve this I mainly followed the lead of this blog post. This problem can be solved by modifying the standard dijkstra's Algorithm.
We will maintain a 2d vector of Distance array rather than 1D Distance array.
A distance will be pushed in two cases:
1. if the size of the distance arraylist of current vertex is zero. that certainly implies this is the shortest cost so far of this vertex.So we will push it into the list of that vertex.
2.if the size is one and the current distance is greater than the existing one. so that makes this as the 2nd best distance.
As the dijkstra's algorithm works greedily , so the elements of the list of any vertex is certainly the shortest distances. So if any vertex has already two elements in its list so we just skip it.
Problem links:
uva-always late
lightoj-not the best
Implementation:
http://ideone.com/QpWFnR
K-best shortest path:
https://en.wikipedia.org/wiki/Yen%27s_algorithm
(I will update this as soon as i get time to implement it by myself :P )
To solve this I mainly followed the lead of this blog post. This problem can be solved by modifying the standard dijkstra's Algorithm.
We will maintain a 2d vector of Distance array rather than 1D Distance array.
A distance will be pushed in two cases:
1. if the size of the distance arraylist of current vertex is zero. that certainly implies this is the shortest cost so far of this vertex.So we will push it into the list of that vertex.
2.if the size is one and the current distance is greater than the existing one. so that makes this as the 2nd best distance.
As the dijkstra's algorithm works greedily , so the elements of the list of any vertex is certainly the shortest distances. So if any vertex has already two elements in its list so we just skip it.
Problem links:
uva-always late
lightoj-not the best
Implementation:
http://ideone.com/QpWFnR
K-best shortest path:
https://en.wikipedia.org/wiki/Yen%27s_algorithm
(I will update this as soon as i get time to implement it by myself :P )
Saturday, March 12, 2016
Primes: Primality Testing,Generating Primes ( Sieve of Eratosthenes)
Prime Numbers:
All numbers greater than 1 and having only two divisors (1 and the number itself) is called prime numbers.
Such that 2,3,5 are prime. 4,8,10 are not.
Primality Testing:
In this section we will discuss how to check whether a number is prime or not.
We can iterate from 2 to n-1 and checks if the number can be divided by any of these numbers.But these approach has a complexity of O(n).
We can notice that for every number it is impossible to have a divisor greater than n/2 besides the number itself. So it is enough to iterate over 2 to n/2. But though the complexity does not improve a much.
So we will discuss about a property that will allow us to reduce the complexity upto square root of n,Using the knowledge from discrete math- " if a number is not prime then there exists at least one prime divisor of that number which is less than square root of n."
So using this property we only need to iterate over 2 to sqrt(n). Thus our approach is reduced to the complexity of O(sqrt(n)).
Code:
bool isPrime(int n)
{
int f=1;
for(int i=2;i*i<=n;i++)
{
if(n%i==0)
{
f=0;
break;
}
}
return f;
}
All numbers greater than 1 and having only two divisors (1 and the number itself) is called prime numbers.
Such that 2,3,5 are prime. 4,8,10 are not.
Primality Testing:
In this section we will discuss how to check whether a number is prime or not.
We can iterate from 2 to n-1 and checks if the number can be divided by any of these numbers.But these approach has a complexity of O(n).
We can notice that for every number it is impossible to have a divisor greater than n/2 besides the number itself. So it is enough to iterate over 2 to n/2. But though the complexity does not improve a much.
So we will discuss about a property that will allow us to reduce the complexity upto square root of n,Using the knowledge from discrete math- " if a number is not prime then there exists at least one prime divisor of that number which is less than square root of n."
So using this property we only need to iterate over 2 to sqrt(n). Thus our approach is reduced to the complexity of O(sqrt(n)).
Code:
bool isPrime(int n)
{
int f=1;
for(int i=2;i*i<=n;i++)
{
if(n%i==0)
{
f=0;
break;
}
}
return f;
}
Here I use i*i<=n which is an alternate to i<= sqrt(n).
But sqrt(n) function has a complexity of O(sqrt(n)),
So i will suggest not to use the function in loop,
which will unnecessarily increase the run time
of the code. Besides there can also be a floating
point precision error if written like that. So better
way to compute the square root of n in a variable before
and then use that variable or simply use the above method
I used in the code.
But sqrt(n) function has a complexity of O(sqrt(n)),
So i will suggest not to use the function in loop,
which will unnecessarily increase the run time
of the code. Besides there can also be a floating
point precision error if written like that. So better
way to compute the square root of n in a variable before
and then use that variable or simply use the above method
I used in the code.
Generating Prime:
Ok for Generating primes, a very good article was
written by Jane Alam Jan in Lightoj. The article is so enriched,
I found no need of writing
anything else :) .
written by Jane Alam Jan in Lightoj. The article is so enriched,
I found no need of writing
anything else :) .
Code I Used:
#define M 1000000
bool marked[M];
vector <int> primes;
void sieve(int n) {
primes.push_back(2);
for (int i = 3; i * i <= n; i += 2) {
if (marked[i] == 0) {
primes.push_back(i);
for (int j = i * i; j <= n; j += i + i) {
marked[j] = 1;
}
}
}
}
Complexity:
The algorithm has run time complexity of O(Nlog(logN))
Least Common Multiple of Two Numbers
Given Two numbers, say a and b we have to find their lowest multiple which is common to the both nunbers.
Finding Method:
The formula is:
GCD(a,b) * LCM(a,b) = a * b;
Therefore, LCM(a,b) = (a * b) / GCD(a,b);
Code and pitfalls:
int lcm(int a,int b)
{
return ( a * b ) / gcd ( a, b );
}
this code will work fine but for some cases it may overflow.So we should rewrite the (a*b)/gcd(a,b) part into a/gcd(a,b) * b .
What I use:
template< class T > T lcm(T a, T b) { return (a / gcd(a, b) * b); }
Finding Method:
The formula is:
GCD(a,b) * LCM(a,b) = a * b;
Therefore, LCM(a,b) = (a * b) / GCD(a,b);
Code and pitfalls:
int lcm(int a,int b)
{
return ( a * b ) / gcd ( a, b );
}
this code will work fine but for some cases it may overflow.So we should rewrite the (a*b)/gcd(a,b) part into a/gcd(a,b) * b .
What I use:
Greatest Common Divisor
So we are trying to compute GCD ( Greatest Common Divisor) of two numbers, Say a and b.As the name suggests we are trying to determine the greatest number that divides both a and b.
Finding Procedure:
There are many procedures of how we can find the gcd of two numbers, but we will discuss about the euclidean method here.
It works on the principle GCD(a,b)=GCD(b,a%b). Since GCD(b,a%b) is a smaller state,it is easier to find than the original.So we can solve it using this recursion relation and using the base case, GCD(a,a)=a and GCD(a,0)=a;
Code:
Recursive version:
int gcd ( int a, int b )
{
if(b==0) return a;
return gcd(b,a%b);
}
Iterative Version:
int gcd ( int a , int b )
{
while(!b)
{
a=a%b;
swap(a,b)
}
}
Built in version:
There is also a builtin version in C++ for finding GCD. ( __gcd(a,b) ).
What i use:
I use this as my template:
template< class T > T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
Proof:
We can imagine a grid a * b. We are trying to find the largest number x
such that we can cover the whole grid using tiles of size x * x .
And if the whole grid is to be covered by the square sized tiles so x
must be a divisor of both a and b. So we will try to choose x such that x
be the smaller number between a and b (say b). If we found that it is not
possible to cover the whole grid, there must be some remainder of the grid
which will be a%b. So the we will try the same method for a= b and b=a%b;
GCD texure: courtesy Wiki.
Complexity:
Well the complexity of this algorithm is kindaa tricky, My coach refers me to an answer of stack overflow. For now I am only giving the complexity of the answer.but as soon as i understand the proof the solution i will rewrite this portion.
The complexity of above algorithm is - O( log10(a) + log10(b) ).
Coding Pitfalls:
Well this is one of the great things i have learnt recently from my Coach.Though i used the algorithm for a long time i didn't know this pitfall.That is the algorithm only works for non negative numbers. So in case of negative numbers are concerned we can either send absolute value of the numbers or we can take the absolute value of the result.
Another thing is- notice that
Number Theory From Scratch to Things I know
This Blog Post will be updated time to time. I will update when I think I have learnt something new and need to keep note. In this post I will mainly focus on theory along with code.
Though working code for my cookbook will be also updated in Dropbox and google drive as well.
1.Greatest Common Divisor.
2.Least Common Multiple of Two Numbers.
3.Primes: Primality Testing,Generating Primes ( Sieve of Eratosthenes).
Subscribe to:
Posts (Atom)
