10207 - The Unreal Tournament
Moderator: Board moderators
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
10207 - The Unreal Tournament
I don't know why I get always WA.
I'm using Java BigInteger and my values for the number of recursive calls seem to be ok. In which cases is the value of P(i,j) undefined? I think, only for i=j=0. And then I print
-1.00000
-1
Is this false?
Adrian K
I'm using Java BigInteger and my values for the number of recursive calls seem to be ok. In which cases is the value of P(i,j) undefined? I think, only for i=j=0. And then I print
-1.00000
-1
Is this false?
Adrian K
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
The maximum number has over 500 digits, so I used Java Big Integer. Therefore it is not possible (or so I think) to precompute all the values and store it, even if one computes only one triangle of the symmetrical Matrix. I have precomputed every hundredth line and then I used DP to compute the actual values.
Of course you can precompute the probability. Good luck!
Of course you can precompute the probability. Good luck!
Can anyone check these values?
I get wrong answer, but I don't see the problem. Can anyone check
these values?
INPUT:
0.5 3
100 100
7 3
3 8
0.7 3
500 500
11 7
2 11
0.5 3
0 1
1 0
0 0
0.7 0
OUTPUT:
0.50000
181097029312206562330808354154968327749009179350826673682638
0.08984
238
0.94531
328
1.00000
540576481890873139031229387251950550992304016893096574014785750213250857411044387797224967849004740330725212170043092209604419500101359835099788439399036950847330968527503466712324928159475774688729148322238995209142089971512575761029201988438853504733831713206273725204968856218593811727599642432638
0.77522
63646
0.99998
154
1.00000 0
0.00000 0
-1.00000 0
-Chris
these values?
INPUT:
0.5 3
100 100
7 3
3 8
0.7 3
500 500
11 7
2 11
0.5 3
0 1
1 0
0 0
0.7 0
OUTPUT:
0.50000
181097029312206562330808354154968327749009179350826673682638
0.08984
238
0.94531
328
1.00000
540576481890873139031229387251950550992304016893096574014785750213250857411044387797224967849004740330725212170043092209604419500101359835099788439399036950847330968527503466712324928159475774688729148322238995209142089971512575761029201988438853504733831713206273725204968856218593811727599642432638
0.77522
63646
0.99998
154
1.00000 0
0.00000 0
-1.00000 0
-Chris
Doh!
Doh! Look at the last few lines (special cases). Everything else
was correct; I was accepted after formatting the special cases
correctly.
I got the 2nd fastest running time, and the lowest memory usage.
I found a nice closed form for the number of recursive calls, which
is why it ran quickly. No DP needed!
If I had better handling
of big integers it would run much faster.
-Chris
was correct; I was accepted after formatting the special cases
correctly.

I got the 2nd fastest running time, and the lowest memory usage.
I found a nice closed form for the number of recursive calls, which
is why it ran quickly. No DP needed!

of big integers it would run much faster.
-Chris
10207 anyone tell me the output ??
0.8 10
1000 1000
800 1000
500 10
800 100
400 400
300 300
200 200
10 3
1001 1001
0 0
1.0 0
thx u
1000 1000
800 1000
500 10
800 100
400 400
300 300
200 200
10 3
1001 1001
0 0
1.0 0

