November 21st, 2012, 11:58 AM

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[n1]!=0)
{
return ((1p)*(arr[n1])+p*(1arr[n1]));
}
else
{
q=find(p,n1);
ans=(1p)*q+p*(1q);
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 testcases 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 testcases. I would be highly obliged if anyone could tell me why it failed?
Thanks in advance.
November 21st, 2012, 01:33 PM

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 testcases 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.
November 21st, 2012, 01:54 PM

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 testcases 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.
November 21st, 2012, 02:48 PM

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