Arnab's blog: 2016

Monday, November 21, 2016

Important and Unimportant Links

To be continued...

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;

#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)]

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

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. :)

Friday, May 13, 2016

Dynamic Programming - Table Of Content

#<links>

quora links

#<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>

LOJ 1031 - Easy Game

#<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>

Dynamic Programming - Table Of Content

#<links>

quora links

#<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>

LOJ 1031 - Easy Game

#<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>

Friday, April 15, 2016

Graph - table of contents

Articulation Point and Bridge Finding

Samiul vaia's Blog:

Articulation Point
Bridge finding

Others:

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 )

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;
}

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.

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 :) .

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); }

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
GCD(0,0)=0. It should be infinity. Also, if you try to work with the return value of

GCD(0,0), then you might get RTE due to division by zero.

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).

Thursday, February 4, 2016

EDITORIAL : MIST selection contest (SUB IUPC) - LAST

Contest link: MIST selection contest (SUB IUPC) - LAST :

C - Help howcum, you must :

Problem Category: implementation, fibonacci numbers, pisano's period.

Well the problem is plain simulation. The steps are given in a very organized way. One has just to implement those.

At first one has to compute fibonacci numbers upto 10^6. Don't get anxious as you only will need the last 4 digits of those.So one can mod every time so that the numbers don't get out of range to fit in int data type.To do this you can mod every time with least number of 5 digit if you don't know about Pisano's period.

fibonacci numbers have a amazing property discovered by Pisano.
every last 1/2/3/4 digit(s) of fibonacci numbers repeats with a period of 60/300/1500/15000, respectively. (So you can easily understand you don't have to compute all 10^6 fibonacci numbers either :) ).

So upto this we covered the first two steps of the problem requirement.

For the 3rd and 4th steps you just have to count how many bits are on in the numbers got in the previous steps. ( you can just use __builtin_popcount() function for this steps. )

And now for the last step you have to count how many numbers in that range are there of which the sum of digits are divisible by P. Pretty easy you may think.. :P

you can prune out that in this last part- the range is never greater than 14. So the mod value given is just to scare you out. :P (you know RAM is a bit weird :) , but that's how howcum likes her ^_^ ).

Well you may need something extra. just be careful when k and p is zero.

E - Breaking Toys :

Problem Category: Number theory,catalan numbers,backtracking

Well this problem is very easy if you know the catalan numbers and its properties.

Dyck language is the language consisting of balanced strings of square brackets [ and ].

C_n is the number of Dyck words of length 2n. A Dyck word is a string consisting of n X's and n Y's such that no initial segment of the string has more Y's than X's. For example, the following are the Dyck words of length 6.

XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY.

So if you have read the problem set you can easily find that I just changed the X and Y with A and B. :P

In this problem you just need to calculate and pre-compute the first 14 catalan numbers.you can try this formula:

cat(m) = (2m*(2m-1))/((m+1)*m)* cat(m-1).

Then you can just give the result for every test case in O(1).

Alternative Solution:

As the input limit is small, so one can use backtrack to calculate the answer if he/she does not find the pattern or for any other reason.

J - RAM weds howcum :

This problem was set jointly by me and Shubhashis Roy Dipta.
Well to be honest we were trying to set a DP problem. In fact our solution of this problem was also DP until one of the contestants submit a solutions faster than us. Then we figure out it is a pure combinatorics problem :P and can be done with a linear loop. :P (A weird place, the world is :) )

The problem was to make a number of exactly length n without any consecutive same digit. ( this means no leading zeros are allowed).
So one can easily prune out that in the first position there can be at most 9 digits.( 0 is not allowed)
then in the second position there can also be 9 digits (0 to 9 except the digit placed in first position).

Thus in ith position there can also be 9 digits( 0 to 9 except the digits placed in position i-1)

So the solution is 9^n. you have to mod as per the mod value described in the problem.

DP Solution:

if you are really curious, this part is for you- Our DP solution consists of two state, in which position we are currently in and what was the last digit placed in the last position.

In the function we loop over 0 to 9 and check if this digit is not same with the last placed digit then do nothing, otherwise call the function for next position with this digit as the last placed digit.

The base case is if all the positions are placed with some digits then just return 1. :)

This can be what a raw code look like:

#define ll long long int
ll call(int pos,int last)
{
if(pos==n)
{
return 1;
}
ll res=0;
if(pos==0)
{
for(int i=1;i<=9;i++)
{
res+=call(pos+1,i);
}
}
else
{
for(int i=0;i<=9;i++)
{
if(last==i) continue;
res+=call(pos+1,i);
}
}
return res%mod;
}

And also Don't forget to memorize the results for this function. Because you know "Those who do not memorize the past are to repeat the same things again and again." :P :)

Hope this may be helpful. Anyone is warmly welcomed for any type of criticism. :)

for code snippets

Monday, November 21, 2016

Wednesday, November 16, 2016

Saturday, May 28, 2016

#Variant-01:

Friday, May 13, 2016

Friday, April 15, 2016

Saturday, March 12, 2016

Thursday, February 4, 2016