10207 - The Unreal Tournament

[Adrian Kuegel]

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

[Adrian Kuegel]

I have now found out, that I had to print
-1.00000
0
in the case, that the value of P(i,j) is undefined. After this modification I got Accepted.

[Even]

I have no ideal about how to DP it...

I use long array to record and it seems not work...

can you give me any hint... thx..

[Adrian Kuegel]

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!

[Cubist]

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

[Cubist]

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

[coolbila]

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

[Amir Aavani]

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.

[Shahriar Nirjon]

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 ?

[mlvahe]

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.

[CDiMa]

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]

Make your array declarations global (i.e. move them outside main()), you can't put on the stack that much data...

Ciao!!!

Claudio

[mlvahe]

Thank you very much for your advice.
It's really useful.
But no I get MLE.
Can anybody tell me the standart Memory limit.

[CDiMa]

Thank you very much for your advice.
It's really useful.
But no I get MLE.
Can anybody tell me the standart Memory limit.

It should be 32 Mb.

Ciao!!!

Claudio

[mlvahe]

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.

[sERbU]

I'm not sure but I think that P(i,j) = (0,0) is the only undefined.