TopCoder SRM 786 - 250: SwapTheString

Problem Statement

You are given a string S of length N. You are also given an integer K. In each step, you are allowed to select an index i and swap the characters at indices i and i + K (such that i + K < N) in the string S. After the swap, the new formed string should be lexographically greater than the old string. You keep on performing such steps, as long as possible. You need to find the maximum number of steps that can be performed on the given string.

You are given integers A0, X, Y and N and a string P. Use the pseudocode below to generate the string S.

A[0] = A0 for i = 1 to N-1: A[i] = (A[i-1] * X + Y) modulo 1812447359 S = P for i = size(P) to N-1: S[i] = (char)(A[i] % 26 + 'a')

Definition

Class SwapTheString
Method findNumberOfSwaps
Parameters string , int , int , int , int , int
Returns long long
Method signature long long findNumberOfSwaps(string P, int A0, int X, int Y, int N, int K)

(be sure your method is public)

Limits

Time limit (s) 2.000
Memory limit (MB) 256

Constraints

The length of P will be between 0 and min(N, 100) (inclusive)
A0 will be between 0 and 1812447358 (inclusive)
X will be between 0 and 1812447358 (inclusive)
Y will be between 0 and 1812447358 (inclusive)
N will be between 1 and 200,000 (inclusive)
K will be between 1 and N (inclusive)
String P will only contain lowercase English letters ('a'-'z').

Test cases

input
- P "cbexa"
- A0 0
- X 0
- Y 0
- N 5
- K 2
output
Returns 2

note

There are 2 possible swaps in string "cbexa" : "cbexa" -> "cxeba" (swapping characters at index 1 and 3) and then "cxeba" -> "excba" (swapping characters at index 0 and 2). Note that if the k would have been 1, more swaps would have been possible.
input
- P ""
- A0 5
- X 2
- Y 3
- N 4
- K 1
output
Returns 3

note

The string here is "fndj". There are 3 swaps possible : "fndj" -> "fnjd", "fnjd" -> "nfjd" and "nfjd" -> "njfd". Note that there can be multiple ways to do these swaps.
input
- P "b"
- A0 1001
- X 1001
- Y 1001
- N 5
- K 2
output
Returns 3

note

The string is "banol". There are 3 swaps possible : "banol" -> "bonal", "bonal" -> "nobal" and "nobal" -> "nolab".
input
- P ""
- A0 9999
- X 50000
- Y 4797
- N 6
- K 3
output
Returns 2
input
- P ""
- A0 3435
- X 1000000000
- Y 1812447358
- N 7
- K 2
output
Returns 5

SRM 786 1 250 SwapTheString

Problem Statement

Definition

Limits

Constraints

Test cases