Connection Status:
Competition Arena > TreasureOfWinedag

TreasureOfWinedag

TCO17 Round 2C · 2017-03-31 · by matthew99a

TCO17 Round 2C · 2017-03-31 · by matthew99a · Dynamic Programming
Class Name: TreasureOfWinedag
Return Type: int
Method Name: solvePuzzle
Arg Types: (int, int, int, int, vector<int>, vector<int>, vector<int>, vector<int>, string)
Problem Statement

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

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
0)
4
2
1
0
{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)
12
3
1
0
{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".

2)
10
4
10
7
{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".

3)
100000
2
100000
1
{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.

4)
100000
99980
987654
654321
{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

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

Coding Area

Language: C++17 · define a public class TreasureOfWinedag with a public method int solvePuzzle(int N, int K, int m, int c0, vector<int> c1, vector<int> c2, vector<int> c3, vector<int> c4, string s) · 234 test cases · 2 s / 256 MB per case

Submitting as anonymous