[Solved] Need help: Anthony and Cora

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

[Solved] Need help: Anthony and Cora — Kattis

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

I am stuck on this problem

Basically: p1 has N points, p2 has M points. They play N + M - 1 rounds. N, M ≤ 1000. The player who gets zero first loses.

p1 knows the probability of winning each round p_i, the loser gets 1 point subtracted.

I can only think of dp in O((N+M)*N*M), but it gets TLE

my code

        int N, M;
	cin >> N >> M;
	vector<vector<double>> dp(N + 1, vector<double>(M + 1, 0.));
	dp[N][M] = 1.;
	for (int i = 0; i < N + M - 1; ++i) {
		double p;
		cin >> p;

		for (int i = 0; i <= N; ++i) {
			for (int j = 0; j <= M; ++j) {
				if (i > 0 && j > 0) dp[i][j] = 0.;
				if (j > 0 && i + 1 <= N) dp[i][j] += dp[i + 1][j] * (1. - p);
				if (i > 0 && j + 1 <= M) dp[i][j] += dp[i][j + 1] * p;
			}
		}
	}

	double win = 0., lose = 0.;
	for (int i = 1; i <= N; ++i) {
		win += dp[i][0];
	}
	for (int j = 1; j <= M; ++j) {
		lose += dp[0][j];
	}
	cout.precision(17);
	cout << fixed << win / (win + lose) << "\n";

Any help is appreciated :)

kattis, anthony, probability, dp?

yassin_
7 лет назад
2

Комментарии (2)

Написать комментарий?

redocyz

7 лет назад, # |

If I am not mistaken, your O(N*M) dp update is very inefficient? In fact, I believe only O(N+M) element are actually updated? So maybe you can make that more efficient?

→ Ответить