Editorial for SAC '22 Code Challenge 5 Junior P5 - English Summative

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: maxcruickshanks

Subtask 1

It suffices to iterate over all possible subsets of the N words and count the number of consecutive pairs of letters.

Time Complexity: \mathcal{O}(2^N N)

Subtask 2

Realize that this problem can be modelled with dynamic programming:

DP[i] represents the maximum number of consecutive pairs of letters that ends at the i^\text{th} word.

The recurrence of DP[i] is DP[i] = \max(DP[j] + CNT[j] + LAST[j] == FIRST[i]), where 0 \le j < i, DP[0] = 0, FIRST[i] is the first character of the i^\text{th} word, LAST[j] is the last character of the j^\text{th} word, and CNT[j] is the number of consecuive pairs of letters in the j^\text{th} word.

Finally, output DP[N].

Time Complexity: \mathcal{O}(N^2)

Subtask 3

Realize that subtask 2 can be greedily optimized by only maintaining the index of the last 26 lowercase letters and the maximum DP value for that character.

Time Complexity: \mathcal{O}(26 N)


There are no comments at the moment.