11061 - Playing War

[arsalan_mousavian]

on each level they roll the dice attakers hava the probabillity of 15/36 to kill one defender ( becauese there is 15 pair of numbers between 1 and 6 that the first one is greater than the second one ) and defender has the probabilty of 21/36 to kill one attacker

Well, but in each attack both of them may use up to 3 armies, therefore on each side up to 3 armies may die in one attack.

ok , but i calculate other probabilties recursively , we have maximum 3 rolling dice on each level that i calculate them recursively

[Towhid]

Well, how the winning of a single combat is determined? I thought, in a 3 against 3 battle the combat is continued until all 3 of any side are died. But in that case there can be more than 3 battles...

[arsalan_mousavian]

on each level they roll the dice attakers hava the probabillity of 15/36 to kill one defender ( becauese there is 15 pair of numbers between 1 and 6 that the first one is greater than the second one ) and defender has the probabilty of 21/36 to kill one attacker

Well, but in each attack both of them may use up to 3 armies, therefore on each side up to 3 armies may die in one attack.

actually there are exactly bno = min (Attack, Defense) (<= 3) battles can happen in 1 attack, and exactly that many armies (in total, counting from both side) will die.

i think it should be min ( defend , attack -1 ) , since the attackers should always keep one soldier in their territory , by the way i got still WA , can someone check my code plz ?

Code: Select all

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std ;
double prob [2000][1001] ;
int result [1001] ;
double f ( int attack , int defend ) 
{
	if ( attack <= 1 || defend <=0 ) return 0 ;
	return prob [attack][defend] ;
}
int main ()
{
	for ( int i=0 ; i<2000 ; i++ )
		prob [i][0] = 1 ;
	for ( int i=0 ; i<=1000 ; i++ )
		prob [1][i] = prob [0][i] = 0 ;

	for ( int attack = 2 ; attack < 2000 ; attack ++ ) 
		for ( int defend = 1 ; defend <= 1000 ; defend ++ ) 
		{
			int size ;
			size = min ( attack  ,  defend ) ;
			if ( size > 3 ) size = 3 ;
			prob[attack][defend] = 0 ;
			for ( int state = 0 ; state<(1<<size) ; state ++ )// generating all the possible result ( one from attack or defend kill ) 
			{
				double temp;
				int countAttack , countDefend ;
				countAttack = countDefend = 0 ;
				temp = 1 ;
				for ( int pos = 0 ; pos < size ; pos ++ ) 
				{
					if ( ( 1<<pos ) & state ) // if in the pos th dice attackers win and kill one defendent
					{
						temp *= ( 15.0/36.0 );
						countDefend ++ ;// the number of killed defenders
					}
					else
					{
						temp*=(21.0/36.0) ;
						countAttack ++ ;// the number of killed attackers
					}
				}
				temp *= prob [attack - countAttack][defend - countDefend ];
				prob [attack][defend] += temp ;
			}
		}
	memset ( result , 0 , sizeof result ) ;
	int X ;
	while ( cin >> X ) 
	{
		if ( !X ) break;
		if ( result [X] == 0 )
		{
			for ( int attack = 2 ; attack < 2000 ; attack ++ ) 
				if ( prob [attack][X] > 0.5 )
				{
					result [X] = attack ;
					break ;
				}
		}
		cout << result [X] << endl;

	}


}

[Martin Macko]

i think it should be min ( defend , attack -1 ) , since the attackers should always keep one soldier in their territory , by the way i got still WA , can someone check my code plz ?

Note, that there may be different numbers of attacker's and defender's armies in one attack. Suppose somewhere before the end of the game the attacker has 4 armies and the defender has just 1 army. In that case there are 3 attacking armies and 1 defending army in the next attack. However, in the following part of your ode you assume that in each attack both the defender and the attacker have the same number of armies (namely size):

.........int size ;
.........size = min ( attack..,..defend ) ;
.........if ( size > 3 ) size = 3 ;
.........prob[attack][defend] = 0 ;
.........for ( int state = 0 ; state<(1<<size) ; state ++ )// generating all the possible result ( one from attack or defend kill )
.........{
...............
.........}

Read the third paragraph of the problem statement more carrefully.

