ROPASCI - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Nishant Shah
Tester: Lavish Gupta
Editorialist: Taranpreet Singh

DIFFICULTY

Easy

PREREQUISITES

None

PROBLEM

There are N players standing in a line, indexed 1 to N from left to right. They all play a game of Rock, Paper, Scissors. Each player has already decided which move they want to play. You are given this information as a string S of length N, i.e,

  • S_i is equal to \verb+R+ if player i will play Rock.
  • S_i is equal to \verb+P+ if player i will play Paper.
  • S_i is equal to \verb+S+ if player i will play Scissors.

Let W(i, j) denote the move played by the winner if players i, i+1, \ldots, j compete in order from left to right. That is,

  • First, players i and i+1 play a game
  • The winner of this game plays against player i+2
  • The winner of the second game plays against player i+3

\vdots

  • The winner of the first j-i-1 games plays against player j, and the move played by the winner of this game is declared to be W(i, j).

If i = j, then player i is considered to be the winner and W(i, i) = S_i.

Your task is to find the value of W(i,N) for all i from 1 to N.

QUICK EXPLANATION

  • Considering position p, if q is the first position where p-th person loses, then W(p, N) = W(q, N).
  • If no such q exists, person at position p wins all games, hence W(p, N) = A_p in that case.

EXPLANATION

The brute force solution for this problem would be to consider each start point and simulate all games one by one. There are a total of N games, and each game may require N steps, so a total O(N^2) time is required to simulate this, which is not fast enough.

Let’s just consider computing W(p, N) for some p. Two cases are possible for a person at position p.

  • Person at position p wins all games. In this case, W(p, N) = A_p, since p-th person win the last game.
  • Person at position p loses to the person at position q.

In the second case, now q-th person starts playing subsequent games. Once q-th person starts playing, it does not matter whether we were computing W(q, N) or W(p, N). The answer only depends on subsequent games. We can prove that if q-th person is the first person to which p-th person loses, then W(q, N) = W(p, N) holds.

Hence, in order to compute W(p, N) quickly, we need W(q, N) computed for q \gt p. We can ensure this by solving the problem in the decreasing order of p.

We also need to compute quickly for each position, the smallest position q where the person at position p loses. It roughly translates to finding the first position of some character after position p.

Since there are only three distinct characters in the string, we can keep an ordered set of positions of each character. Alternatively, since we are iterating from right to left, we can maintain three variables, the last seen position of each charcacter. As soon as we process position p, we update the value of variable representing character A_p with p.

TIME COMPLEXITY

The time complexity is O(N) per test case.

SOLUTIONS

Tester's Solution
#include <bits/stdc++.h>
using namespace std;
 
 
/*
------------------------Input Checker----------------------------------
*/
 
long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);
 
            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            if(is_neg){
                x= -x;
            }
 
            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }
 
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        assert(g!=-1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}
 
 
/*
------------------------Main code starts here----------------------------------
*/
 
const int MAX_T = 100000;
const int MAX_N = 500000;
const int MAX_SUM_LEN = 500000;
 
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ff first
#define ss second
#define mp make_pair
#define ll long long
 
int sum_len = 0;
int max_n = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;

int get_res(int a , int b)
{
    if(a == b)
        return a ;
    if(a > b)
        return get_res(b , a) ;
    if(a == 0 && b == 1)
        return 1 ;
    if(a == 1 && b == 2)
        return 2 ;
    return 0 ;
}
    
void solve()
{   
    string str ;
    int n = readIntLn(1 , MAX_N) ;
    str = readStringLn(n , n);
    
    sum_len += n;
    max_n = max(max_n , n) ;

    int dp[n][3] ;
    int arr[n] ;
    string s = "RPS" ;

    for(int i = 0 ; i < n ; i++)
    {
        for(int j = 0 ; j < 3 ; j++)
            if(str[i] == s[j])
                arr[i] = j ;
    }

    for(int i = n-1 ; i >= 0 ; i--)
    {
        for(int j = 0 ; j < 3 ; j++)
        {
            if(i == n-1)
                dp[i][j] = get_res(j , arr[i]) ;
            else
                dp[i][j] = dp[i+1][get_res(j , arr[i])] ;
        }
    }
    string ans;
    for(int i = 0 ; i < n ; i++)
    {
        if(i == n-1)
            ans += s[arr[i]] ;
        else
            ans += s[dp[i+1][arr[i]]] ;
    }
    cout << ans << endl ;
    return ;

}
 
