Rock Paper Scissors ROPASCI Solution Codechef

Rock Paper Scissors ROPASCI Solution

There are NN players standing in a line, indexed 11 to NN 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 SS of length NN, i.e,

  • SiSi is equal to RR if player ii will play Rock.
  • SiSi is equal to PP if player ii will play Paper.
  • SiSi is equal to SS if player ii will play Scissors.

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

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

⋮⋮

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

If i=ji=j, then player ii is considered to be the winner and W(i,i)=SiW(i,i)=Si.

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

Note : If a person with index ii and index jj (i<ji<j) play against each other, then:

  • If Si≠SjSi≠Sj, the winner is decided by classical rules, i.e, rock beats scissors, scissors beats paper, and paper beats rock.
  • If Si=SjSi=Sj, the player with lower index (in this case, ii) wins.

Input Format

  • The first line of input contains a single integer TT, denoting the number of test cases. The description of TT test cases follows.
  • The first line of each test case contains a single integer NN, the number of players.
  • The second line of each test case contains the string SS of length NN, denoting the moves chosen by the players.

Output Format

For each test case, print a single line containing a string of length NN, whose ii-th character is W(i,N)W(i,N).

Constraints

  • 1≤T≤1051≤T≤105
  • 1≤N≤5⋅1051≤N≤5⋅105
  • SiSi is either RR, PP or SS
  • Sum of NN over all test cases doesn’t exceed 5⋅1055⋅105

Subtasks

Subtask 1 (10 points):

  • 1≤T≤10001≤T≤1000
  • 1≤N≤50001≤N≤5000
  • Sum of NN over all test cases doesn’t exceed 50005000

Subtask 1 (90 points):

  • Original constraints

Sample Input 1 

2
1
S
4
SSPR

Sample Output 1 

S
RRPR

Explanation

Test Case 1. W(1,1)=SW(1,1)=S as there is only one player.

Test Case 2.

For W(1,4)W(1,4) the game is played as follows :

  • Player 11 and 22 compete, player 11 wins.
  • Player 11 and 33 compete, player 11 wins.
  • Player 11 and 44 compete, player 44 wins.

Hence, we print W(1,4)=S4=RW(1,4)=S4=R

For W(3,4)W(3,4) the game is played as follows :

  • Player 33 and 44 compete, player 33 wins.

Hence, we print W(3,4)=S3=P

SOLUTION

Program Python: Rock Paper Scissors ROPASCI Solution in Python

# cook your dish here
def match(a,b):
    if a==b:
        return a
    
    if a == 'S' and b == 'R' or a == 'R' and b == 'S':
        return 'R'
    elif a == 'S' and b == 'P' or a == 'P' and b == 'S':
        return 'S'
    elif a == 'P' and b == 'R' or a == 'R' and b == 'P':
        return 'P'
    else:
        return None
    
for _ in range(int(input())):
    n = int(input())
    s = input()
    
    dp_r = [None]*(n+1)
    dp_p = [None]*(n+1)
    dp_s = [None]*(n+1)
    
    ans = [None]*(n+1)
    
    #base case
    ans[n] = s[n-1]
    dp_r[n] = match('R', s[n-1])
    dp_p[n] = match('P', s[n-1])
    dp_s[n] = match('S', s[n-1])
    
    for i in range(n-1,1-1,-1):
        #find dp_arrays and ans
        
        #dp_r
        r_res = match('R', s[i-1])
        
        if r_res == 'R':
            dp_r[i] = dp_r[i+1]
        elif r_res == 'P':
            dp_r[i] = dp_p[i+1]
        elif r_res == 'S':
            dp_r[i] = dp_s[i+1]
        
        #dp_p
        p_res = match('P', s[i-1])
        
        if p_res == 'R':
            dp_p[i] = dp_r[i+1]
        elif p_res == 'P':
            dp_p[i] = dp_p[i+1]
        elif p_res == 'S':
            dp_p[i] = dp_s[i+1]
        
        #dp_s
        s_res = match('S', s[i-1])
        
        if s_res == 'R':
            dp_s[i] = dp_r[i+1]
        elif s_res == 'P':
            dp_s[i] = dp_p[i+1]
        elif s_res == 'S':
            dp_s[i] = dp_s[i+1]
        
        #ans
        if s[i-1] == 'R':
            ans[i] = dp_r[i+1]
        elif s[i-1] == 'P':
            ans[i] = dp_p[i+1]
        elif s[i-1] == 'S':
            ans[i] = dp_s[i+1]
        
    print(''.join(ans[1:]))

Program C++: Rock Paper Scissors ROPASCI Solution in C++

#include <iostream>
#include<cassert>
#include<vector>
#include<string>
using namespace std;

char match(char a, char b)
{
    if(a==b) return a;
    
    else if(a=='R' && b=='P' || a=='P' && b=='R')
    {
        return 'P';
    }
    else if(a=='R' && b=='S' || a=='S' && b=='R')
    {
        return 'R';
        
    }
    else if(a=='P' && b=='S' || a=='S' && b=='P')
    {
        return 'S';
    }
    else
    {
        assert (false);
    }
    
}
int main() {
	// your code goes here
	int t;
	cin>> t;
	
	while(t--)
	{
	    int n;
	    cin>>n;
	    string s;
	    cin>>s;
	    
	    vector<char> dp_r(n+1);
	    vector<char> dp_p(n+1);
	    vector<char> dp_s(n+1);
	    
	    vector<char> ans(n+1);
	    
	    ans[n]=s[n-1];
	    dp_r[n]=match('R', s[n-1]);
	    dp_p[n]=match('P', s[n-1]);
	    dp_s[n]=match('S', s[n-1]);
	    
	    for(int i =n-1;i>=1;i--)
	    {
	        char r_res = match('R', s[i-1]);
	        if(r_res=='R')
	        {
	            dp_r[i]= dp_r[i+1];
	        }
	        else if(r_res=='P')
	        {
	            dp_r[i]= dp_p[i+1];
	        }
	        else if(r_res=='S')
	        {
	            dp_r[i]= dp_s[i+1];
	        }
	        
	        char p_res = match('P', s[i-1]);
	        if(p_res=='R')
	        {
	            dp_p[i]= dp_r[i+1];
	        }
	        else if(p_res=='P')
	        {
	            dp_p[i]= dp_p[i+1];
	        }
	        else if(p_res=='S')
	        {
	            dp_p[i]= dp_s[i+1];
	        }
	        
	        char s_res = match('S', s[i-1]);
	        if(s_res=='R')
	        {
	            dp_s[i]= dp_r[i+1];
	        }
	        else if(s_res=='P')
	        {
	            dp_s[i]= dp_p[i+1];
	        }
	        else if(s_res=='S')
	        {
	            dp_s[i]= dp_s[i+1];
	        }
	        
	        
	        if(s[i-1] == 'R')
	        {
	            ans[i]=dp_r[i+1];
	        }
	        
	        else if(s[i-1] == 'P')
	        {
	            ans[i]=dp_p[i+1];
	        }
	        else if(s[i-1] == 'S')
	        {
	            ans[i]=dp_s[i+1];
	        }
	    } 
	
	    for(int i =1; i<=n;i++)
	    {
	        cout<<ans[i];
	    }
	    cout<<endl ;
	}
	

}

December Long Challenge 2021 Solution

Leave a Comment