# How to reduce run time of my code to solve Cycle race practice problem from geeksforgeeks

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

• Does your code work at all? I mean does it ever return a valid result, e.g. for small samples? – t3chb0t Nov 18 '18 at 9:06
• Yes. I have posted the code which passes the submission criteria. – user2940110 Nov 18 '18 at 9:38
• If you add the description of the original task to the question I'll give you two votes ;-) – t3chb0t Nov 18 '18 at 9:42
• I have included the link in my question where the original task has been described. – user2940110 Nov 18 '18 at 9:47
• 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 '18 at 8:59

## 1 Answer

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