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! If I had better handling
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
thx u
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 ?
10207Runtime 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[i1][j] + (1p)*P[j1];
Q[j][0] = (Q[i1][j][0] + Q[j1][0] + 2) % 10;
carry = (Q[i1][j][0] + Q[i][j1][0] + 2) / 10;
for (k = 1; k < QMAX; k++)
{
Q[i][j][k] = (Q[i1][j][k] + Q[i][j1][k] + carry) % 10;
carry = (Q[i1][j][k] + Q[i][j1][k] + carry) / 10;
}
if (Q[i][j][max(ln[i1][j],ln[i][j1])] == 0)
ln[i][j] = max(ln[i1][j],ln[i][j1]);
else
ln[i][j] = max(ln[i1][j],ln[i][j1]) + 1;
}
for (k = 0; k < N; k++)
{
cin >> i >> j;
if (i + j == 0)
cout << "1\n0\n";
else
{
cout << setiosflags(ios::fixedios::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[i1][j] + (1p)*P[j1];
Q[j][0] = (Q[i1][j][0] + Q[j1][0] + 2) % 10;
carry = (Q[i1][j][0] + Q[i][j1][0] + 2) / 10;
for (k = 1; k < QMAX; k++)
{
Q[i][j][k] = (Q[i1][j][k] + Q[i][j1][k] + carry) % 10;
carry = (Q[i1][j][k] + Q[i][j1][k] + carry) / 10;
}
if (Q[i][j][max(ln[i1][j],ln[i][j1])] == 0)
ln[i][j] = max(ln[i1][j],ln[i][j1]);
else
ln[i][j] = max(ln[i1][j],ln[i][j1]) + 1;
}
for (k = 0; k < N; k++)
{
cin >> i >> j;
if (i + j == 0)
cout << "1\n0\n";
else
{
cout << setiosflags(ios::fixedios::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: 10207Runtime 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,j1) + Numberofcalls(i1,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,j1) + Numberofcalls(i1,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.