javacoder1's blog

By javacoder1, history, 2 years ago, In English,
I was looking through this accepted code and seems that the states of dp are dp[i][j] meaning that the submask i is considered and j is the winner.I am confused about two things.
1. dp[i][j] shouldn't be max(dp[i][j],p[j][k]*dp[i^(1<<k)][j] + p[j][k]*dp[i^(1<<j)][k])
 meaning j is the winner of the mask so j was winner of mask excluding k and defeated k. and k was the winner of mask excluding j and j defeated k.
2. we want 0 to be winner so why we are iterating to get final answer.shouldn't it be dp[(1<<N)][0] 
#include <iostream>
#include <iomanip>
using namespace std;

double p[18][18];
double dp[1<<18][18];

int main()
{
	int N;
	cin >> N;
	for(int i=0;i<N;i++) for(int j=0;j<N;j++) cin >> p[i][j];
	for(int i=0;i<N;i++) dp[1][i] = 0.0;
	dp[1][0] = 1.0;
	for(int i=2;i<(1<<N);i++) for(int j=0;j<N;j++) if(i&(1<<j))
	{
		dp[i][j] = 0.0;
		for(int k=0;k<N;k++) if((i&(1<<k))&&(k!=j))
		{
			dp[i][j] = max(dp[i][j],p[j][k]*dp[i^(1<<k)][j] + p[k][j]*dp[i^(1<<j)][k]);
		}
	}
	double best = 0;
	for(int i=0;i<N;i++) best = max(best,dp[(1<<N)-1][i]);
	cout  << setprecision(20) << best << '\n';
}

THe editorial as well as all solution seems to do the same thing.Can someone explain?

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

»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Can someone please clear the above doubts...

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Actually dp[i][j] means the maximal probability of Jedi being alive where the ones in the binary representation of i represents who is alive and j is considered the master who is currently fighting. The base case dp[1][0] = 1.0 means the maximal probability of Ivan being alive when he is the only one alive and the current master. For the recurrence relation, we're making Sith alive, so there are two cases for the current master: 1- he kills Sith k who was alive 2- another Sith k took the place of the master j It's obvious that we're maximizing over the probability that makes Jedi alive, the initial call's mask must be contain n ones, as all the sith are alive and we try all the different masters and get the maximum probability returned by one of these masters.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am so glad you responded! After 2 years I started to worry that no one would respond to this blog...