Solving CodeForces Problem E(Div.3)
Rock, Paper, Scissors
Problem Description
There are 2 players Alice and Bob, who are playing Rock, Paper and Scissors game. Alice can pick rock ‘a’ times, scissors ‘b’ times and paper ‘c’ times. Similarly, Bob can pick rock ‘x’ times, scissors ‘y’ times and paper ‘z’ times.
Note: The ordering given in the question is RSP and not RPS
We need to find what is the minimum and maximum number of times that Alice can win.
Solution and Approach
Let’s first find the maximum number of times that Alice can win.
Alice will win only when Bob loses. And Bob can lose in the following cases:
Case 1: When Alice plays rock, Bob plays scissors, i.e., min(a,y)
Case2: When Alice plays paper, Bob plays rock, i.e., min(b,z)
Case3: When Alice plays scissors, Bob plays paper, i.e., min(c,x)
Alice’s winning in each of the above cases is always dependant on the minimum of Alice’s player and Bob’s player.
So, the maximum number of times Alice can win is Case1 + Case2 + Case3
Now, let’s focus on the minimum number of times that Alice is assured to win.
Here, we must not just subtract the total number of plays from the maximum times that Alice can win. We need to encounter the ties as well.
How can we do that?
For minimizing Alice’s win we need to maximize Bob’s win + maximize the ties.
For this, we need to construct a DP.
Let’s see in what cases Alice will not win:
Case 1: When Alice plays Rock, Bob can either play Rock or Paper
if(a!=0 and x!=0) dp(a-min(a,x),b,c,x-min(a,x),y,z);
if(a!=0 and z!=0) dp(a-min(a,z),b,c,x,y,z-min(a,z));
Case 2: When Alice plays Scissors, Bob can either play Scissors or Rock
if(b!=0 and y!=0) dp(a,b-min(b,y),c,x,y-min(b,y),z);
if(b!=0 and x!=0) dp(a,b-min(b,x),c,x-min(b,x),y,z);
Case 3: When Alice plays Paper, Bob can either play Paper or Scissors
if(c!=0 and z!=0) dp(a,b,c-min(c,z),x,y,z-min(c,z));
if(c!=0 and y!=0) dp(a,b,c-min(c,y),x,y-min(c,y),z);
At last, we can see how many chances are remaining, those are the chances that Alice will win.
ans1=min(ans1,a+b+c);
Code
Follow for more such explanations.
Discord link: https://discord.gg/zEHhKWQm for any questions, debugging sessions.
