Hello, I am trying to solve a problem about probability, but I keep getting WA. The problem is from the brazilian contest **IV Maratona Mineira**. I can only find the problem in portuguese, so I will try to translate. I explained my idea and posted my code. My english is not that good, so any doubts, just ask me.↵
↵
### Problem:↵
Player A and B are playing a game of War(based on the board game Risk). A has **NA** armies in his territory and is in a war against a neighbor territory that B is defending with **NB** armies. The war between two territories is made up of several battles.↵
↵
The rules of a battle are:↵
↵
- The attacker can attack a territory with the maximum of 3 armies.↵
- The attacker must leave at least 1 army in his territory. Basically, the attacker can attack with max( **NA** -1,3) armies.↵
- The defender can protect his territory with the maximum of 3 armies.↵
- The defender can use all of his armies to protect his territory. The defender can defend with max( **NB** ,3) armies.↵
↵
After each player has chosen a valid amount of armies to use in the battle (player A with **XA** armies and player B with **XB** armies), **XA** dices representing the attacker are thrown and **XB** dices representing the defender are thrown. The dices are numbered from 1 to 6. Then, the dices thrown by player A are sorted, as well as B's dices. After that, the min( **XA** , **XB** ) highest values obtained by each player are compared pairwise. For each comparison where the number obtained by attacker is higher than the number obtained by the defender, the defender loses an army. Otherwise, the attacker will lose an army.↵
↵
For example: player A is battling with 3 armies against 2 armies of B. Player A gets numbers {1,4,3}, player B gets numbers {2,3}. In this case, Player B loses his 2 armies (because 4 > 3 and 3 > 2).↵
↵
Given the two numbers **NA** and **NB**, Player A wants to know the probability that he wins the war against player B, if both players play optimally.↵
↵
Remember that a war is a sequence of battles. Player A loses the war if only one of his armies remains. Player A wins the war if there is no armies of player B left.↵
↵
**Input**: The input has two numbers **NA** **NB**, where 1 <= **NA**, **NB** <= 10000.↵
↵
**Output**: Probability that player A wins the war.↵
↵
**Sample test case** (which my code is already failing): ↵
Input: 5 4 ↵
Output: 0.2554↵
↵
**Time limit**: 1.5s ↵
**Memory limit**: 256MB↵
↵
### My solution:↵
↵
code: http://pastebin.com/MdpHGjZT↵
↵
code with memory optimization: http://pastebin.com/0A9NJf99↵
↵
I created a vector called prob, where prob[x][y][z] is the probability that X armies attacking against Y armies will beat Z armies. (Ex: prob[3][2][1] is the probability that 3 armies are going against 2 armies and beat 1 of them). I'm pretty sure those probabilities are correct, since I checked them at least 5 times each.↵
↵
The rest is just dynamic programming, where I test all possibilities. The base cases are:↵
↵
- a == 1 : return 0 (because the war is lost);↵
- b == 0 : return 1 (because the war is won);↵
↵
Can someone give some ideas on how to solve this problem? Thanks :D
↵
### Problem:↵
Player A and B are playing a game of War(based on the board game Risk). A has **NA** armies in his territory and is in a war against a neighbor territory that B is defending with **NB** armies. The war between two territories is made up of several battles.↵
↵
The rules of a battle are:↵
↵
- The attacker can attack a territory with the maximum of 3 armies.↵
- The attacker must leave at least 1 army in his territory. Basically, the attacker can attack with max( **NA** -1,3) armies.↵
- The defender can protect his territory with the maximum of 3 armies.↵
- The defender can use all of his armies to protect his territory. The defender can defend with max( **NB** ,3) armies.↵
↵
After each player has chosen a valid amount of armies to use in the battle (player A with **XA** armies and player B with **XB** armies), **XA** dices representing the attacker are thrown and **XB** dices representing the defender are thrown. The dices are numbered from 1 to 6. Then, the dices thrown by player A are sorted, as well as B's dices. After that, the min( **XA** , **XB** ) highest values obtained by each player are compared pairwise. For each comparison where the number obtained by attacker is higher than the number obtained by the defender, the defender loses an army. Otherwise, the attacker will lose an army.↵
↵
For example: player A is battling with 3 armies against 2 armies of B. Player A gets numbers {1,4,3}, player B gets numbers {2,3}. In this case, Player B loses his 2 armies (because 4 > 3 and 3 > 2).↵
↵
Given the two numbers **NA** and **NB**, Player A wants to know the probability that he wins the war against player B, if both players play optimally.↵
↵
Remember that a war is a sequence of battles. Player A loses the war if only one of his armies remains. Player A wins the war if there is no armies of player B left.↵
↵
**Input**: The input has two numbers **NA** **NB**, where 1 <= **NA**, **NB** <= 10000.↵
↵
**Output**: Probability that player A wins the war.↵
↵
**Sample test case** (which my code is already failing): ↵
Input: 5 4 ↵
Output: 0.2554↵
↵
**Time limit**: 1.5s ↵
**Memory limit**: 256MB↵
↵
### My solution:↵
↵
code: http://pastebin.com/MdpHGjZT↵
↵
code with memory optimization: http://pastebin.com/0A9NJf99↵
↵
I created a vector called prob, where prob[x][y][z] is the probability that X armies attacking against Y armies will beat Z armies. (Ex: prob[3][2][1] is the probability that 3 armies are going against 2 armies and beat 1 of them). I'm pretty sure those probabilities are correct, since I checked them at least 5 times each.↵
↵
The rest is just dynamic programming, where I test all possibilities. The base cases are:↵
↵
- a == 1 : return 0 (because the war is lost);↵
- b == 0 : return 1 (because the war is won);↵
↵
Can someone give some ideas on how to solve this problem? Thanks :D
