#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    2
    Rep Power
    0

    Adobe codesprint challenge


    I recently attempted GAME problem on Interviewstreet.
    Problem:
    Player A and B , agree to play several games.

    Game rules:-

    1. A game never ends in a draw.

    2. Player "A" starts first in the first game.

    3. Player who starts a game has probability "P" of winning that game.

    4. The one who loses starts the new game.

    Everyone knows no one settles after losing a game. One more game please!!, is the word of mouth whenever someone loses. This way people end up playing many games.

    Now A wants to know the probability that he will win the Nth game.

    Input:
    First line - probability P.
    Second line - Q ( Number of query ).
    Next Q lines, each have an integer N.

    Output:
    For each query output the probability that A will win Nth game.
    Output the answer rounded to 4 decimal places. While rounding to 4 decimal place 0.12345 becomes 0.1235, 0.43531 becomes 0.4353 and 0.32768 becomes 0.3277.

    Constraint :-

    0.0 <= P <= 1.0
    0 < Q <= 200000
    0 < N <= 1000000

    Sample Input:-
    0.2
    3
    1
    4
    7
    Sample Output:-
    0.2000
    0.4352
    0.4860


    My solution is as follows:
    #include <iostream>
    using namespace std;

    double arr[1000000]={0};
    double find(double p,long long int n)
    {
    double ans=0.0;double q=0.0;
    if(n==1)
    {
    arr[1]=p;
    return p;
    }

    if(arr[n-1]!=0)
    {
    return ((1-p)*(arr[n-1])+p*(1-arr[n-1]));
    }
    else
    {
    q=find(p,n-1);
    ans=(1-p)*q+p*(1-q);
    arr[n]=ans;
    return ans;
    }
    }
    int main()
    {
    double p=0;int q=0;long long int n=0;double ans=0.0;long long int i=0;
    scanf("%lf",&p);
    scanf("%d",&q);
    while(q--)
    {
    scanf("%lld",&n);
    ans=find(p,n);

    printf("%.4lf\n",ans);
    }

    return 0;
    }

    It passed 10/11 test-cases and for one test case it gives me Segmentation fault(core dumped). I did a lot of research (googling) but could not understand why this error comes up. My logic is correct I think since it passed 10 test-cases. I would be highly obliged if anyone could tell me why it failed?

    Thanks in advance.
  2. #2
  3. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,379
    Rep Power
    1871
    First, use [code][/code] tags when posting code, so it looks nice and readable.
    Code:
    #include <iostream>
    #include <cstdio>
    using namespace std;
    
    double arr[1000000] = { 0 };
    
    double find(double p, long long int n)
    {
      double ans = 0.0;
      double q = 0.0;
      if (n == 1) {
        arr[1] = p;
        return p;
      }
    
      if (arr[n - 1] != 0) {
        return ((1 - p) * (arr[n - 1]) + p * (1 - arr[n - 1]));
      } else {
        q = find(p, n - 1);
        ans = (1 - p) * q + p * (1 - q);
        arr[n] = ans;
        return ans;
      }
    }
    
    int main()
    {
      double p = 0;
      int q = 0;
      long long int n = 0;
      double ans = 0.0;
      long long int i = 0;
      scanf("%lf", &p);
      scanf("%d", &q);
      while (q--) {
        scanf("%lld", &n);
        ans = find(p, n);
    
        printf("%.4lf\n", ans);
      }
    
      return 0;
    }
    Second, decide which language you're programming in.
    The first couple of lines are C++, but the rest of it is pure C.

    > It passed 10/11 test-cases and for one test case it gives me Segmentation fault(core dumped).
    Well I tried your 3 test cases, got your output, and it didn't crash.
    If you want us to say anything else, you need to tell us what your other test cases are, especially the one which caused a crash.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    2
    Rep Power
    0
    Originally Posted by salem
    First, use [code][/code] tags when posting code, so it looks nice and readable.
    Code:
    #include <iostream>
    #include <cstdio>
    using namespace std;
    
    double arr[1000000] = { 0 };
    
    double find(double p, long long int n)
    {
      double ans = 0.0;
      double q = 0.0;
      if (n == 1) {
        arr[1] = p;
        return p;
      }
    
      if (arr[n - 1] != 0) {
        return ((1 - p) * (arr[n - 1]) + p * (1 - arr[n - 1]));
      } else {
        q = find(p, n - 1);
        ans = (1 - p) * q + p * (1 - q);
        arr[n] = ans;
        return ans;
      }
    }
    
    int main()
    {
      double p = 0;
      int q = 0;
      long long int n = 0;
      double ans = 0.0;
      long long int i = 0;
      scanf("%lf", &p);
      scanf("%d", &q);
      while (q--) {
        scanf("%lld", &n);
        ans = find(p, n);
    
        printf("%.4lf\n", ans);
      }
    
      return 0;
    }
    Second, decide which language you're programming in.
    The first couple of lines are C++, but the rest of it is pure C.

    > It passed 10/11 test-cases and for one test case it gives me Segmentation fault(core dumped).
    Well I tried your 3 test cases, got your output, and it didn't crash.
    If you want us to say anything else, you need to tell us what your other test cases are, especially the one which caused a crash.

    Ok so when I give input as 1000000 for N then it crashes.
  6. #4
  7. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,379
    Rep Power
    1871
    Two things are problematic.

    > q = find(p, n - 1);
    1000000 recursive calls will eat a hell of a lot of stack space.
    With those parameters and local variables, you could be looking at 30+ bytes per stack frame.

    Most machines limit stack space to between 1 and 8MB, so you're comfortably blowing that away.

    > arr[n] = ans;
    On the first iteration, this is an out of bound memory access when n = 1000000
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper

IMN logo majestic logo threadwatch logo seochat tools logo