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$ ~N~ words and count the number of consecutive pairs of letters.

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

Subtask 2

Realize that this problem can be modelled with dynamic programming:

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

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

Finally, output $DP[N]$ ~DP[N]~.

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

Subtask 3

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

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

Comments

There are no comments at the moment.