TLE in SUMTHING

general
1

I’m getting a TLE in SUMTHING from the INOI Practice Server…
Here’s my C++ source code:

#include “iostream”
#include “cmath”
#include “string”
#include “algorithm”

using namespace std;

int main()

{

int n;
cin >> n;
string x;
cin >> x;
int k, z;
cin >> k;
int xyz[n];
int sum[n-1];
for (int i = 0; i<=n-1; i++)
{
	if (i<n-1)
	sum[i]=0;
	xyz[i]=(int)x.at(i)-48; 
}
int ans;
for (int p = 1; p<=n-1; p++)
{
	sort (sum, sum+n-1);
	sum[n-1-p]=1;
	
	do
	{
		ans=0;
		z=1;
		for (int q = n-1; q>=0; q--)
		{
			if (q<n-1 && sum[q]==1)
			z=1;
			else
			z++;
			ans+=pow(10, z)*xyz[q];
		}
		if (ans==k)
		{
			cout << p;
			return 0;
		}
	}while(next_permutation(sum, sum+n-1));
}
cout << "-1";
return 0;

}

PLEASE HELP ME SPEED IT UP…

2

I received a score of 30…

3

Hey,

I’ll give you a quick hint: think of it as a dynamic programming problem. For each position onwards in the input number, you store the least number of ‘+’ required to get a sum from 0 to T. You do this from the end to the beginning. The answer would be the least number of ‘+’ required from position 0 onwards, to make a sum of ‘T’.

Cheers!

1 Like
4

tnx…@idraumr!!! I’ll try it out as soon as I wake up!!!

5

@idraumr: Plz. find out what’s wrng in the 0/1 tiles (iarcs online judge) solution of mine

Here it is:
#include “iostream”
#include “algorithm”

using namespace std;

int main()
{
int n;
cin >> n;
long long int x[n+1];
x[0]=1;
x[1]=2;
for (int p = 2; p<=n-1; p++)
{
x[p]=x[p-1]+x[p-2];
}
cout << x[n-1]%15746;
return 0;
}

6

I think you should have made a new thread out of this.

Anyway, the answer starts from the 3rd element of the fibonacci sequence. Try finding out the answer for small input numbers. 50 or so. That, in itself, is a large number. For larger input values, the answer quickly goes out of the range of a 64-bit signed integer.

The fix is simple. Change the loop’s body to x[p] = (x[p - 1] + x[p - 2]) % MOD_VALUE;. Also note that you don’t need such a big array, as only the last two values are significant.

Cheers!

7

thanks @idraumr It worked…