×

# TLE in SUMTHING

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

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


}

3★arpanb8
1201312
accept rate: 13%

I received a score of 30...

(05 Jan '15, 21:01) 3★

 1 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! answered 05 Jan '15, 22:25 0★idraumr 246●3 accept rate: 45% tnx...@idraumr!!! I'll try it out as soon as I wake up!!! (05 Jan '15, 22:35) arpanb83★

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

Here it is:

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

3★arpanb8
1201312
accept rate: 13%

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!

(05 Jan '15, 23:13) 0★

thanks @idraumr It worked...

(06 Jan '15, 23:31) 3★
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

question asked: 05 Jan '15, 20:21

question was seen: 1,733 times

last updated: 06 Jan '15, 23:31