Time Limit Exceeded

[John3682]

hey

i keep getting "Time Limit Exceeded"(it needs to be 0.5 sec) on this code can someone help me with this . (and improve it if u dont mind ty )

Compiled Successfully
Test 1
ACCEPTED
Test 2
ACCEPTED
Test 3
ACCEPTED
Test 4
ACCEPTED
Test 5
ACCEPTED
Test 6
ACCEPTED
Test 7
ACCEPTED
Test 8
ACCEPTED
Test 9
ACCEPTED
Test 10
ACCEPTED
Test 11
WRONG ANSWER
Test 12
Time Limit Exceeded
Test 13
ACCEPTED
Test 14
ACCEPTED
Test 15
ACCEPTED
Test 16
ACCEPTED
Test 17
Time Limit Exceeded
Test 18
ACCEPTED

#include <iostream>
#include <chrono> 
using namespace std;
using namespace chrono;


void Ure();

int main()
{
	auto start =high_resolution_clock::now();
	Ure();
	cout << endl;
	auto stop =high_resolution_clock::now();
	auto duration =duration_cast<microseconds>(stop - start);
	cout << duration.count();

	return 0;
}

void Ure() 
{
	int n, x, y;

	cin >> n >> x >> y;

	for (int i = 1; i <= n; i++)
	{
		if (x * i == n)
		{
			cout << i << " " << 0;
			return;
		}

		if (y * i == n)
		{
			cout << 0 << " " << i;
			return;

		}

		for (int j = 1; j <= n; j++)
		{
			if ((i * x) + (j * y) == n)
			{
				cout << i << " " << j;

				return;
			}
		}
	}


	cout << -1;

	exit;

}

The output consists of two numbers that are separated by a distance. These numbers should represent the number of times that he has to keep his foot Longitudinal and transverse(till his foot is tangent with wall ). There may be several answers for one entry. You can print any one you like. If there was no way for him to tangent to the wall, just print a -1 in the output.

n = number of steps
x = length of his feet
y = width of his feet

Example :

10 2 3

2 2

-----------

10 4 7

-1

----------


***UPDATE (ASSIGNMENT):

The game is that he stands at a distance of n cm from the wall and wants to reach the wall. To do this, he can put his foot in front of his other foot Longitudinal or transverse(till his foot is tangent with wall ) .u need to tell him to keep this several times to eventually travel the exact distance n cm and tangle with the wall. Or tell him this is impossible.

In the only input row you are given three numbers n, x, and y, representing his distance to the wall and the length and width of the his legs, respectively.

[Handy Andy]

Hello John3682,

The first thing I see is the code you posted does not match the output that you provided. I have no idea where the "Time Limit Exceeded" is coming from.

Line 56. Where did you define the variable "exit" because I can not find it. Did you mean the function "exit()"? But this would leave the program at that line.

As a void function there is no need to return or exit the function. When you reach the closing } of the function it will return to where it was called from.

You wrote:

n = number of steps
x = length of his feet
y = width of his feet

If you have to explain what these variables are then you need better names:

numSteps for 'n'
footLength for 'x'
footWidth for 'y'

With something like this there is no question what they are.

Your program records a start time then calls the function where you enter three numbers. So how fast can you type? The longer it takes to enter these numbers the longer the time is. If the "Time Limit Exceeded" is to be based on how long the function takes then you need to input the numbers before you record start time and when calling the function pass the variables to the function. Then you will be dealing with the amount of time it takes the function to return.

Andy

[thmm]

Looks like a codechef challenge.
What don't you show us the link to the challenge so we know what this is about.

[jonnin]

most likely you are supposed to find a way to make the loop at 42 not a loop. At the very least, it does too many iterations: you can stop the loop if you exceed N as every answer after that will also exceed N.

But I think you can solve it for I and J instead of iterating it? i,x,and y are constant that line for that outer loop iteration.

if ( (n-ix)/y <= n) then its solved, right? or maybe check both sides, >= 1 as well... watch the integer math etc...

[John3682]

hi Handy Andy (funny name btw XD ) , ty for answering .

so ive deleted all the unnecessarily parts (including that exit u mentioned), and i still get the same result .


1<= n,x,y <= 100000

#include <iostream>
using namespace std;
int main()
{
	int n, x, y;         
	
	cin >> n >> x >> y;

	for (int i = 1; i <= n; i++)
	{
		if (x * i == n)
		{
			cout << i << " " << 0;
			return 0;
		}

		if (y * i == n)
		{
			cout << 0 << " " << i;
			return 0;

		}

		for (int j = 1; j <= n; j++)
		{
			if ((i * x) + (j * y) == n)
			{
				cout << i << " " << j;

				return 0;
			}
		}
	}

	cout << -1;
}

the execution time must be under 0.5 sec and i dont know how to solve the time limit exceeded problem .


also this part was just to tell u what i meant by the variables , and i their meaning has no part in code :

n = number of steps
x = length of his feet
y = width of his feet

[jlb]

Please show the text of the entire "assignment".

The output you showed appears to be the output of some automated grading system, so it appears that your code is not fulfilling all of the "assignment" requirements.

[zapshe]

Instead of the initial conditions in your loop, you can just check if x divides n. if n % x is 0, then cout n/x since that's your answer. This way, you don't have to go through 2 if statements that do math every time you loop.

