SPOJ #4177. Herding editorial

The question asks for the number of disjoint groups in which the cats can move. For a cat in a square, it always moves in one direction of {North, South, East, West}. It is provided that cats never go outside the city. This information is helpful in building a simple solution using stl in C++.

  • Take the input matrix in an array of strings.
  • Make a map(squares) with each index as key and random value(say 1) as its value. map< pair<int,int>, int > squares. (squares will have N*M elements.)
  • Take an empty array(A) of size N*M. int A[N][M].
  • Take an empty vector(V) and a variable “temp” initialised to 1.
  • Run a loop until the map is not empty.
    • Add a random value(say 1) into vector V.
    • Take the key of first element of map(squares) and run a loop // to trace the path along with given directions.
      • Mark the index in A with value of temp.
      • Erase the element from map having the key as the current index.
      • Find the next index according to the direction given in current index.
      • If next index is already visited and has a value less than temp, remove an element from vector V and come out of loop.
      • If next index is already visited with the same value as temp, just come out of loop.
      • If next index is not visited, continue the loop.
    • Increment value of temp.
  • The size of vector V is the answer.

The reason for why size of vector is the answer? We are incrementing number of groups by 1 whenever we find a new group, by adding an element into the vector. If we find that a group leads to an already traversed group, we are not counting that group by removing an element from the vector.

Coding is left for you. Leave a comment to this post if you have any difficulty in understanding or in coding.

Link to the problem HERDING.

Advertisements

Multiplying large numbers in C/C++

Working with large numbers in C/C++ is always a problem. Those who have knowledge in Java/python tend to code in these languages for those particular problems. (Java has a BigInteger class where in there is no limit for integer range you work on. Python doesn’t have any limits on integers.) For those who wanted to handle large numbers in C/C++, lets discuss an approach for how to multiply large numbers.

We use arrays to store the numbers.
Why? Because we do not have any data type which could store big integers say around 10^3 digits.
How? Each digit of integer is stored in each index in the array. Lets store them in reverse order for simpler calculations.

Now we have two integers(A,B) in array each of length L1,L2 respectively. Product of these two numbers will be at most L1+L2. So lets take an empty Ans[] array of size 2*N.

Procedure :

Step 1 : Multiply index i of B with all the indexes j of A. Add the product to value in Ans[k] where 0 <= i < L2, 0 <= j < L1, k = i+j.
Step 2 : Repeat step 1 till i = L2. (Picture how you multiply two large numbers on a paper).
Step 3 :
for each i in range(0,L1+L2)
TMP = X/10. X = X%10. Y = Y+TMP.
X = A[i]
Y = A[i+1]
TMP = temporary variable.
Step 4 : reverse the array Ans, and that will be the final product.

Code:

#include <stdio.h>
#include <string.h>

int main()
{
    int a[100],b[100];
    int ans[200]={0};
    int i,j,tmp;
    char s1[101],s2[101];
    scanf(" %s",s1);
    scanf(" %s",s2);
    int l1 = strlen(s1);
    int l2 = strlen(s2);
    for(i = l1-1,j=0;i>=0;i--,j++)
    {
        a[j] = s1[i]-'0';
    }
    for(i = l2-1,j=0;i>=0;i--,j++)
    {
        b[j] = s2[i]-'0';
    }
    for(i = 0;i < l2;i++)
    {
        for(j = 0;j < l1;j++)
        {
            ans[i+j] += b[i]*a[j];
        }
    }
    for(i = 0;i < l1+l2;i++)
    {
        tmp = ans[i]/10;
        ans[i] = ans[i]%10;
        ans[i+1] = ans[i+1] + tmp;
    }
    for(i = l1+l2; i>= 0;i--)
    {
        if(ans[i] > 0)
            break;
    }
    printf("Product : ");
    for(;i >= 0;i--)
    {
        printf("%d",ans[i]);
    }
    return 0;
}

Input :
150353265326
22055653351

Output:
Product : 3316139500221184007426

Related problems : Small Factorials(FCTRL2)
My Solution for Small Factorials

Maximum number of 1’s in a submatrix of given area in a binary matrix

Firstly, let me make the statement clear. You will be given a binary matrix. A binary matrix is one which only consists of 1’s and 0’s. You will be asked to find a maximum number of 1’s in rectangular sub-matrix of a given area.

