F — PAS Makeup
Idea: agrim07
Hint
Try to use DP to solve this problem
Tutorial$$$ dp[i][p][q][turn] = p_{\text{even}} \cdot dp[i - 1][p][q][turn \oplus 1] + p_{\text{odd}} \cdot dp[i - 1][p \oplus 1][q][turn \oplus 1] + p_n \cdot dp[i - 1][p \oplus 1][q][turn] $$$ $$$ dp[i][p][q][turn] = p_{\text{even}} \cdot dp[i - 1][p][q][turn \oplus 1] + p_{\text{odd}} \cdot dp[i - 1][p][q \oplus 1][turn \oplus 1] + p_n \cdot dp[i - 1][p][q][turn] $$$ $$$ dp[i][p][q][turn] = p_{\text{even}} \cdot dp[i - 1][p][q][turn \oplus 1] + p_{\text{odd}} \cdot dp[i - 1][p][q \oplus 1][turn \oplus 1] + p_n \cdot dp[i - 1][p \oplus 1][q][turn] $$$ $$$ dp[i][p][q][turn] = p_{\text{even}} \cdot dp[i - 1][p][q][turn \oplus 1] + p_{\text{odd}} \cdot dp[i - 1][p][q \oplus 1][turn \oplus 1] + p_n \cdot dp[i - 1][p][q][turn] $$$
Let $$$dp[i][p][q][turn]$$$ denote the probability of Rajat winning the game, where:
- $$$i$$$ denotes the number of turns left,
- $$$p$$$ denotes the parity of Rajat’s score,
- $$$q$$$ denotes the parity of Dr. S’s score, and
- $$$turn$$$ is 0 if it is Rajat’s turn and 1 if it is Dr. S’s turn.
Let $$$p_{\text{even}}$$$ and $$$p_{\text{odd}}$$$ denote the probabilities of landing even and odd elements, respectively, among the first $$$n - 1$$$ elements of $$$a$$$. We will consider the scenario where $$$a_n$$$ is rolled on the die separately.
The transitions will be as follows:
If it is Rajat’s turn, then there are 2 additional cases:
Case 1: When $$$a_n$$$ is odd
Case 2: When $$$a_n$$$ is even
Similarly, for Dr. S’s turn:
Case 1: When $$$a_n$$$ is odd
Case 2: When $$$a_n$$$ is even
where $$$p_n$$$ is the probability of rolling $$$n$$$.