Inverting sub-array to get maximum 1’s.

Let there be an array containing only two different elements. Lets consider them to be 0 and 1. You have to find total number of 1’s you could make from this array after performing some task. And the task is to select a sub-array and invert each of its element(Convert each of the element from 0 to 1 or 1 to 0 for every element in sub-array).

This problem certainly have a simple approach. Check for all subsets and count number of resulting 1’s in the array. That would result in an O(N3) solution and the pseudocode would look something like this

for i = 0 to n
    for j = i to n
        for k = i to j
            invert(elements)
            count(number of 1s)
            revert(elements)

That is very high complexity and surely is not expected. But the solution for above problem can be condensed to O(n) complexity. Yeah! That’s great!! But how?

First count number of 1’s in given array and store them(C). Now make another array such that for all 0’s in given array, corresponding indexes in new array have value 1 and for all 1’s in given array, corresponding indexes have value of -1. Now find Maximum sub-array sum for this new array. It gives number of 1’s that would be added by the sub-array to actual array after being inverted/flipped. It also removes all previously counted 1’s in that part of sub-array. How? all 0’s are 1’s now which will be added to MaxSubarray sum and all 1’s are -1’s now which will be subtracted from that sum.

Adding C and M would result in number of maximum 1’s that could be formed as per the question.

C = 0
M = 0
for i = 0 to n
    if A[i] = 1
        C = C+1
for i = 0 to n
    if A[i] = 1
        B[i] = -1
    else if B[i] = 0
        B[i] = 1
M = MaxSubarraySum(B)
print C + M
Example :
Array     :  1 0 0  1 0  1  1 0 0 0  1 0 0  1  1  1  1 0 0  1
Inverting : -1 1 1 -1 1 -1 -1 1 1 1 -1 1 1 -1 -1 -1 -1 1 1 -1
Count of 1's = 10
Maximum Subarray sum = 4

Answer for given array = 10 + 4 = 14
Final Array : 1 0 0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1

Maximum Subarray Sum algorithm

This algorithm is used to find the maximum sum of a contiguous sub array in a given array of integers. If the set of integers include only positive integers, maximum sum would be sum of all the elements of array. But when the array include negative integers too, the problem comes of how to solve it efficiently.

A naive approach would be finding sum of elements of all sub arrays.

MaxSubarraySumNaive(a[])
    max = 0
    for i = 1 to n
        for j = i to n
            temp = 0
            for k = i to j
                temp = temp + a[i]
            if temp > max
                max = temp
    return max

That’s an O(n3) solution which is not at all appreciable. So let’s learn this algo which could solve this problem with an O(n) complexity.

MaxSubarraySum(a[])
    max_sum = 0
    temp = 0
    for i = 1 to n
        temp = max( 0 , temp+a[i] )
        max_sum = max( max_sum , temp )
    return max_sum

This short function solves the problem in real quick time. Working of the function with an example is shown below

For increasing i,
Array elements  : 1 -2 8 -1  6  3 -12  4 -16  5 10
temp values     : 1  0 8  7 13 16   4  8   0  5 15
max_sum values  : 1  1 8  8 13 16  16 16  16 16 16

Fast Doubling method to find nth Fibonacci number

One among very common questions asked in maths category in competitive programming is Fibonacci Series.

For a question that asks to find nth term of Fibonacci series, a naive approach to solve is an iterative method like

#define MOD 1000000007
long long int fib(long long int n)
{
    if(n < 2)
        return n;
    long long int a = 0,b = 1,ans;
    int i = 1;
    while(i < n)
    {
        ans = (a+b) % MOD;
        a = b;
        b = ans;
        i++;
    }
    return ans;
}

Above function has an O(n) complexity. With all our patience we may use it to calculate for at most n = 10^9 which gives output in around 10-15 seconds.

But as n gets larger, it takes hours,days,months,years,decades and so on for increasing n.

So the question is can we optimise it? Do we have methods to find nth Fibonacci number in less than a second?

Yes. We have few methods to do this. Out of them matrix exponentiation is most commonly used concept. Another well known concept is fast doubling method, which we are going to learn now.

Fast doubling is based on two formulae

F(2n) = F(n)[2*F(n+1) – F(n)]
F(2n + 1) = F(n)2 + F(n+1)2

Let us consider n starts from 0 and F(0) = 0. So our Fibonacci series would be F(0) = 0, F(1) = 1, F(2) = 1, F(3) = 2, F(4) = 3, F(5) = 5, F(6) = 8 …

For calculating terms, F(2n) & F(2n + 1), lets have a record of F(n) & F(n+1). By following this statement and taking care of equations and data type overflow, code would be as follows,

#include <bits/stdc++.h>

using namespace std;

#define MOD 1000000007;
long long int a,b,c,d;

