-3
\$\begingroup\$

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

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;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.