Forums: » Register « |  Free Tools |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

New Free Tools on Dev Shed!

#1
November 21st, 2012, 12:58 PM
 mancoolgunda
Registered User

Join Date: Nov 2012
Posts: 2
Time spent in forums: 8 m 49 sec
Reputation Power: 0

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?

#2
November 21st, 2012, 02:33 PM
 salem
Contributed User

Join Date: Jun 2005
Posts: 4,247
Time spent in forums: 2 Months 4 Weeks 1 Day 11 h 34 m 37 sec
Reputation Power: 1809
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

#3
November 21st, 2012, 02:54 PM
 mancoolgunda
Registered User

Join Date: Nov 2012
Posts: 2
Time spent in forums: 8 m 49 sec
Reputation Power: 0
Quote:
 Originally Posted by salem First, use [code][/code] tags when posting code, so it looks nice and readable. Code: ```#include #include 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.

#4
November 21st, 2012, 03:48 PM
 salem
Contributed User

Join Date: Jun 2005
Posts: 4,247
Time spent in forums: 2 Months 4 Weeks 1 Day 11 h 34 m 37 sec
Reputation Power: 1809
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

 Viewing: Dev Shed Forums > Programming Languages > C Programming > Adobe codesprint challenge