void fast_fib(long long int n,long long int ans[])
{
    if(n == 0)
    {
        ans[0] = 0;
        ans[1] = 1;
        return;
    }
    fast_fib((n/2),ans);
    a = ans[0];             /* F(n) */
    b = ans[1];             /* F(n+1) */
    c = 2*b - a;
    if(c < 0)
        c += MOD;
    c = (a * c) % MOD;      /* F(2n) */
    d = (a*a + b*b) % MOD;  /* F(2n + 1) */
    if(n%2 == 0)
    {
        ans[0] = c;
        ans[1] = d;
    }
    else
    {
        ans[0] = d;
        ans[1] = c+d;
    }
}

int main()
{
    long long int n;        /* nth value to be found */
    scanf("%lld",&n);
    long long int ans[2]={0};
    fast_fib(n,ans);
    printf("%lld\n",ans[0]);
    return 0;
}

This code has a complexity of O(log n) which is way too faster than previously discussed function.

Travelling in a Maze

We might have come across problems asking number of possible paths to reach destination from source point. Lets see one such problem that can be solved with simple DP.

Question is, given a maze of dimensions MxN, and few obstructions, find number of paths that are possible starting at (1,1) and ends at (M,N). Also given that we can travel only to right or down from current position. ((1,1) will on top-left and (M,N) will be on bottom-right).

Lets once trace out for a maze with no obstructions. How many different paths are possible? There might be a mathematical formula for this. But let us solve it using DP. We will caluclate possible ways to reach each position starting from (1,1) and moving away from it towards (M,N).

Recursion formula would be,

f(X,Y) = 0 if either X = 0 or Y = 0
1 if X = 1 and Y = 1
f(X-1,Y)+f(X,Y-1) for rest of X,Y

For either X =0 or Y= 0, we never reach to those points, so number of paths leading to those points is 0.
For (X,Y) = (1,1), f(X,Y) = 1 because that is the source node. Only one possible way to reach there.
For rest of X and Y, reaching to that position is possible only from (X-1,Y) or (X,Y-1) as we can move only to right or down.

So tracing for X=4,Y=4, maze will become,

0 0 0 0 0
0 1 1 1 1
0 1 2 3 4
0 1 3 6 10
0 1 4 10 20

So to reach (4,4) from (1,1), there are 20 paths possible.

Now for any given obstructions, mark them 0 in the DP matrix and then apply above recursive formula for rest of the positions.

Code solving above question would be,

#include <iostream>;
#include <cstdio>;

using namespace std;

void travel_in_maze(int a[][100],int m,int n)
{
    int i,j;
    for(i = 0;i <= m;i++)
    {
        for(j = 0;j <= n;j++)
        {
            if(i == 0 || j == 0)
                a[i][j] = 0;
            else if(i == 1 && j == 1)
                a[i][j] = 1;
            else if(a[i][j] != 0)
                a[i][j] = a[i-1][j] + a[i][j-1];
        }
    }
}

int main()
{
    int m,n;
    int maze[100][100];
    int i,j;
    for(i = 0;i < 100;i++)
    {
        for(j = 0;j < 100;j++)
        {
            maze[i][j] = -1;
        }
    }
    scanf("%d %d",&m,&n);
    int obs; /* number of obstructions */
    int x,y;
    scanf("%d",&obs);
    for(i = 0;i < obs; i++)
    {
        scanf("%d %d",&x,&y);
        maze[x][y] = 0;
    }
    travel_in_maze(maze,m,n);
    printf("Number of paths = %d\n",maze[m][n]);
return 0;
}
Tracing for following case,
M = 5, N = 5
obs = 3
obstruction points = (1,3)
(5,1)
(3,2)

0 0 0 0 0 0
0 1 1 0 0 0
0 1 2 2 2 2
0 1 0 2 4 6
0 1 1 3 7 13
0 0 1 4 11 24

Number of paths = 24.

Lazy Caterer’s Sequence

That’s an interesting name! Has an interesting concept too. Lets say you have a large cake. In N cuts, what is the maximum number of pieces you could cut this cake into, given that cuts always follow straight line? Do you have any answer for it? Well if no, maximum number of pieces follows Lazy Caterer’s Sequence.

Starting with N = 0, as N increases sequence is
1, 2, 4, 7, 11, 16, 22, 29, 37, 46, 56, 67, 79, 92, 106, 121, 137, …

Now it would be great if you could find any relation in this sequence. Did you? Well let me reveal it to you. Observe that f(n) = (n*(n+1))/2 + 1.

That made the sequence a lot simpler right? But how did this sequence come up? Lets derive it..

For any cut that you could make, you can achieve maximum number of pieces if you pass through all previous cuts. Lets say for nth cut, it should pass through all n-1 previously made cuts and at the same time not along any intersections. Thus the line itself divides into n segments each dividing their respective piece of cake into two parts. Hence for nth cut, you get n new pieces of cake. (If you are passing through an intersection of two cuts, you are loosing a piece of cake for that cut. And later on, a lot more.)

