TreasureOfWinedag | Topcoder Archive

Problem Statement

Zhangzj is the ruler of Yali Empire. One day, TgopKnight, a knight from Tang Goupu, a county in the empire, discovers a record of a huge treasure from the ancient Empire of Winedag. Exhilarated by the prospect of restoring it, Zhangzj doesn't hesitate to order TgopKnight to find it as soon as possible. Unfortunately, upon arriving at the treasury, TgopKnight find that the entry is locked by a puzzle. With a supreme respect for Zhangzj, TgopKnight is determined to solve the puzzle.

Here is the puzzle. The value of a string is the number of distinct letters in it. Given a String str, split it into exactly K non-empty substring, so that the sum of the values of each substring is minimal. The specific definition of substring is in the Notes.

Due to a technical restriction, the String str will be generated using a generator. You are given ints N, m, c0, int[]s c1, c2, c3, c4, and a String s. Compute str using the following pseudocode:

str = s
for i in s.length() .. N-1:
	let t = (i * c0) mod m
	let newChar = 'z'
	for j in 0 .. 24:
		if (t &gt= c3[j]) and (t &lt= c4[j]) and ((t mod c1[j]) == c2[j])
			newChar = 'a' + j
			break
	str += newChar

Definition

Class:: TreasureOfWinedag
Method:: solvePuzzle
Parameters:: int, int, int, int, int[], int[], int[], int[], String
Returns:: int
Method signature:: int solvePuzzle(int N, int K, int m, int c0, int[] c1, int[] c2, int[] c3, int[] c4, String s)
(be sure your method is public)

Notes

A substring of a string is a consecutive subsequence of the string. A non-empty substring is one that contains at least one character.
The author's solution does not depend on any properties of the generator.

Constraints

N will be between 1 and 100,000, inclusive.
K will be between 1 and N, inclusive.
The length of s will be between 0 and min(1,000, N), inclusive.
s will consist of lowercase letters.
m will be between 1 and 1,000,000,000, inclusive.
c0 will be between 0 and m - 1, inclusive.
Each of c1, c2, c3, c4 contains exactly 25 elements.
For each i, c1[i] will be between 1 and m, inclusive.
For each i, c2[i] will be between 0 and c1[i] - 1, inclusive.
For each i, c3[i] will be between 0 and m - 1, inclusive.
For each i, c4[i] will be between c3[i] and m - 1, inclusive.

Examples

{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

"aabb"

Returns: 2

str = "aabb". If you split it into "aa" and "bb", the values of two substrings are 1 and 1. The sum of them is 2. No other ways of splitting the string yield a smaller sum.

{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

"abaacdddfeff"

Returns: 6

str = "abaacdddfeff". This time the optimal solution is to split the string into "abaa", "cddd" and "feff".

{4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

{0, 1, 2, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

{9, 9, 9, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

""

Returns: 6

str = "adababcbcd".

{2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

{0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

{0, 0, 50000, 50000, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

{49999, 49999, 99999, 99999, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

""

Returns: 4

The first half of the string consists of 'a' and 'b', and the second half consists of 'c' and 'd'. Therefore, it is possible to split the string into two substrings, each containing only 2 distinct letters.

{26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26}

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24}

{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

{987653, 987653, 987653, 987653, 987653, 987653, 987653, 987653, 987653, 987653, 987653, 987653, 987653, 987653, 987653, 987653, 987653, 987653, 987653, 987653, 987653, 987653, 987653, 987653, 987653}

"topcoderopen"

Returns: 99990

424507751

79193201

{93991416, 122377683, 100930010, 373124588, 366757111, 314344105, 335481602, 25553224, 271158873, 131361019, 331824611, 152948279, 126679689, 84708668, 6797210, 361729904, 145699274, 79606375, 264167932, 413280894, 15762918, 207584964, 154302042, 70002530, 194642143}

{83184146, 70533279, 73860028, 211278755, 121940531, 286864621, 251852612, 18877531, 173979121, 104440673, 50907689, 29428358, 82351994, 20366667, 1415145, 165813027, 100425184, 11939160, 31133943, 157023871, 6513169, 86669984, 104254852, 21419693, 61982959}

{133139882, 123741581, 58820135, 40395052, 204057998, 220052469, 47757992, 135477098, 81874422, 38543527, 64336686, 54070556, 85767758, 394101179, 47318637, 141026976, 283673073, 227348343, 405835722, 203692488, 261118934, 76467402, 110499099, 179937390, 62000638}

{171061341, 420093260, 115970860, 246835989, 273845074, 423933877, 264762986, 225084596, 374349399, 242851788, 292230379, 173105221, 112972969, 417034170, 279113506, 255955057, 297052869, 264177905, 408974790, 348069397, 408363094, 224880992, 416173264, 296181015, 351748226}

"c"

Returns: 1

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.