Oh my God ... Wrong Answer
-
- New poster
- Posts: 30
- Joined: Wed Oct 23, 2002 6:53 am
hi to all
to solve this problem, i use an array of Data [1000][1000] of double to
save the result of precalculated P (i, j). and for the number of recursive
call i found that it is equal to 2* C (i+ j, i)- 2 becuase
T( i, j)= T (i- 1, j)+ T (i, j- 1)+ 2.
am i correct about this formula?
any special test case. my program's answer to the testcases which Cubist said is correct.
i use a long integer structure with 1000 digits, is it enough.
please help me.
to solve this problem, i use an array of Data [1000][1000] of double to
save the result of precalculated P (i, j). and for the number of recursive
call i found that it is equal to 2* C (i+ j, i)- 2 becuase
T( i, j)= T (i- 1, j)+ T (i, j- 1)+ 2.
am i correct about this formula?
any special test case. my program's answer to the testcases which Cubist said is correct.
i use a long integer structure with 1000 digits, is it enough.
please help me.
-
- New poster
- Posts: 16
- Joined: Tue Dec 03, 2002 9:44 pm
Rubish
Problem says : 'If the value of P(i,j) is undefined you should print -1 as its value with similar formatting '
My question : When P(i,j) is undefined ?
My question : When P(i,j) is undefined ?
10207-Runtime error(Problem with compiler)
Can anybody tell me why do I get runtime error in 0.000 seconds.
I think there is a problem with compiler, 'cause when I use more than 10MB memory I get runtime error (SIGSEGV)
[cpp]#include <iostream.h>
#include <iomanip.h>
const int NMAX = 1000;
const int QMAX = 58;
int max(int a, int b)
{
if (a> b)
return a;
else
return b;
}
main()
{
float P[NMAX][NMAX], p;
short Q[NMAX][NMAX][QMAX];
short ln[NMAX][NMAX];
int i, N, j, k, k1, carry;
cin >> p >> N;
while (N != 0)
{
for (i = 0; i < NMAX; i++)
{
for (k = 0; k < QMAX; k++)
Q[0][k] = Q[0][k] = 0;
ln[0] = ln[0] = 1;
P[0] = 1;
P[0] = 0;
}
for (i = 1; i < NMAX; i++)
for (j = 1; j < NMAX; j++)
{
P[j] = p*P[i-1][j] + (1-p)*P[j-1];
Q[j][0] = (Q[i-1][j][0] + Q[j-1][0] + 2) % 10;
carry = (Q[i-1][j][0] + Q[i][j-1][0] + 2) / 10;
for (k = 1; k < QMAX; k++)
{
Q[i][j][k] = (Q[i-1][j][k] + Q[i][j-1][k] + carry) % 10;
carry = (Q[i-1][j][k] + Q[i][j-1][k] + carry) / 10;
}
if (Q[i][j][max(ln[i-1][j],ln[i][j-1])] == 0)
ln[i][j] = max(ln[i-1][j],ln[i][j-1]);
else
ln[i][j] = max(ln[i-1][j],ln[i][j-1]) + 1;
}
for (k = 0; k < N; k++)
{
cin >> i >> j;
if (i + j == 0)
cout << "-1\n0\n";
else
{
cout << setiosflags(ios::fixed|ios::showpoint) << setprecision(5) << P[i][j] << "\n";
for (k1 = ln[i][j]-1; k1 >= 0; k1--)
cout << Q[i][j][k1];
cout << "\n";
}
}
cin >> p >> N;
if (N != 0)
cout << "\n";
}
return 0;
}[/cpp]
Thanks in advance.
I think there is a problem with compiler, 'cause when I use more than 10MB memory I get runtime error (SIGSEGV)
[cpp]#include <iostream.h>
#include <iomanip.h>
const int NMAX = 1000;
const int QMAX = 58;
int max(int a, int b)
{
if (a> b)
return a;
else
return b;
}
main()
{
float P[NMAX][NMAX], p;
short Q[NMAX][NMAX][QMAX];
short ln[NMAX][NMAX];
int i, N, j, k, k1, carry;
cin >> p >> N;
while (N != 0)
{
for (i = 0; i < NMAX; i++)
{
for (k = 0; k < QMAX; k++)
Q[0][k] = Q[0][k] = 0;
ln[0] = ln[0] = 1;
P[0] = 1;
P[0] = 0;
}
for (i = 1; i < NMAX; i++)
for (j = 1; j < NMAX; j++)
{
P[j] = p*P[i-1][j] + (1-p)*P[j-1];
Q[j][0] = (Q[i-1][j][0] + Q[j-1][0] + 2) % 10;
carry = (Q[i-1][j][0] + Q[i][j-1][0] + 2) / 10;
for (k = 1; k < QMAX; k++)
{
Q[i][j][k] = (Q[i-1][j][k] + Q[i][j-1][k] + carry) % 10;
carry = (Q[i-1][j][k] + Q[i][j-1][k] + carry) / 10;
}
if (Q[i][j][max(ln[i-1][j],ln[i][j-1])] == 0)
ln[i][j] = max(ln[i-1][j],ln[i][j-1]);
else
ln[i][j] = max(ln[i-1][j],ln[i][j-1]) + 1;
}
for (k = 0; k < N; k++)
{
cin >> i >> j;
if (i + j == 0)
cout << "-1\n0\n";
else
{
cout << setiosflags(ios::fixed|ios::showpoint) << setprecision(5) << P[i][j] << "\n";
for (k1 = ln[i][j]-1; k1 >= 0; k1--)
cout << Q[i][j][k1];
cout << "\n";
}
}
cin >> p >> N;
if (N != 0)
cout << "\n";
}
return 0;
}[/cpp]
Thanks in advance.
Re: 10207-Runtime error(Problem with compiler)
Make your array declarations global (i.e. move them outside main()), you can't put on the stack that much data...mlvahe wrote:Can anybody tell me why do I get runtime error in 0.000 seconds.
I think there is a problem with compiler, 'cause when I use more than 10MB memory I get runtime error (SIGSEGV)
[cpp]const int NMAX = 1000;
const int QMAX = 58;
/* ... */
main()
{
float P[NMAX][NMAX], p;
short Q[NMAX][NMAX][QMAX];
short ln[NMAX][NMAX];
[/cpp]
Ciao!!!
Claudio
10207- Invitation to discuss.
Hello everybody.
I wrote a program for this problem, but it gets MLE.
Lets take a look at the problem.
There we can read
1 <= i,j <= 1000
Trying to solve the problem dynamically me see that
Numberofcalls(i,j) = Numberofcalls(i,j-1) + Numberofcalls(i-1,j)+2
This means that for i == j == 1000 we have Numberofcalls(1000,1000) > 2^1000 > 10^300
So while using dynamic programming to calculate the
Numberofcalls(i,j) we must use Big Numbers.
We must keep an array of 300 elements for each [j].
So we need 1000*1000*300 = 286MB memory which is out of time limit.
Does anybody have any idea what to do?
I hope your replays.
I wrote a program for this problem, but it gets MLE.
Lets take a look at the problem.
There we can read
1 <= i,j <= 1000
Trying to solve the problem dynamically me see that
Numberofcalls(i,j) = Numberofcalls(i,j-1) + Numberofcalls(i-1,j)+2
This means that for i == j == 1000 we have Numberofcalls(1000,1000) > 2^1000 > 10^300
So while using dynamic programming to calculate the
Numberofcalls(i,j) we must use Big Numbers.
We must keep an array of 300 elements for each [j].
So we need 1000*1000*300 = 286MB memory which is out of time limit.
Does anybody have any idea what to do?
I hope your replays.