The way to achieve better time complexities is to use an understanding of the mathematical problem rather than to brute force the answer through a nested loop like yours. I'm sure there's some kind of formula that could be used that could at least cut your code down to a single loop.

[John3682]

hey yall

(ive put the actual assignment , since it wasn't in english i had to use gt hence srry for the grammar)

zapshe :


i did what u said (ty for answering btw) :

#include <iostream>
using namespace std;
int main()
{
	int n, x, y,G = 0;         
	
	cin >> n >> x >> y;

	if (n % x == 0)
	{
		G = n / x;
		cout << G << " " << 0;
		return 0;
	}

	if (n % y == 0)
	{
		G = n / y;
		cout << 0 << " " << G;
		return 0;

	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if ((i * x) + (j * y) == n)
			{
				cout << i << " " << j;

				return 0;
			}
		}
	}

	cout << -1;
}

but i still have the same problem , (code works fine in my pc without time limit)

i THINK this part is taking most of the execution time :

for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if ((i * x) + (j * y) == n)
			{
				cout << i << " " << j;

				return 0;
			}
		}
	}

[jlb]

***UPDATE (ASSIGNMENT):

The game is that he stands at a distance of n cm from the wall and wants to reach the wall. To do this, he can put his foot in front of his other foot Longitudinal or transverse(till his foot is tangent with wall ) .u need to tell him to keep this several times to eventually travel the exact distance n cm and tangle with the wall. Or tell him this is impossible.

In the only input row you are given three numbers n, x, and y, representing his distance to the wall and the length and width of the his legs, respectively.

Okay, and what exactly are the limits on n, x, and y if any?

[zapshe]

Try this:

int result;

for (int i = 1; i <= n; i++)
{
	for (int j = 1; j <= n; j++)
	{
                result = (i * x) + (j * y);

                if(result > n)
                        break;

		if (result == n)
		{
			cout << i << " " << j;
			return 0;
		}
	}
}

This way, if the number exceeds n, you break out of the nested loop since you know you've already shot passed n, and you won't have unnecessary loops.


Try coming up with some of these optimization tricks yourself :)

[John3682]

hey jlb

1<= n,x,y <= 100000

[John3682]

NJ ZAPSHE u did it ; )

Compiled Successfully
Test 1
ACCEPTED
Test 2
ACCEPTED
Test 3
ACCEPTED
Test 4
ACCEPTED
Test 5
ACCEPTED
Test 6
ACCEPTED
Test 7
ACCEPTED
Test 8
ACCEPTED
Test 9
ACCEPTED
Test 10
ACCEPTED
Test 11
WRONG ANSWER
Test 12
ACCEPTED
Test 13
ACCEPTED
Test 14
ACCEPTED
Test 15
ACCEPTED
Test 16
ACCEPTED
Test 17
ACCEPTED
Test 18
ACCEPTED

the time limit is gone thanks to u , now i just have to find the last error XD

***update :

ok so i cdnt find the last error , what do u think it might be ?

Test 11
WRONG ANSWER

ty in advance

***UPDATE :

i found the part where the error happens :

//with this error 11 is gone but more than one error happens :

			if (result > n) {
				cout << -1;
				return 0;
			}

//with this error 11 remain but checks the rest :


if(result > n)
                        break;

ps : I THINK the answer to test 11 is -1

[John3682]

can someone help me with the last error ?

[dutch]

The problem description is meaningless:

The game is that he stands at a distance of n cm from the wall and wants to reach the wall. To do this, he can put his foot in front of his other foot Longitudinal or transverse(till his foot is tangent with wall ) .u need to tell him to keep this several times to eventually travel the exact distance n cm and tangle with the wall. Or tell him this is impossible.

In the only input row you are given three numbers n, x, and y, representing his distance to the wall and the length and width of the his legs, respectively.

[zapshe]

What are the inputs for test 11?

[John3682]

no idea zapshe .

[zapshe]

Can't help without knowing the input :( You should be able to get it? Is there a link to this problem?

[ne555]

1<= n,x,y <= 100000
perhaps you have overflow
try replacing int with unsigned long long int

also, http://cplusplus.com/forum/beginner/268977/#msg1157267 to avoid the inner loop

[John3682]

its not in english ,imma figure it out by meself XD . tysm for all ur help

[lastchance]

#include <iostream>
using namespace std;

bool trial( int &i, int &j, int x, int y, int n )
{
   if ( !x )
   {
      i = 0;
      j = n / y;
      return !( n % y );
   }
   else
   {
      int ip, jp;
      bool result = trial( ip, jp, y % x, x, n );
      j = ip;
      i = jp - j * ( y / x );
      return result;
   }
}


int main()
{
   int x, y, n, i, j;

   cin >> n >> x >> y;

   if ( !trial( i, j, x, y, n ) )
   {
      cout << -1 << '\n';
   }
   else
   {
      if      ( j < 0 ) { j += ( i / y ) * x;  i %= y; }
      else if ( i < 0 ) { i += ( j / x ) * y;  j %= x; }
      if ( i >= 0 && j >= 0 )
      {
//       cout << i << " x " << x << " + " << j << " x " << y << " = " << n << '\n';
         cout << i << " " << j << '\n';
      }
      else
      {
         cout << -1 << '\n';
      }
   }
}