signed main()
{

    #ifndef ONLINE_JUDGE
    freopen("inputf.txt", "r" , stdin);
    freopen("outputf.txt", "w" , stdout);
    #endif
    fast;
    
    int t = 1;
    t = readIntLn(1,MAX_T);
    
    for(int i=1;i<=t;i++)
    {    
       solve();
    }
    
    assert(sum_len <= MAX_SUM_LEN) ;
    assert(getchar() == -1);

 
    cerr<<"SUCCESS\n";
    cerr<<"Tests : " << t << '\n';
    cerr<<"Sum of lengths : " << sum_len << '\n';
    cerr<<"Maximum length : " << max_n << '\n';
    // cerr<<"Total operations : " << total_ops << '\n';
    //cerr<<"Answered yes : " << yess << '\n';
    //cerr<<"Answered no : " << nos << '\n';
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class ROPASCI{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int N = ni(), A = 26;
        char[] S = n().toCharArray();
        int[] nxt = new int[A];
        Arrays.fill(nxt, N);
        char[] ans = new char[N];
        for(int i = N-1; i>= 0; i--){
            char win = win(S[i]);
            if(nxt[win-'A'] == N)ans[i] = S[i];
            else ans[i] = ans[nxt[win-'A']];
            nxt[S[i]-'A'] = i;
        }
        pn(new String(ans));
    }
    //who wins against ch
    char win(char ch){
        switch(ch){
            case 'R': return 'P';
            case 'P': return 'S';
            case 'S': return 'R';
            default: return ' ';
        }
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    static boolean multipleTC = true;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        new ROPASCI().run();
    }
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

3 Likes

can someone provide me a better solution, the editorialist’s solution seems a bit confusing

3 Likes

Can someone please help me optimise my solution I have used a dp kind of approach but it is turning out to be O(N^2)!!

2 Likes

Here my solution using divide and conquer.

Instead of a nĂ—n dp solution try to think for a 3Ă—n dp solution
At any index we can come with 3 possible pre winners R ,P or S
You can check my Sol for ref.

https://www.codechef.com/viewsolution/54844951

doesn’t seem to be O(n) cuz its showing TLE in some of the testcases

1 Like

thanx bro, very nicely explained

I liked this problem a lot because of this solution, and it can be easily applied to solve range queries if the problem had asked for that.

1 Like

My approach was to work from right to left.

Suppose that at an arbitrary position j we have an array of length 3 of who would be the winner if each kind of play was made. The value of W there is the winner when the actual play there is made.

To evaluate the corresponding array at position j - 1, evaluate k = the result of each kind of play on the item at position j. Then set this element of the array at j - 1 to element k of the array for position j.

This method is best illustrated by an example, say the second example in the problem statement SSPR.

At the last position, the result of playing each of [RPS] against nothing is [RPS]. The value of W there is the R played there.

At the previous position 3, the result of playing each of [RPS] against the R at position 4 is [RPR]. So the array at position 3 is [RPR]. As P is played the value of W there is P.

At the previous position 2, the result of playing each of [RPS] against the P at position 3 is [PPS]. So the array at position 2 is [PPR]. As S is played the value of W there is R.

At the first position 1, the result of playing each of [RPS] against the S at position 2 is [RSS]. So the array at position 1 is [PRR]. As S is played the value of W there is R.

2 Likes

my soln in c++ using maps

https://www.codechef.com/viewsolution/54825011
I have used 3*n dp Solution but I don’t know why my solution is giving wrong answer on first two Cases. Can anyone help me, where I am going wrong?

My Solution Click here