PROBLEM LINK:
Author: vikiwarrior
Tester: hellb0y_suru
Tester: eccentrik
Editorialist: vikiwarrior
DIFFICULTY:
EASY-MEDIUM
PROBLEM:
Given a string of R and L find the difference between the maximum possible sum of respect that can be gained and the minimum possible sum of respect that can be gained for Mr chef.
EXPLANATION:
In this question, we need to maximize and minimize the total respect gained for Mr. Chef. Let’s suppose the string given is A.
First, let’s take two elements having indices i and j where i<j, there are only four possibilities
-
A[i]=R and A[j]=R
“RR”, in this for if we process/medal the elements/athlete from left to right ie A[i]=R then A[j], the cost/respect gained is zero and if we process from right to left cost/respect will increase by 1. -
A[i]=R and A[j]=L
“RL”, in this case, whichever order we process the elements cost will increase by 1. -
A[i]=L and A[j]=R
“LR”, in this case, whichever order we process the elements cost gained will be 0. -
A[i]=L and A[j]=L
“LL”, in this for if we process/medal the elements from left to right ie A[i] then A[j], the cost/respect gained is 1 and if we process from right to left cost gained will be 0.
So, for minimum possible respect gained:
We add the cost that occur in type 2 and minimise the rest .Basically count number of indices i, j such as i < j and A[i] = R and A[j] = L.This can be done by O(N) algorithm building an array count[j] = number of Ls in range {j, j + 1, …, N} from array A.We will traverse the whole array and add the count[i] to the answer when A[i] = R.
And for maximum possible respect gained:
We add the cost that occurs in type 2 which will be the same as the minimum case answer. Additionally, we maximize type 1 and type 4 costs add them in max answer. If there are ‘P’ no of Rs in the string then we can maximize the type 1 costs by moving right to left which will give up the cost as ((P-1)+(P-2)+(P-3).......+3+2+1) i.e summation from 1 to (P-1).
Similarly, if we have ‘Q’ no of 'L's in the string then we can maximize the type 4 costs by moving left to right which will give up the cost
as ((Q-1)+(Q-2)+(Q-3).......+3+2+1) i.e summation from 1 to (Q-1).
Finally, Max. cost = Min.cost+\displaystyle\sum_{x=1}^{P-1} x +\displaystyle\sum_{x=1}^{Q-1}x
which means you just need to count the no. of Ls and Rs and evaluate this expression
Answer = Max. cost- Min.cost = \displaystyle\sum_{x=1}^{P-1} x +\displaystyle\sum_{x=1}^{Q-1}x
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
#define ll long long int
#define endl '\n'
using namespace std;
const ll mod = 1000000000+7;
int main() {
ll t;
cin>>t;
while(t--)
{
ll n,i;
cin>>n;
string s;
cin>>s;
ll c=0;
ll cc=0;
for(i=0;i<n;i++)
{
if(s[i]=='L')
c++;
else if(s[i]=='R')
cc++;
}
cout<<((c*(c-1))/2)+((cc*(cc-1))/2)<<endl;
}
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long int
#define MOD 1000000007
#define oo 1000000000000000000
#define forr(i,n) for(ll i=0;i<n;i++)
#define fastio ios_base::sync_with_stdio(false); cin.tie(0) ; cout.tie(0);
#define all(x) x.begin(),x.end()
#define eb emplace_back
#define pb push_back
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;
template<typename...T>
void read(T&... args){
((cin >> args), ...);
}
ll valueOfIndex(ordered_set&s , ll i){ return *(s.find_by_order(i)); }
ll indexOfValue(ordered_set&s , ll x){ return s.order_of_key(x); }
ll add(ll a, ll b,ll p=MOD) { a%=p; b%=p; return (a+b + p)%p;}
ll mul(ll a, ll b,ll p=MOD) { a%=p; b%=p; return (a*b + p)%p;} // __int128
ll power(ll x,ll n,ll p=MOD){ if(x==0) return 0; if(n==0 || x==1) return 1LL;
ll r = (power(x,n/2,p))%p; if(n&1) return mul(mul(r,r,p) , x,p); else return mul(r,r,p);
}
ll minimum(vector<char> &v,vector<ll> l, vector<ll> r ,int n){
for(int i=n-1;i>=1;i--) l[i] += l[i+1];
ll cnt=0 , ans;
for(int i=1;i<=n;i++){
if(v[i]=='R') cnt+= l[i];
}
ans = cnt;
for(int i=1;i<=n;i++) r[i] += r[i-1];
cnt = 0;
for(int i=n;i>=1;i--){
if(v[i]=='L') cnt+= r[i];
}
return min(cnt,ans);
}
ll maximum(vector<char> &v, vector<ll> l, vector<ll> r, int n){
ll left = 0,right=0;
for(int i=1;i<=n;i++){
if(v[i]=='L') left++;
else right++;
}
ll kk = left , kp = right;
for(int i=1;i<=n;i++) r[i]+=r[i-1];
ll cnt=0 , ans;
for(int i=1;i<=n;i++){
if(v[i]=='L'){
cnt+= left-1 + r[i];
left--;
}
}
ans = cnt + (right*(right-1))/2;
cnt = 0;
for(int i=n-1;i>=1;i--) l[i]+= l[i+1];
// for(int i=1;i<=n;i++) cout << l[i] << " ";
for(int i=n;i>=1;i--){
if(v[i]=='R'){
cnt+= right-1 + l[i];
right--;
}
}
cnt+= (kk*(kk-1))/2;
// cout << cnt << "\n";
return max(cnt,ans);
}
void __sol(){
int n;
cin >> n;
vector<ll> l(n+2) , r(n+2);
vector<char> v(n+2);
for(int i=1;i<=n;i++){
char c; cin >> c;
if(c=='L') l[i]=1;
else r[i]=1;
v[i] = c;
}
cout << maximum(v,l,r,n) - minimum(v,l,r,n) << "\n";
return;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
fastio
ll tc=1; cin >> tc;
while(tc--) __sol();
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >>t;
while(t--)
{
int n;cin >>n;
string s;
cin >>s;
int left=0,right=0;
for(int i=0;i<s.length();i++)
{
if(s.at(i)=='L')
{
left++;
}
else
{
right++;
}
}
long ans=0;
if(left>0)
{
ans=ans+(((left)*(left-1))/2);
}
if(right>0)
{
ans=ans+(((right)*(right-1))/2);
}
cout <<ans<<'\n';
}
return 0;
}
