BanazadehAria's blog

By BanazadehAria, history, 5 years ago, In English

Hi, I just wanted to know what is wrong with my recurrence for this question?

problem link ==> https://mirror.codeforces.com/contest/678/problem/E

my recurrence==>

dp[mask] ==> The probability that the sith number one will win if anyone that is marked in the mask zero is dead and anyone that is alive are marked 1.

so we only go through the mask and if the i-th one is 1 then res+= dp[mask&(1<<j)] and at the end we do res/(Count of the soldiers that are not dead).

I know its completely wrong but I don't know why?

and also please give me a correct recurrence and idea.

Thanks in advance :(

  • Vote: I like it
  • +4
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Guys, please help.

»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

The state must include the currently winning sith.