Page **1** of **2**

### 10207 - The Unreal Tournament

Posted: **Thu Dec 20, 2001 12:19 am**

by **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

Posted: **Thu Dec 20, 2001 12:39 am**

by **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.

Posted: **Thu Jan 10, 2002 10:01 pm**

by **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..

Posted: **Thu Jan 10, 2002 10:09 pm**

by **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!

### Can anyone check these values?

Posted: **Wed Jun 12, 2002 4:59 am**

by **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

### Doh!

Posted: **Wed Jun 12, 2002 8:57 am**

by **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

### 10207 anyone tell me the output ??

Posted: **Mon Oct 06, 2003 7:28 am**

by **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

Posted: **Tue Oct 21, 2003 7:42 am**

by **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.

### Rubish

Posted: **Wed Feb 04, 2004 9:06 pm**

by **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 ?

### 10207-Runtime error(Problem with compiler)

Posted: **Tue Apr 13, 2004 8:35 am**

by **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.

### Re: 10207-Runtime error(Problem with compiler)

Posted: **Tue Apr 13, 2004 9:34 am**

by **CDiMa**

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]

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

Ciao!!!

Claudio

Posted: **Tue Apr 13, 2004 2:15 pm**

by **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.

Posted: **Tue Apr 13, 2004 2:21 pm**

by **CDiMa**

mlvahe wrote: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

### 10207- Invitation to discuss.

Posted: **Tue Apr 13, 2004 5:54 pm**

by **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.

Posted: **Wed Apr 28, 2004 11:41 pm**

by **sERbU**

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