harshuiui's blog

Robot Positions
By harshuiui, history, 11 months ago, In English

Problem Statement:

N robots are standing in a line consisting of N squares numbered from 1 to N. Initially, the ithith robot is standing on the ith square. Each square has a letter 'L' or 'R' written on it. After 1 second, each robot moves one unit in the left direction if its square has the letter 'L' and moves one unit in the right direction if its square has the letter 'R'. It is guaranteed that the letter on the leftmost square is always 'R' and on the rightmost square is 'L'. You are given a string S of length N denoting the letter written on each square. You must determine how many robots would stand on each square after 10^5 seconds. Output a string of length N, where the ith character represents the number of robots on the ith square after 10^5 seconds. Input Format * The first line contains a single integer TT, the number of test cases. For each test case: * A single line containing the string SS of length NN. Output Format Output a single line for each test case: the string of length NN representing the number of robots on each square after 105105 seconds. Constraints * 1≤T≤10^5 * 1≤∣S∣≤10^5 * The sum of the lengths of SS over all test cases does not exceed 10^6

SAMPLE:

Input : 3 RLL
Expected Output : 210

The question is not really complicated but lately I have been noticing that quite a few of my solution give WA based on things I don't realize are problems, like using just a count instead of a vector even though they give the same answer and stuff like that, just implementation details, so here is the code I wrote for it and after that I have attached the code that is the editorial solution can somebody PLEASE TELL ME WHAT IS WRONG WITH MY CODE(it gives WA on all test cases except one)

MY CODE:

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

int solve(){
    string s;
    cin>>s;
    if(s.size()==1){
        cout<<1<<"\n";
    }
    vector<int> marker(s.size());
    unordered_map<int,int> L_occ;
    int SEC = 100000;
    int cnt=0;
    for(int i=0;i<s.size();i++){
        if((i>0)&&(s[i]!=s[i-1])){
            cnt++;
            if(s[i]=='L')L_occ[cnt]=i;
        }
        if(s[i]=='R'){
            marker[i]=cnt;
        }
        else{
            marker[i]=cnt;
        }
    }
    // for(int i=0;i<s.size();i++)cout<<marker[i]<<" ";
    // for(auto [k,v]:L_occ){
    //     cout<<k<<":"<<v<<"\n";
    // }
    // cout<<"\n";
    vector<int> ans(s.size(),1);
    for(int i=0;i<s.size();i++){
        if(marker[i]%2==0){
            int L_idx = L_occ[marker[i]+1];
            int par = (SEC-(L_idx-i))%2;
            if(par){
                ans[L_idx-1]++;
                ans[i]--;
            }
            else{
                ans[L_idx]++;
                ans[i]--;
            }
        }
        else{
            int L_idx = L_occ[marker[i]];
            int par = (SEC-(i-L_idx))%2;
            if(par){
                ans[L_idx]++;
                ans[i]--;
            }
            else{
                ans[L_idx-1]++;
                ans[i]--;
            }
        }
    }
    for(int i=0;i<s.size();i++)cout<<ans[i];
    cout<<"\n";
    return 0;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    int t=1;
    cin>>t;
    while(t--){
        solve();
    }

    return 0;
}

SOLUTION:

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

#define ll long long
#define mod 1000000007
#define mod2 998244353

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  
  long long t;
  cin >> t;

  for (int tt = 1; tt <= t; tt++) {
    string str;
    cin >> str;
    int n = str.size();
    int prev = 0;
    vector<int> before(n), after(n);
    for (int i = 0; i < n; i++) {
      before[i] = prev;
      if (str[i] == 'R') prev = i;
    }
    prev = n - 1;
    for (int i = n - 1; i >= 0; i--) {
      after[i] = prev;
      if (str[i] == 'L') prev = i;
    }
    vector<int> cnt(n, 0);
    for (int i = 0; i < n; i++) {
      if (str[i] == 'L') {
        int diff = i - before[i];
        if (diff % 2 == 0)
          cnt[before[i]]++;
        else
          cnt[before[i] + 1]++;
      } else {
        int diff = after[i] - i;
        if (diff % 2 == 0) {
          cnt[after[i]]++;
        } else {
          cnt[after[i] - 1]++;
        }
      }
    }
    int sum = 0;
    for (int i = 0; i < n; ++i) {
      cout << cnt[i];
    }
    cout << endl;
  }
  return 0;
}
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
11 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by harshuiui (previous revision, new revision, compare).

→ Reply
»
11 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I think your problem is that you are using one cnt and a single L_occ map so you never correctly record the matching L for every trailing run of R's so marker[i] ends up pointing at the wrong boundary index

for example in RRRLLR your loop only sets L_occ[1]=3 and L_occ[2]=5, but because you only assign when you see an L after a change the final lone R at position 5 never gets a proper L_occ entry for its cnt then when you doo int L_idx = L_occ[marker[i]+1] for that robot you are actually looking up a non existent key so you pick the wrong boundary and your parity check sends the robot to the wrong squar

→ Reply
  • »
    »
    11 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    RRRLLR cannot be a valid input as the rightmost square has to have a L and the leftmost square has to have a R so if the input was RRRLLRL my L_occ would be 1:3 and 3:6 and for the last second last R its marker would be 2 so it'll look for 3 find its L_occ at idx 6 and then calculate position accordingly

    → Reply
»
11 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Is my approach correct?

Code
→ Reply
»
11 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

BAbbee!!

#include <bits/stdc++.h>
using namespace std;
using ll= long long;
const int MOD = 1e9+7;

void solution(){
    string s;
    cin>>s;
    int n = s.size();
    vector<int>res(n,0);
    int i=0;
    while(i<n){
        if(s[i]=='R'){
            int rstart = i;
            while(s[i]=='R') i++;
            int rend = i-1;
            
            int lstart = i;
            while(i<n && s[i] =='L') i++;
            int lend = i-1;
            res[rend] = ceil((rend-rstart+1)/2.0) + floor((lend-lstart+1)/2.0);
            res[lstart] = floor((rend-rstart+1)/2.0) + ceil((lend-lstart+1)/2.0);

        }
        else i++;
    }
    for(auto v:res){
        cout<<v;
    }cout<<"\n";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        solution();
    }
    
    return 0;
}
→ Reply