Maximum number of pieces for n cuts thus forms a recurrence relation,
f(n) = n + f(n-1).

Expanding the relation,

f(n) = n + (n-1) + f(n-2)
f(n) = n + (n-1) + (n-2) + f(n-3)
.
..
.
f(n) = n + (n-1) + (n-2) + ... 1 + f(0)

f(0) = 1 as there is one piece of cake when no cuts are made.

Therefore, f(n) = Sum of first n natural numbers + 1

Thus relation is f(n) = (n*(n+1))/2 + 1.

Lazy_Caterer's_Sequence_(Cuts)

Problem related to this concept: Joyfest and Joyful Cake

Polynomial Evaluation using Horner’s Method

Let suppose we have an n-degree polynomial expression

F(x) = cn.xn + cn-1.xn-1 + cn-2.xn-2 + . . . + c1.x + c0

Here cn, cn-1, cn-2, … c0 are integral coefficients.

Now we need to evaluate the polynomial for some given value x. A naive approach for solving would take O(n2) complexity, which costs lots of time in solving this kind of problem.

We can use Horner’s method to solve this in an efficient way. For solving this problem using Horner’s method, the given equation can be written in a form of nested multiplication as

F(x) = ((...(((cn*x + cn-1)*x + cn-2)*x + cn-3)*x + . . . )*x + c0

Ex: Let we have a polynomial f(x) = 6.x3 – 3.x2 + 2.x + 1
We shall evaluate this polynomial for x = 4 using Horner’s Method.
The expression would be (((6*4 -3)*4 + 2)*4 + 1 = 345
Solving it directly, 6*(43) – 3*(42) + 2*(4) + 1 = 345

Horner’s Method implementation in C++

#include <iostream>

using namespace std;

int horner(int n,int c[],int x)
{
    int ans = c[0];
    int i = 0;
    while(i < n)
    {
        ans = ans*x + c[i+1];
        i++;
    }
    return ans;     /*returns evaluated value of polynomial with x*/
}

int main()
{
    int n;          /*degree or order of polynomial*/
    cout<<"Enter degree of polynomial : "; 
    cin>>n;
    int c[n+1];     /*this contains coefficients of the polynomial*/
    int i = 0;
    cout<<"Enter n+1 coefficients of polynomial : ";
    while(i <= n)
    {
        cin>>c[i];
        i++;
    }
    int x;          /*value with which polynomial should be evaluated*/
    cout<<"Enter value of x : "; 
    cin>>x;
    cout<<"\nEvaluated value of x in polynomial is : ";
    cout<<horner(n,c,x)<<endl;
    return 0;
}

Output :

Enter degree of polynomial : 3
Enter n+1 coefficients of polynomial : 6 -3 2 1
Enter value of x : 4

Evaluated value of x in polynomial is : 345

Complexity of evaluation of polynomial is now reduced to O(n). We can see the considerable amount of change in efficiency by using Horner’s Method for this problem.

Problems : POLEVAL(SPOJ)

Fast integer input function in C

There can be few problems on online judges with large input data. Using traditional funcitons like scanf() for taking input would not work in such cases. So a function for taking faster inputs does effect final result.

Here is a function that reduces execution time in taking inputs of integeral numbers.

int get_num()
{
	int num = 0;
	char c = getchar_unlocked();
	while(!(c>='0' && c<='9'))
		c = getchar_unlocked();
	while(c>='0' && c<='9')
	{
		num = (num<<3) + (num<<1) + c -'0';
		c = getchar_unlocked();
	}
	return num;
}

How it works?

getchar_unlocked() is the function in C that takes inputs of character. It is much much faster in taking an input compared to scanf().

Coming to the functioning of function, c is a character variable and num is integer variable in which input number will be taken. Initially taking ‘c’ and checking if it lies in values between ‘0’ and ‘9’(It checks in ASCII order). Once you find the value of ‘c’ in the range, it gets into second while loop. Here, num value is changing the every time. It is indeed multiplied by 10, when everytime the while loop is repeated. Finally while loop breaks when c is some other character other than integral digit(in general will be a space or ‘\n’).

Atlast it returns the given input number. But this function is only for +ve integers. We can make a function for taking numbers including -ve numbers also.

It goes this way..

int get_num()
{
	int num = 0;
	char c = getchar_unlocked();
	int flag = 0;
	while(!((c>='0' & c<='9') || c == '-'))
		c=getchar_unlocked();
	if(c == '-')
	{
		flag = 1;
		c=getchar_unlocked();
	}
	while(c>='0' && c<='9')
	{
		num = (num<<1)+(num<<3)+c-'0';
		c=getchar_unlocked();
	}
	if(flag==0)
		return num;
	else
		return -1*num;
}

There is another function using fread() which takes much faster input.. you can read about that here.. FAST_I/O