RearrangePages
SRM 794 · 2020-11-24 · by misof
Problem Statement
Peter is writing a thesis. He's not really a technical type, so he's using a text editor and his whole thesis is one huge file. The file contains N pages, numbered from 0 to N-1. The number N is even.
Exactly one half of the pages contain text and the other half contain images. Currently, the pages with images have numbers of the form ((A + i * B) mod N) where 0 <= i < N/2. (It is guaranteed that these are N/2 different pages.)
For example, if N = 10, A = 2 and B = 3, the image pages have the following numbers:
- (2 + 0*3) mod 10 = 2,
- (2 + 1*3) mod 10 = 5,
- (2 + 2*3) mod 10 = 8,
- (2 + 3*3) mod 10 = 11 mod 10 = 1, and
- (2 + 4*3) mod 10 = 14 mod 10 = 4.
Thus, there would be images on pages 1, 2, 4, 5, 8, and text on pages 0, 3, 6, 7, 9.
Watch out for integer overflow when computing the values (A + i * B).
Peter has now decided that he wants to rearrange his thesis into a more reader-friendly form: the pages should alternate between text and images. More precisely, the even-numbered pages (0, 2, 4, ...) should contain text and the odd-numbered pages (1, 3, 5, ...) should contain images.
The main issue now is the text editor. Haphazardly moving pages from place to place will break all formatting, references and such, and Peter does not want to spend ages fixing the document after each such edit. The only operation he's comfortable doing is swapping the order of two consecutive pages.
Compute and return the minimum number of such swaps Peter needs to make in order to rearrange his thesis into the desired pattern.
Notes
- The last constraint requires that B and N must be relatively prime. In other words, they must not have any common divisor other than 1. This constraint guarantees that the N/2 page numbers given in the problem statement are distinct.
Constraints
- N will be between 2 and 1,000,000, inclusive.
- N will be even.
- A will be between 0 and N-1, inclusive.
- B will be between 1 and N-1, inclusive.
- B and N will be relatively prime.
6 1 1 Returns: 3
The thesis has 6 pages. Pages with images are pages 1, 2, 3. Thus, the thesis now looks like this: "text, image, image, image, text, text". We can rearrange this thesis as follows: Swap the pages with current (0-based) indices 3 and 4. New thesis: "text, image, image, text, image, text". Swap the pages with current indices 4 and 5. New thesis: "text, image, image, text, text, image". Swap the pages with current indices 2 and 3. New thesis: "text, image, text, image, text, image" and we are done.
10 0 3 Returns: 5
The thesis has 10 pages. Pages with images are pages 0, 3, 6, 9, and (12 mod 10) = 2. Thus, currently the thesis looks as follows: image, text, image, image, text, text, image, text, text, image. If Peter chooses his swaps wisely, he can rearrange the pages of this thesis using five swaps.
10 5 1 Returns: 10
This thesis starts with five pages with text and then contains five pages with images. We need 10 swaps to rearrange it into "text, image, text, image, ...". Remember that we are only allowed to swap consecutive pages.
1000000 500000 1 Returns: 124999750000
1000000 0 1 Returns: 125000250000
Submissions are judged against all 96 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RearrangePages with a public method long long countSwaps(int N, int A, int B) · 96 test cases · 2 s / 256 MB per case