#### Concepts Used

Strings, Hash Table

#### Difficulty Level

Hard

#### Problem Statement (Simplified):

Find the total number of children standing on each square after

`10^{100}`

rotations by every individual child. Each child moves according to`'R'`

or`'L'`

written on each square. Where`R`

stands for right and`L`

stands for left.

**See original problem statement here**

#### Test Case

```
Input:
RRLRL
Output:
0 1 2 1 1
Explanation:
After each child had moved one place to their left or right as written on their square, their final count becomes
0 2 1 1 1
Now 2 children are standing on 2nd square and 1 square on 3rd, 4th and 5th square each. After repeating the same procedure for 10^100 steps, their final position becomes,
0 1 2 1 1
```

#### Solving Approach :

Bruteforce Approach :

1) We can move each child by direction written on his square, after all, children have moved, we repeat this step for

`10^{100}`

times. After all, steps have completed, we print final counts.

2) By looking above approach we can see it would take infinite time even to process an array of smaller length. As compiler takes 1 second to process`10^{7}`

procedures, so this program takes`O(N\times{10^{100}})`

time to solve this problem for an array of size`N`

.

3) We can’t solve this problem with this approach, so we look for a more efficient approach.

Efficient Approach :

1) We know whenever the square direction is changed from

`Left`

to`Right`

or`Right`

to`Left`

, i.e. when adjacent squares have a different direction, the child will rotate circularly for all next steps in these both squares. It will repeat its position after every 2 rotations in these two squares.

2) So if we can identify when the next`Left`

will be for the current square which directs to`Right`

or when was the previous`Right`

for the current square which directs`Left`

, We can solve this problem easily.

3) For a child standing on the square which directs to`Right`

>Child will be standing on the first square statingThe position will be one less if the distance between its initial position and next`Left`

from its position if the distance between its initial position and next`Left`

square is`even`

.

>`Left`

square is`odd`

.

4) For a child standing on the square which directs to`Left`

>Child will be standing on last square statingThe position will be one closer if the distance between its initial position and previous`Right`

before it’s the position if the distance between its initial position and previous`Right`

square is`even`

.

>`Right`

square is`odd`

.

## Example

- We can visualise above approach using an example. So let’s take the initial example we discussed in the test case section.
- Our squares have
`RRLRL`

written. As every child moves according to direction written on the square, we can focus on a single child for understanding patterns.- Let’s see movements for the child standing at index 0.

- We can see the child has now gone into a loop where it is stuck at index
`1`

and`2`

depending on the step number. After every 2 steps, it repeats its position. We observe the same for the child standing on`left`

square initially, for example, we can visualise same for the child standing at last square.

- We can observe children will rotate in the loop whenever the direction of adjacent squares will change.
- We can maintain an array which saves next
`Left`

index and one for saving previous`Right`

index occurring for the current element.- As mentioned in the efficient approach we can further calculate the position of the current child. For example, a child standing at index
`0`

will have next`Left`

at index`2`

. So we will calculate the distance between both of them and check if it is`even`

or`odd`

and we’ll get final position for the child.- We’ll increase the count in the hash table by 1, where the final position will be the index of the hash table.
- So final answer become
`0 1 2 1 1`

.

## Solutions

#include<stdio.h> #include<string.h> #define maxn 100010 char s[maxn]; int n, ans[maxn], nxtL[maxn], preR[maxn]; int main() { scanf("%s", s); n = strlen(s); int i; for (i = 1; i < n; ++i) if (s[i] == 'R') preR[i] = i; else preR[i] = preR[i - 1]; for (i = n - 1; i >= 0; --i) if (s[i] == 'L') nxtL[i] = i; else nxtL[i] = nxtL[i + 1]; int step; for (i = 0; i < n; ++i) { if (s[i] == 'R') { step = (nxtL[i] - i) & 1; ++ans[nxtL[i] - step]; } else { step = (i - preR[i]) & 1; ++ans[preR[i] + step]; } } for (i = 0; i < n; ++i) printf("%d ", ans[i]); return 0; }

#include<bits/stdc++.h> #define maxn 100010 using namespace std; char s[maxn]; int n, ans[maxn], nxtL[maxn], preR[maxn]; int main() { cin>>s; n = strlen(s); int i; for (i = 1; i < n; ++i) if (s[i] == 'R') preR[i] = i; else preR[i] = preR[i - 1]; for (i = n - 1; i >= 0; --i) if (s[i] == 'L') nxtL[i] = i; else nxtL[i] = nxtL[i + 1]; int step; for (i = 0; i < n; ++i) { if (s[i] == 'R') { step = (nxtL[i] - i) & 1; ++ans[nxtL[i] - step]; } else { step = (i - preR[i]) & 1; ++ans[preR[i] + step]; } } for (i = 0; i < n; ++i) cout<<ans[i]<<" "; return 0; }

import java.util.*; import java.io.*; public class Main { public static void main(String args[]) throws IOException { Scanner sc= new Scanner(System.in); String s = sc.next(); int n = s.length(); int ans[] = new int[100010]; int nxtL[] = new int[100010]; int preR[] = new int[100010]; int i; for (i = 1; i < n; ++i) if (s.charAt(i) == 'R') preR[i] = i; else preR[i] = preR[i - 1]; for (i = n - 1; i >= 0; --i) if (s.charAt(i) == 'L') nxtL[i] = i; else nxtL[i] = nxtL[i + 1]; int step; for (i = 0; i < n; ++i) { if (s.charAt(i) == 'R') { step = (nxtL[i] - i) & 1; ++ans[nxtL[i] - step]; } else { step = (i - preR[i]) & 1; ++ans[preR[i] + step]; } } for (i = 0; i < n; ++i) System.out.print(ans[i]+" "); } }

Space Complexity of this approach would be `O(N).`