Large matrix problem ...

[pirlo89]

Hi,

I have a problem i have been working on: http://drdash.acm-acpc.org/problems/view/119 . The way i see it, you can solve it easily if you have tons of RAM. Or, you can solve it on your computer but Drdash (the website used to submit the solution) wont accept it. By creating files and storing each matrix in a text file.

Is there a way to solve it without creating the matrix (or at least not all of it) ?

Here is my try : http://pastebin.com/kE2xck8e

[hamsterman]

You don't have to brute force it. This problem has a rather simple divide-and-conquer kind of solution. Consider for example that sum( N = 2, R = 2, S = 0, E = 2 ) = sum( N = 1, R = 0, S = 0, E = 1 ) - sum( N = 1, R = 0, S = 0, E = 0).

[pirlo89]

I'm sorry but i don't quite get your answer. Could you explain it ?

I tried another way but it seems that it just needs a little tweaking. Could someone take a look at it ...

int result(int N, int R, int S, int E, int inverse)
{
	const int half = pow(2, N-1);
	if (N==0)
		return inverse;
	else if (R < half)
	{
		if ( E<half || S>=half )
			return result(N-1, half-R, S, E, inverse);
		else
			return ( result(N-1, half-R, half-S-1, half-1, inverse)+result(N-1, half-R, half, E, inverse) );
	}
	else
	{
		if (E<half)
			return result(N-1, R-half, S, E, inverse);
		else if (S>=half)
			return result(N-1, R-half, S, E, inverse*-1);
		else
			return ( result(N-1, R-half, half-S-1, half-1, inverse)+result(N-1, R-half, half, E, inverse*-1) );
	}
}

[hamsterman]

That is what I meant.
It seems to me that you don't calculate new S and E properly. Use min and max functions to divide the ranges. That is, pass min(S, half-1), min(E, half-1) to she first side and max(S, half), max(E, half) to the second one. Also, at the beginning of the function, add if(S==E) return 0;.
When you do that, you won't need all those ifs. Just check whether R is more or less than half.
Note that you don't really need that inverse. result(..., -1) = result(..., +1)*(-1). Though it might be good to keep it. Now you can do cout<<inverse before returning it to see how the row looks and where the problem is.

[pirlo89]

I have done what you asked but there seems to be an infinite loop ...

int result(int N, int R, int S, int E, int inverse)
{
	const int half = pow(2, N-1);

	// reached the base case
	if (N==0)
		return inverse;
	else if (S==E)
		return 0;

	// if R is in the upper half
	else if (R < half)
	{
		return ( result(N-1, R, min(S, half-1), min(E, half-1), inverse)+result(N-1, R, max(S, half), max(E, half), inverse) );
	}

	// if R is in the lower half
	else
	{
		return ( result(N-1, R-half, min(S, half-1), min(E, half-1), inverse)+result(N-1, R-half, max(S, half), max(E, half), inverse*-1) );
	}
}

But in the case of if(S==E) , i don't think that it means that it should return 0; as you specified. It just means return the value of a single element, right ?

[hamsterman]

I don't see how this could go infinitely. N will reach 0 eventually.. Not that it matters.
You're right about S==E. I forgot that range is inclusive and assumed [S;E). Change that to S>E.
Note that with S>E, we only need to cut one of them. That is, the first call to result should be
result( N-1, R, S, min( E, half-1 ), inverse )
There's one very important thing we both ignored. When R >= half, you pass R-half to the next result() to fix the offset. Same should be done with S and E with the right result() calls. The right side of the first return would thus be
result( N-1, R, max( S, half )-half, E-half, inverse)

[pirlo89]

Still doesn't work, infinite loop ...

int result(int N, int R, int S, int E, int inverse)
{
	const int half = pow(2, N-1);

	// reached the base case
	if (N==0)
		return inverse;
	else if (S>E)
		return 0;

	// if R is in the upper half
	else if (R < half)
	{
		return ( result(N-1, R, S, min(E, half-1), inverse)+result(N-1, R, max(S, half)-half, max(E, half)-half, inverse) );
	}

	// if R is in the lower half
	else
	{
		return ( result(N-1, R-half, S, min(E, half-1), inverse)+result(N-1, R-half, max(S, half)-half, max(E, half)-half, inverse*-1) );
	}
}

[pirlo89]

I took what you said (about changing the offset) and changed a little bit in my previous code. And it works !!!

#include <iostream>
#include <cmath>
#include <fstream>
using namespace std;

ifstream in("matrix.in");

long long int result(long long int N, long long int R, long long int S, long long int E, long long int inverse)
{
        // reached the base case
        if (N==0)
                return inverse;

        const long long int half = pow(2, N-1);

        // if R is in the upper half
        if (R < half)
        {
                if (E<half)                     /*if the sum required is in the first quarter*/
                        return result(N-1, R, S, E, inverse);
                else if (S>=half)            /*if the sum required is in the second quarter*/
                        return result(N-1, R, S-half, E-half, inverse);
                else                            /*if the sum required is shared between the first and the second quarter*/
                        return ( result(N-1, R, S, half-1, inverse)+result(N-1, R, 0, E-half, inverse) );
        }

        // if R is in the lower half
        else
        {
                if (E<half)                     /*if the sum required is in the third quarter*/
                        return result(N-1, R-half, S, E, inverse);
                else if (S>=half)                       /*if the sum required is in the fourth quarter*/
                        return result(N-1, R-half, S-half, E-half, inverse*-1);
                else                            /*if the sum required is shared between the third and the fourth quarter*/
                        return ( result(N-1, R-half, S, half-1, inverse)+result(N-1, R-half, 0, E-half, inverse*-1) );
        }
}

int main()
{
        long long int N, R, S, E;

        in>>N>>R>>S>>E;

        while (N!=-1 && R!=-1 && S!=-1 && E!=-1)
        {
                cout<<result(N, R, S, E, 1)<<endl;

                in>>N>>R>>S>>E;
        }

        return 0;
}

Thank you so very much for your help :D
You have done me a great favor. If you somehow need any programming help let me know X)

I am so happy right now :D
Thanks again.