MINRPC - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: notsoloud
Tester: yash_daga
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

Chef and Chefina play N rounds of standard rock-paper-scissors.
Given Chefina’s moves on all the rounds, find the lexicographically smallest sequence of moves for Chef that allows him to win more than half the games.

EXPLANATION:

The three characters we have to work with are \texttt{P, R, S}.
Among them, \texttt{P} is the smallest, so our aim should be to use it as much as possible.
This can be done greedily.

Let X = \left\lfloor \frac{N}{2} \right\rfloor + 1 be the minimum required number of wins for Chef.
For each i from 1 to N:

  • If Chef can play a \texttt{P} at this position, he should.
    For this, Chef should be able to win the required number of rounds from the remaining ones.
    There are two cases:
    • First, if A_i = \texttt{R}, then playing \texttt{P} is optimal, since it’s smallest and it wins the round.
      So, play it and reduce X by 1 (Chef needs one less win from the remaining rounds).
    • Otherwise, \texttt{P} here doesn’t lead to a win. Then, Chef can play \texttt{P} here if and only if X \leq N-i: that is, if winning all the rounds after it is enough.
      If this condition is true, play \texttt{P}, but don’t reduce X (since Chef doesn’t win this round).
  • If Chef isn’t able to play \texttt{P} at the current position, that means he’s forced to win all his remaining games.
    This means all of his remaining moves are uniquely determined - play the only winning move for each of them.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (Python) 
win = {'R':'P', 'P':'S', 'S':'R'}
for _ in range(int(input())):
    n = int(input())
    s = input()
    req = n//2 + 1
    ans = []
    for i in range(n):
        if req == n-i:
            ans.append(win[s[i]])
            req -= 1
        else:
            ans.append('P')
            req -= s[i] == 'R'
    print(''.join(ans))
2

I did the same thing as the editorial and yet I keep getting a wrong answer.
I calculate how many free wins I get, which are in the (first half-1) and keep all moves here as ‘P’.
Even if we get no ‘R’ as Chefina’s moves in the first half we can get them all in the second half. That should give us the lexgraphically smallest string.

#include <bits/stdc++.h>
using namespace std;

/* clang-format off */

/* TYPES  */
#define ll long long

int main() {
	ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t --> 0) {
    	ll n;
    	cin >> n;
    	ll toWin = (n/2) + 1;
    	string inp;
    	cin >> inp;
        if (n == 1) {
            if (inp[0] == 'S') {
				cout << "R" << endl;
				} else if (inp[0] == 'P') {
					cout << "S" << endl;
					
				} else if (inp[0] == 'R') {
					cout << "P" << endl;
				}
				continue;
        }
    	int half = n/2;
    	if (n % 2 == 0) {
    	    --half;
    	}
    	for (int i = 0; i < half; i++) {
// free win
    		if (inp[i] == 'R') {
    			--toWin;
			}
		}

		vector<char> ans(n, 'P');
		if (toWin > 0) {
			for (int i = n-1; i >= half && toWin > 0; i--) {
				if (inp[i] == 'S' && toWin > 0) {
					ans[i] = 'R';
					toWin--;
				} else if (inp[i] == 'P' && toWin > 0) {
					ans[i] = 'S';
					toWin--;
				} else if (inp[i] == 'R' && toWin > 0) {
					ans[i] = 'P';
					toWin--;
				}
			}	
		}
		for (int i = 0; i < n; i++) {
			cout << ans[i];
		} 
		cout << endl;
    }
}
3

Wouldn’t starting from the end give us the lexographically smallest answer?
i.e. inp = “SRSPPPP”
ANS = “PPPSSSS”
because my code does exactly that and still fails

4 
1
3
RRP

The answer is PPP.

1 Like
5

Thank you for helping me out!
Cheers!

6

include <bits/stdc++.h>
using namespace std;

int main() {
// your code goes here
int t;
cin>>t;
unordered_map<char,string>mp;
mp[‘P’]=“S”;
mp[‘R’] = “P”;
mp[‘S’] = “R”;
while(t–){
int n;
cin>>n;
string s;
cin>>s;
string ans =“”;
for(int i=0; i<n; i++){
ans += mp[s[i]];
}
int left = n/2;
if(n%2 == 0)left-=1;
for(int i=0; i<n && left > 0;i++){
if(ans[i] == ‘P’)continue;
else{
ans[i] = ‘P’;
left-=1;
}
}
cout<<ans<<endl;

}

}
can this be the right way also
replace as my letters with P as u can in the winning answers