Naive Approach:
Find all possible rectangles for given area.
For all possible rectangles in given matrix, find number of 1’s in given area.

(I will be discussing for a square matrix of dimensions NxN. Similar solution for any rectangular matrix can be constructed)

for(i = 1;i <= N;i++)
{
	if(area%i == 0 && area/i <= N) 
	{//(area/i) should be less than N else the rectangle goes is out of NxN
		x = i;
		y = area/i;
		for(j = 1;j <= N;j++)
		{
			for(k = 1;k <= N;k++)
			{
				if(j+x-1 <= N && k+y-1 <= N)
				{//checking if other ends lie in range of matrix dimensions
					temp = 0;
					for(l = j; l <= j+x-1 ; l++)
					{//here I find number of 1's in the rectangle
						for(m = k;m <= k+y-1; m++)
						{
							if(a[l][m] == 1)
								temp++;
						}
					}
					if(temp > max)
						max = temp;
				}
				if(j+y-1 <= N && k+x-1 <= N)
				{//this is another rectangle of same dimensions but different orientation
					temp = 0;
					for(l = j; l <= j+y-1 ; l++)
					{
						for(m = k;m <= k+x-1; m++)
						{
							if(a[l][m] == 1)
								temp++;
						}
					}
					if(temp > max)
						max = temp;
				}
			}
		}
	}
}
printf("%d\n",max);

This approach takes a long time to give output for even a values of N around 100. Let us now learn a better approach to this problem.

Solving using Dynamic programming :
We can construct a 2d DP where dp[x][y] has number of 1’s in submatrix a[i][j] where 1 ≤ i ≤ x and 1 ≤ j ≤ y.
The DP can be constructed by this formula

dp[i][j] = 	dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]	    ,if a[i][j] = 0
		dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + 1  ,if a[i][j] = 1

In single statement,

dp[i][j] =     dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + a[i][j]

Understanding the formula : For dp[x][y], we add (number of 1’s in sub-matrix a[i][j], where 1 ≤ i ≤ x and 1 ≤ j ≤ y-1) and (number of 1’s in sub-matrix a[i][j], where 1 ≤ i ≤ x-1 and 1 ≤ j ≤ y).
In doing this we add a sub-matrix a[i][j], where 1 ≤ i ≤ x-1 and 1 ≤ j ≤ y-1 twice. So we subtract that value from the sum.
And lastly, we check if the value at a[i][j] is 1 or not and add the value to sum.

Now we find all possible dimensions of the rectangles, and find number of 1’s in all these rectangles. Return maximum of values found as answer.

How to find number of 1’s in a rectangle now? For example, you are at index (x,y) and dimensions of rectangle is (r,s), number of 1’s in that rectangle would be,

dp[x+r-1][y+s-1] - (dp[x+r-1][y-1] + dp[x-1][y+s-1]) + dp[x-1][y-1].

This is much similar as the way in DP formula that we discussed earlier.

void constructDP(int a[][1001],int dp[][1001])
{
	for (int i = 0; i <= n; ++i)
	{
		dp[0][i] = 0;
		dp[i][0] = 0;
	}
	for (int i = 1; i <= n; ++i)
	{
		for(int j = 1;j <= n; ++j)
		{
			dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + a[i][j];
		}
	}
}

int solve(int a[][1001],int dp[][1001],int n)
{
	constructDP(a,dp);
	ans = INT_MAX;
	for (int i = 1; i <= n; ++i)
	{
		if(count%i == 0 && count/i <= n)
		{
			x = i;
			y = count/i;
			for(int j = 1;j <= n;j++)
			{
				for(int k =1; k <= n;k++)
				{
					if((j+x-1 <= n) && (k+y-1 <= n))
						ans = max(ans, dp[j+x-1][k+y-1]-dp[j-1][k+y-1]-dp[j+x-1][k-1]+dp[j-1][k-1]);
					if((j+y-1 <= n) && (k+x-1 <= n))
						ans = max(ans, dp[j+y-1][k+x-1]-dp[j-1][k+x-1]-dp[j+y-1][k-1]+dp[j-1][k-1]);
				}
			}
		}
	}
	return ans;
}

Using the function, you can note that, with a O(N2) pre-computation, we reduce a query of finding number of 1’s in a rectangle every time from O(N2) to O(1).

Problems related with this concept : SWAPMATR

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

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.

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)