How to reduce run time of my code to solve Cycle race practice problem from geeksforgeeks
up vote
-3
down vote
favorite
I am referring to this problem https://practice.geeksforgeeks.org/problems/cycle-race/0.
The Problem description:
Jack and Jelly are two friends. They want to go to a place by a cycle ( Assume that they live in same house). Distance between the place and their house is 'N' km. Rules of game are as follows:
- Initially Jelly will ride cycle.
- They will ride cycle one by one.
- When one is riding cycle other will sit on the carrier of cycle.
- In each ride they can ride cycle exactly 1, 2 or 4 km. One cannot ride more than remaining distance.
- One who reaches school riding cycle will win.
Both play optimally. You have to find who will win this game.
Input:
First line of input contains an integer 'T' denoting the number of test cases. Then 'T' test cases follow. Each test case consists of a single line containing an integer N.
Output:
Print the name of winner i.e 'JACK' or 'JELLY'.
I have written following code for this problem.
Bottom-up approach solution gives me time out.
The top-down approach gives me Segfault. Most probably due to recursion stack.
How can I improve my solution?
Please help me.
Thanks in advance.
Bottom Up (Timeout):
#include <iostream>
using namespace std;
bool arr[2][10000001];
int main() {
int t, n;
cin >> t;
while(t--) {
cin >> n;
arr[0][1]=arr[0][2]=arr[0][4]=0;
arr[1][1]=arr[1][2]=arr[1][4]=1;
arr[0][3]=1;
arr[1][3]=0;
for(int i=5;i<=n;i++) {
for(int player=0;player<2;player++) {
if(arr[1-player][i-1]==player||
arr[1-player][i-2]==player||
arr[1-player][i-4]==player) {
arr[player][i] = player;
} else {
arr[player][i] = 1-player;
}
}
}
if(!arr[0][n]) {
cout << "JELLY" << endl;
} else {
cout << "JACK" << endl;
}
}
return 0;
}
Top-down (Segfault, I think due to recursion):
#include <iostream>
using namespace std;
char arr[2][10000001];
bool solve(int n, bool player) {
if(arr[player][n] != -1)
return arr[player][n];
if(solve(n-1,!player) == player ||
solve(n-2,!player) == player ||
solve(n-4,!player) == player) {
arr[player][n] = player;
} else {
arr[player][n] = !player;
}
return arr[player][n];
}
int main() {
int t, n;
cin >> t;
while(t--) {
cin >> n;
for(int i=0;i<2;i++) {
for(int j=0;j<n+1;j++) {
arr[i][j] = -1;
}
}
arr[0][1]=arr[0][2]=arr[0][4]=0;
arr[1][1]=arr[1][2]=arr[1][4]=1;
arr[0][0]=arr[0][3]=1;
arr[1][0]=arr[1][3]=0;
solve(n, false);
if(!arr[0][n]) {
cout << "JELLY" << endl;
} else {
cout << "JACK" << endl;
}
}
return 0;
}
c++ algorithm programming-challenge time-limit-exceeded
add a comment |
up vote
-3
down vote
favorite
I am referring to this problem https://practice.geeksforgeeks.org/problems/cycle-race/0.
The Problem description:
Jack and Jelly are two friends. They want to go to a place by a cycle ( Assume that they live in same house). Distance between the place and their house is 'N' km. Rules of game are as follows:
- Initially Jelly will ride cycle.
- They will ride cycle one by one.
- When one is riding cycle other will sit on the carrier of cycle.
- In each ride they can ride cycle exactly 1, 2 or 4 km. One cannot ride more than remaining distance.
- One who reaches school riding cycle will win.
Both play optimally. You have to find who will win this game.
Input:
First line of input contains an integer 'T' denoting the number of test cases. Then 'T' test cases follow. Each test case consists of a single line containing an integer N.
Output:
Print the name of winner i.e 'JACK' or 'JELLY'.
I have written following code for this problem.
Bottom-up approach solution gives me time out.
The top-down approach gives me Segfault. Most probably due to recursion stack.
How can I improve my solution?
Please help me.
Thanks in advance.
Bottom Up (Timeout):
#include <iostream>
using namespace std;
bool arr[2][10000001];
int main() {
int t, n;
cin >> t;
while(t--) {
cin >> n;
arr[0][1]=arr[0][2]=arr[0][4]=0;
arr[1][1]=arr[1][2]=arr[1][4]=1;
arr[0][3]=1;
arr[1][3]=0;
for(int i=5;i<=n;i++) {
for(int player=0;player<2;player++) {
if(arr[1-player][i-1]==player||
arr[1-player][i-2]==player||
arr[1-player][i-4]==player) {
arr[player][i] = player;
} else {
arr[player][i] = 1-player;
}
}
}
if(!arr[0][n]) {
cout << "JELLY" << endl;
} else {
cout << "JACK" << endl;
}
}
return 0;
}
Top-down (Segfault, I think due to recursion):
#include <iostream>
using namespace std;
char arr[2][10000001];
bool solve(int n, bool player) {
if(arr[player][n] != -1)
return arr[player][n];
if(solve(n-1,!player) == player ||
solve(n-2,!player) == player ||
solve(n-4,!player) == player) {
arr[player][n] = player;
} else {
arr[player][n] = !player;
}
return arr[player][n];
}
int main() {
int t, n;
cin >> t;
while(t--) {
cin >> n;
for(int i=0;i<2;i++) {
for(int j=0;j<n+1;j++) {
arr[i][j] = -1;
}
}
arr[0][1]=arr[0][2]=arr[0][4]=0;
arr[1][1]=arr[1][2]=arr[1][4]=1;
arr[0][0]=arr[0][3]=1;
arr[1][0]=arr[1][3]=0;
solve(n, false);
if(!arr[0][n]) {
cout << "JELLY" << endl;
} else {
cout << "JACK" << endl;
}
}
return 0;
}
c++ algorithm programming-challenge time-limit-exceeded
1
Does your code work at all? I mean does it ever return a valid result, e.g. for small samples?
– t3chb0t
Nov 18 at 9:06
1
Yes. I have posted the code which passes the submission criteria.
– user2940110
Nov 18 at 9:38
2
If you add the description of the original task to the question I'll give you two votes ;-)
– t3chb0t
Nov 18 at 9:42
I have included the link in my question where the original task has been described.
– user2940110
Nov 18 at 9:47
3
Please summarise the requirements (in your own words) in the body of the question. Unlike a diamond, a link is not forever - and we want your question to be able to survive the disappearance of the linked resource.
– Toby Speight
Nov 19 at 8:59
add a comment |
up vote
-3
down vote
favorite
up vote
-3
down vote
favorite
I am referring to this problem https://practice.geeksforgeeks.org/problems/cycle-race/0.
The Problem description:
Jack and Jelly are two friends. They want to go to a place by a cycle ( Assume that they live in same house). Distance between the place and their house is 'N' km. Rules of game are as follows:
- Initially Jelly will ride cycle.
- They will ride cycle one by one.
- When one is riding cycle other will sit on the carrier of cycle.
- In each ride they can ride cycle exactly 1, 2 or 4 km. One cannot ride more than remaining distance.
- One who reaches school riding cycle will win.
Both play optimally. You have to find who will win this game.
Input:
First line of input contains an integer 'T' denoting the number of test cases. Then 'T' test cases follow. Each test case consists of a single line containing an integer N.
Output:
Print the name of winner i.e 'JACK' or 'JELLY'.
I have written following code for this problem.
Bottom-up approach solution gives me time out.
The top-down approach gives me Segfault. Most probably due to recursion stack.
How can I improve my solution?
Please help me.
Thanks in advance.
Bottom Up (Timeout):
#include <iostream>
using namespace std;
bool arr[2][10000001];
int main() {
int t, n;
cin >> t;
while(t--) {
cin >> n;
arr[0][1]=arr[0][2]=arr[0][4]=0;
arr[1][1]=arr[1][2]=arr[1][4]=1;
arr[0][3]=1;
arr[1][3]=0;
for(int i=5;i<=n;i++) {
for(int player=0;player<2;player++) {
if(arr[1-player][i-1]==player||
arr[1-player][i-2]==player||
arr[1-player][i-4]==player) {
arr[player][i] = player;
} else {
arr[player][i] = 1-player;
}
}
}
if(!arr[0][n]) {
cout << "JELLY" << endl;
} else {
cout << "JACK" << endl;
}
}
return 0;
}
Top-down (Segfault, I think due to recursion):
#include <iostream>
using namespace std;
char arr[2][10000001];
bool solve(int n, bool player) {
if(arr[player][n] != -1)
return arr[player][n];
if(solve(n-1,!player) == player ||
solve(n-2,!player) == player ||
solve(n-4,!player) == player) {
arr[player][n] = player;
} else {
arr[player][n] = !player;
}
return arr[player][n];
}
int main() {
int t, n;
cin >> t;
while(t--) {
cin >> n;
for(int i=0;i<2;i++) {
for(int j=0;j<n+1;j++) {
arr[i][j] = -1;
}
}
arr[0][1]=arr[0][2]=arr[0][4]=0;
arr[1][1]=arr[1][2]=arr[1][4]=1;
arr[0][0]=arr[0][3]=1;
arr[1][0]=arr[1][3]=0;
solve(n, false);
if(!arr[0][n]) {
cout << "JELLY" << endl;
} else {
cout << "JACK" << endl;
}
}
return 0;
}
c++ algorithm programming-challenge time-limit-exceeded
I am referring to this problem https://practice.geeksforgeeks.org/problems/cycle-race/0.
The Problem description:
Jack and Jelly are two friends. They want to go to a place by a cycle ( Assume that they live in same house). Distance between the place and their house is 'N' km. Rules of game are as follows:
- Initially Jelly will ride cycle.
- They will ride cycle one by one.
- When one is riding cycle other will sit on the carrier of cycle.
- In each ride they can ride cycle exactly 1, 2 or 4 km. One cannot ride more than remaining distance.
- One who reaches school riding cycle will win.
Both play optimally. You have to find who will win this game.
Input:
First line of input contains an integer 'T' denoting the number of test cases. Then 'T' test cases follow. Each test case consists of a single line containing an integer N.
Output:
Print the name of winner i.e 'JACK' or 'JELLY'.
I have written following code for this problem.
Bottom-up approach solution gives me time out.
The top-down approach gives me Segfault. Most probably due to recursion stack.
How can I improve my solution?
Please help me.
Thanks in advance.
Bottom Up (Timeout):
#include <iostream>
using namespace std;
bool arr[2][10000001];
int main() {
int t, n;
cin >> t;
while(t--) {
cin >> n;
arr[0][1]=arr[0][2]=arr[0][4]=0;
arr[1][1]=arr[1][2]=arr[1][4]=1;
arr[0][3]=1;
arr[1][3]=0;
for(int i=5;i<=n;i++) {
for(int player=0;player<2;player++) {
if(arr[1-player][i-1]==player||
arr[1-player][i-2]==player||
arr[1-player][i-4]==player) {
arr[player][i] = player;
} else {
arr[player][i] = 1-player;
}
}
}
if(!arr[0][n]) {
cout << "JELLY" << endl;
} else {
cout << "JACK" << endl;
}
}
return 0;
}
Top-down (Segfault, I think due to recursion):
#include <iostream>
using namespace std;
char arr[2][10000001];
bool solve(int n, bool player) {
if(arr[player][n] != -1)
return arr[player][n];
if(solve(n-1,!player) == player ||
solve(n-2,!player) == player ||
solve(n-4,!player) == player) {
arr[player][n] = player;
} else {
arr[player][n] = !player;
}
return arr[player][n];
}
int main() {
int t, n;
cin >> t;
while(t--) {
cin >> n;
for(int i=0;i<2;i++) {
for(int j=0;j<n+1;j++) {
arr[i][j] = -1;
}
}
arr[0][1]=arr[0][2]=arr[0][4]=0;
arr[1][1]=arr[1][2]=arr[1][4]=1;
arr[0][0]=arr[0][3]=1;
arr[1][0]=arr[1][3]=0;
solve(n, false);
if(!arr[0][n]) {
cout << "JELLY" << endl;
} else {
cout << "JACK" << endl;
}
}
return 0;
}
c++ algorithm programming-challenge time-limit-exceeded
c++ algorithm programming-challenge time-limit-exceeded
edited Nov 19 at 10:02
asked Nov 18 at 5:49
user2940110
61
61
1
Does your code work at all? I mean does it ever return a valid result, e.g. for small samples?
– t3chb0t
Nov 18 at 9:06
1
Yes. I have posted the code which passes the submission criteria.
– user2940110
Nov 18 at 9:38
2
If you add the description of the original task to the question I'll give you two votes ;-)
– t3chb0t
Nov 18 at 9:42
I have included the link in my question where the original task has been described.
– user2940110
Nov 18 at 9:47
3
Please summarise the requirements (in your own words) in the body of the question. Unlike a diamond, a link is not forever - and we want your question to be able to survive the disappearance of the linked resource.
– Toby Speight
Nov 19 at 8:59
add a comment |
1
Does your code work at all? I mean does it ever return a valid result, e.g. for small samples?
– t3chb0t
Nov 18 at 9:06
1
Yes. I have posted the code which passes the submission criteria.
– user2940110
Nov 18 at 9:38
2
If you add the description of the original task to the question I'll give you two votes ;-)
– t3chb0t
Nov 18 at 9:42
I have included the link in my question where the original task has been described.
– user2940110
Nov 18 at 9:47
3
Please summarise the requirements (in your own words) in the body of the question. Unlike a diamond, a link is not forever - and we want your question to be able to survive the disappearance of the linked resource.
– Toby Speight
Nov 19 at 8:59
1
1
Does your code work at all? I mean does it ever return a valid result, e.g. for small samples?
– t3chb0t
Nov 18 at 9:06
Does your code work at all? I mean does it ever return a valid result, e.g. for small samples?
– t3chb0t
Nov 18 at 9:06
1
1
Yes. I have posted the code which passes the submission criteria.
– user2940110
Nov 18 at 9:38
Yes. I have posted the code which passes the submission criteria.
– user2940110
Nov 18 at 9:38
2
2
If you add the description of the original task to the question I'll give you two votes ;-)
– t3chb0t
Nov 18 at 9:42
If you add the description of the original task to the question I'll give you two votes ;-)
– t3chb0t
Nov 18 at 9:42
I have included the link in my question where the original task has been described.
– user2940110
Nov 18 at 9:47
I have included the link in my question where the original task has been described.
– user2940110
Nov 18 at 9:47
3
3
Please summarise the requirements (in your own words) in the body of the question. Unlike a diamond, a link is not forever - and we want your question to be able to survive the disappearance of the linked resource.
– Toby Speight
Nov 19 at 8:59
Please summarise the requirements (in your own words) in the body of the question. Unlike a diamond, a link is not forever - and we want your question to be able to survive the disappearance of the linked resource.
– Toby Speight
Nov 19 at 8:59
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
I have found the answer myself. It is actually testing the game theory. If we see the pattern then only when n is a multiple of 3 then only whoever starts the game first will loose and in all other cases who starts the game will win. The working code is given below.
#include <iostream>
using namespace std;
int main() {
int t, n;
cin >> t;
while(t--) {
cin >> n;
if( n%3 == 0) {
cout << "JACK" << endl;
} else {
cout << "JELLY" << endl;
}
}
return 0;
}
New contributor
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
I have found the answer myself. It is actually testing the game theory. If we see the pattern then only when n is a multiple of 3 then only whoever starts the game first will loose and in all other cases who starts the game will win. The working code is given below.
#include <iostream>
using namespace std;
int main() {
int t, n;
cin >> t;
while(t--) {
cin >> n;
if( n%3 == 0) {
cout << "JACK" << endl;
} else {
cout << "JELLY" << endl;
}
}
return 0;
}
New contributor
add a comment |
up vote
0
down vote
I have found the answer myself. It is actually testing the game theory. If we see the pattern then only when n is a multiple of 3 then only whoever starts the game first will loose and in all other cases who starts the game will win. The working code is given below.
#include <iostream>
using namespace std;
int main() {
int t, n;
cin >> t;
while(t--) {
cin >> n;
if( n%3 == 0) {
cout << "JACK" << endl;
} else {
cout << "JELLY" << endl;
}
}
return 0;
}
New contributor
add a comment |
up vote
0
down vote
up vote
0
down vote
I have found the answer myself. It is actually testing the game theory. If we see the pattern then only when n is a multiple of 3 then only whoever starts the game first will loose and in all other cases who starts the game will win. The working code is given below.
#include <iostream>
using namespace std;
int main() {
int t, n;
cin >> t;
while(t--) {
cin >> n;
if( n%3 == 0) {
cout << "JACK" << endl;
} else {
cout << "JELLY" << endl;
}
}
return 0;
}
New contributor
I have found the answer myself. It is actually testing the game theory. If we see the pattern then only when n is a multiple of 3 then only whoever starts the game first will loose and in all other cases who starts the game will win. The working code is given below.
#include <iostream>
using namespace std;
int main() {
int t, n;
cin >> t;
while(t--) {
cin >> n;
if( n%3 == 0) {
cout << "JACK" << endl;
} else {
cout << "JELLY" << endl;
}
}
return 0;
}
New contributor
New contributor
answered Nov 18 at 9:37
user2940110
61
61
New contributor
New contributor
add a comment |
add a comment |
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f207896%2fhow-to-reduce-run-time-of-my-code-to-solve-cycle-race-practice-problem-from-geek%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
Does your code work at all? I mean does it ever return a valid result, e.g. for small samples?
– t3chb0t
Nov 18 at 9:06
1
Yes. I have posted the code which passes the submission criteria.
– user2940110
Nov 18 at 9:38
2
If you add the description of the original task to the question I'll give you two votes ;-)
– t3chb0t
Nov 18 at 9:42
I have included the link in my question where the original task has been described.
– user2940110
Nov 18 at 9:47
3
Please summarise the requirements (in your own words) in the body of the question. Unlike a diamond, a link is not forever - and we want your question to be able to survive the disappearance of the linked resource.
– Toby Speight
Nov 19 at 8:59