Блог пользователя pedrohlf

Автор pedrohlf, история, 8 лет назад, По-английски

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 min( 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 min( 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,2}, player B gets numbers {2,3}. In this case, player A loses one army and player B loses one army (because 4 > 3 and 2 <= 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

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by pedrohlf (previous revision, new revision, compare).

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Seeing as no one solved this problem, are you sure that the test data is correct?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Hm, I'm not sure if tests are correct. I think this may be the case here. I just have never seen something like this happening.

»
8 лет назад, # |
Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

Have you calculated all values by hand? Sounds like a very bad idea. Isn't it better to write a program for that?

I implemented a monte carlo approach and for the sample test I get about 0.31. Your program finds the same answer, so likely your implementation is correct. Possible explanations, from the most to the least likely one:

  1. You didn't translate the statement correctly. Maybe you don't understand the original statement.
  2. It isn't optimal to always send as many armies as possible. In other words, maybe it's possible that A will send less than min(na - 1, 3) or that B will send less than min(nb, 3).
  3. Organizers made a mistake.
my Monte Carlo code