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









share|improve this question




















  • 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















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









share|improve this question




















  • 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













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









share|improve this question















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






share|improve this question















share|improve this question













share|improve this question




share|improve this question








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














  • 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










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





share|improve this answer








New contributor




user2940110 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.


















    Your Answer





    StackExchange.ifUsing("editor", function () {
    return StackExchange.using("mathjaxEditing", function () {
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
    });
    });
    }, "mathjax-editing");

    StackExchange.ifUsing("editor", function () {
    StackExchange.using("externalEditor", function () {
    StackExchange.using("snippets", function () {
    StackExchange.snippets.init();
    });
    });
    }, "code-snippets");

    StackExchange.ready(function() {
    var channelOptions = {
    tags: "".split(" "),
    id: "196"
    };
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function() {
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled) {
    StackExchange.using("snippets", function() {
    createEditor();
    });
    }
    else {
    createEditor();
    }
    });

    function createEditor() {
    StackExchange.prepareEditor({
    heartbeatType: 'answer',
    convertImagesToLinks: false,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: null,
    bindNavPrevention: true,
    postfix: "",
    imageUploader: {
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    },
    onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    });


    }
    });














     

    draft saved


    draft discarded


















    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

























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





    share|improve this answer








    New contributor




    user2940110 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.






















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





      share|improve this answer








      New contributor




      user2940110 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.




















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





        share|improve this answer








        New contributor




        user2940110 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
        Check out our Code of Conduct.









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






        share|improve this answer








        New contributor




        user2940110 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
        Check out our Code of Conduct.









        share|improve this answer



        share|improve this answer






        New contributor




        user2940110 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
        Check out our Code of Conduct.









        answered Nov 18 at 9:37









        user2940110

        61




        61




        New contributor




        user2940110 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
        Check out our Code of Conduct.





        New contributor





        user2940110 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
        Check out our Code of Conduct.






        user2940110 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
        Check out our Code of Conduct.






























             

            draft saved


            draft discarded



















































             


            draft saved


            draft discarded














            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





















































            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







            Popular posts from this blog

            Сан-Квентин

            Алькесар

            Josef Freinademetz