[Mg9H]

Well, but in each attack both of them may use up to 3 armies, therefore on each side up to 3 armies may die in one attack.

actually there are exactly bno = min (Attack, Defense) (<= 3) battles can happen in 1 attack, and exactly that many armies (in total, counting from both side) will die.

i think it should be min ( defend , attack -1 ) , since the attackers should always keep one soldier in their territory , by the way i got still WA , can someone check my code plz ?

When I wrote that I meant Attack & Deffense are the number of armies of attacker & defender (respectively) participated in the attack.

[arsalan_mousavian]

i think it should be min ( defend , attack -1 ) , since the attackers should always keep one soldier in their territory , by the way i got still WA , can someone check my code plz ?

Note, that there may be different numbers of attacker's and defender's armies in one attack. Suppose somewhere before the end of the game the attacker has 4 armies and the defender has just 1 army. In that case there are 3 attacking armies and 1 defending army in the next attack. However, in the following part of your ode you assume that in each attack both the defender and the attacker have the same number of armies (namely size):

.........int size ;
.........size = min ( attack..,..defend ) ;
.........if ( size > 3 ) size = 3 ;
.........prob[attack][defend] = 0 ;
.........for ( int state = 0 ; state<(1<<size) ; state ++ )// generating all the possible result ( one from attack or defend kill )
.........{
...............
.........}

Read the third paragraph of the problem statement more carrefully.

maybe i misunderstood the problem statement , assume that attackers have the dices of 5,4,3 and defender has the dice of 6 , then how many attackers will kill ? i think one of attackers will be killed and that's why i am using variable size, because i think when one side has attackers and the other side has 1 defender they only compare the maximum dice of each side ( in this example 6,5),am i right or i misunderstood the problem ? then if i am wrong how many attackers will be killed . . . ?

[mf]

when one side has attackers and the other side has 1 defender they only compare the maximum dice of each side

When the attacker has more units than defender, his 'maximum dice' is more likely to be higher.

For example, if the attacker uses 3 units, and defender 1 unit, the probability that attack succeeds is 0.65972, but for your program it's just 15/36 (as in 1 vs. 1 case.)

[joeluchoa]

I've used DP in my solution for this problem!
However, i got WA for a precision error.
How to I solve this error?

[Martin Macko]

I've used DP in my solution for this problem!
However, i got WA for a precision error.
How to I solve this error?

How do you know you got WA for a precision error? I don't think there should be any problems with precision errors in this problem. Just remember to use doubles instead of floats and to compare them using some small epsilon tolerance (eg. 1e-9).

[joeluchoa]

I think that is precision error. For example, if I have 2 armies and my enemy have 1000, the prabability of me win is too low.

[Martin Macko]

I think that is precision error. For example, if I have 2 armies and my enemy have 1000, the prabability of me win is too low.

Yes you're right. But note that

min{abs(P[d][a]-0.5) | 1 <= d <= 1000, 1 <= a <= 2000} > 4.49 * 10^-6,

where P[d][a] is the probability that Elbdson wins assuming he has a armies and his opponent has d armies. As 4.49 * 10^-6 is big enough to be stored in double you shouldn't get any significiatn precision error near the probability of 0.5.

[joeluchoa]

In my solution, the output for input 100 is 172!!
In a previous posts I see that the correct output is 171!!

I've got probability[100][171] = 0.499692911297
and probability[100][172] = 0.512962827527

( probability[D][A] is the probability of win with A armies attack and D armies defence)

Do somebody have a hint for my problem?

[joeluchoa]

Here is my code:

Code: Select all

I've got AC now!

[Martin Macko]

I've got probability[100][171] = 0.499692911297
and probability[100][172] = 0.512962827527

( probability[D][A] is the probability of win with A armies attack and D armies defence)

Neither one is correct.

[Martin Macko]

Here is my code:

Recheck the following lines of your code:

.......
....probability[2][3] = prob_combat[1][1][2]
........................+ prob_combat[1][1][1] * probability[1][2];
.......

and

.......
....for ( i = 3; i < MAX_DEFENCE; i++ ){.
...........
........probability[i][2] = prob_combat[1][1][1] * probability[i-1][2];.
...........
....}
.......