LeftAndRightHandedDiv1
SRM 612 · 2013-12-22 · by ltaravilse
SRM 612 · 2013-12-22 · by ltaravilse · Simulation, Sorting
Problem Statement
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 aString Y.
Each character of Y is either 'L' or 'R'.
You are also given int s 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.
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
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.
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
0)
"LR" 1 0 1 2 1 Returns: 0
The initial configuration is R, so no swaps are needed.
1)
"LRLR" 1 1 2 3 4 Returns: 0
The initial configuration is RLLR, so no swaps are needed.
2)
"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.
3)
"LRRLRLLRLRLRLLRLR" 12 15 3 22 10 Returns: 2
The initial configuration is LRLLRRRRLL.
4)
"LLLLLLLLL" 0 1 2 3 1000000 Returns: 0
Everyone is left-handed, so there is no need to make any swaps.
Submissions are judged against all 46 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class LeftAndRightHandedDiv1 with a public method long long countSwaps(string Y, int A, int B, int C, int D, int N) · 46 test cases · 2 s / 256 MB per case