SwapTheString

SRM 786 · 2020-05-14 · by jeel_vaishnav

SRM 786 · 2020-05-14 · by jeel_vaishnav · Greedy, String Manipulation, String Parsing

Show categories

Class Name: SwapTheString

Return Type: long

Method Name: findNumberOfSwaps

Arg Types: (string, int, int, int, int, int)

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')

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').

Examples

"prprp"
0
0
0
5
2
Returns: 0

""
23
1
0
5
1
Returns: 0

"yjdfl"
523352556
1077024198
1558842954
5
1
Returns: 4

""
727276963
1291795787
506991530
5
1
Returns: 1

"dukog"
421399669
1715501491
257283161
5
2
Returns: 2

118)

"cbexa"
0
0
0
5
2
Returns: 2

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.

119)

""
5
2
3
4
1
Returns: 3

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.

120)

"b"
1001
1001
1001
5
2
Returns: 3

The string is "banol". There are 3 swaps possible : "banol" -> "bonal", "bonal" -> "nobal" and "nobal" -> "nolab".

Submissions are judged against all 146 archived test cases, of which 8 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class SwapTheString with a public method long long findNumberOfSwaps(string P, int A0, int X, int Y, int N, int K) · 146 test cases · 2 s / 256 MB per case