LeftAndRightHandedDiv1 | Topcoder Archive

Problem Statement

A very large group of people is sitting around a very large round table. Each of them is either left-handed or right-handed. We will use the characters 'L' and 'R' to denote a left-handed and a right-handed person. A collision occurs whenever a left-handed person sits immediately to the right of a right-handed person. (This is because their elbows tend to collide.)

You want to minimize the number of collisions. The only operation you are allowed to do is to swap a pair of adjacent people. For example, if we have 5 people and their current order around the table is "RLRRL", in one step we can change it to any of the orders "LRRRL", "RRLRL", "RLRRL", "RLRLR", and "LLRRR". (Note that the table is round, thus the last person in our description is adjacent to the first one.)

You are given a String Y. Each character of Y is either 'L' or 'R'. You are also given ints A, B, C, D, and N. N is the number of people sitting around the table. All the other variables (including Y) are used to generate a string P of length N. The string P describes the initial seating, and it is generated as follows:

Let T[0]=A, and for each i from 1 to N-1 let T[i] = (T[i-1] * B + C) % D, where % is the modulo operator. Now, for each i from 0 to N-1, let P[i] = Y[ T[i] % length(Y) ].

As we already stated, your goal is to minimize the number of collisions. Return the smallest number of allowed swaps in which that minimum can be reached.

Definition

Class:: LeftAndRightHandedDiv1
Method:: countSwaps
Parameters:: String, int, int, int, int, int
Returns:: long
Method signature:: long countSwaps(String Y, int A, int B, int C, int D, int N)
(be sure your method is public)

Constraints

Y will contain between 1 and 2500 characters, inclusive.
Each character of Y will be either 'L' or 'R'.
D will be between 1 and 10^9, inclusive.
A, B, and C will each be between 0 and D-1, inclusive.
N will be between 1 and 10^6, inclusive.

Examples

```
"LR"
```
```
1
```
```
0
```
```
1
```
```
2
```
```
1
```
```
Returns: 0
```
The initial configuration is R, so no swaps are needed.
```
"LRLR"
```
```
1
```
```
1
```
```
2
```
```
3
```
```
4
```
```
Returns: 0
```
The initial configuration is RLLR, so no swaps are needed.
```
"LRRLLR"
```
```
2
```
```
3
```
```
4
```
```
5
```
```
6
```
```
Returns: 1
```
The initial configuration is RLLRRL. After the first person and the last person are swapped, it becomes LLLRRR. Therefore one swap is enough.
```
"LRRLRLLRLRLRLLRLR"
```
```
12
```
```
15
```
```
3
```
```
22
```
```
10
```
```
Returns: 2
```
The initial configuration is LRLLRRRRLL.
```
"LLLLLLLLL"
```
```
0
```
```
1
```
```
2
```
```
3
```
```
1000000
```
```
Returns: 0
```
Everyone is left-handed, so there is no need to make any swaps.

"RLRRRLLLRLRLLRLRLLRLRLLLLLRRLRLRLRLRLLRRRLRRLLLLLRRRLRRLRLRRLLLLRLRRLRLRRLRRLRLLRRLRLRRRLRLLRLLLLRLLLLRLLRRLLRRRRLLRLLRLRLRRLL"

48658960

221863772

385355602

393787970

Returns: 59619692663

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.