You are not logged in. Please login at www.codechef.com to post your questions!

×

TLE in SUMTHING

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...

asked 05 Jan '15, 20:21

arpanb8's gravatar image

3★arpanb8
120311
accept rate: 13%

I received a score of 30...

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

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!

link

answered 05 Jan '15, 22:25

idraumr's gravatar image

0★idraumr
2463
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 "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; }

link

answered 05 Jan '15, 22:42

arpanb8's gravatar image

3★arpanb8
120311
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) idraumr0★

thanks @idraumr It worked...

(06 Jan '15, 23:31) arpanb83★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×29

question asked: 05 Jan '15, 20:21

question was seen: 861 times

last updated: 06 Jan '15, 23:31