Tala is studying very hard for COMP20007. They read the corresponding book chapters every week to consolidate their understanding of the subject material.

To help with their studying. Tala likes to use highlighters of different colours. Here is an example, taken from the chapter on Brute Force methods:

In this example, Tala used blue to highlight the words "brute force", yellow to highlight the word "problem" and green to highlight "problem statement".

After doing this manually for years, Tala had the idea to write a program that automatically highlights terms. To do this, they used a program to read their past notes and check, for each word, how many times it was highlighted. This led to a collection of tables, one per word, with scores relative to how           frequent that word was highlighted and which colour. For example, for the word "problem", the table looks like this:

In this example, yellow has a larger score because it is the most frequent colour the word "problem"        appears in Tala's notes. Note there is also a row for no colour, meaning the word is not highlighted. After using the program to read their notes, Tala ends up with a set of tables like the one above, one per word.

Part A (code)

For the first automatic highlighter program, you should implement a C program that reads as input:

- A sentence. This is just a sequence of words split by whitespace, with no punctuation marks.

- A set of word tables. The set will only contain tables for words that appear in the sentence. You can  assume there are only 4 colours and they are represented as integers from 0 to 3: 0 is "no colour", 1 is "green", 2 is "yellow" and 3 is "blue".

Then, it generates as the output:

- A sequence of colours, one per word. This should be a sequence of integer values, where each integer represent a colour, as above.

The output sequence of colours should follow an optimisation criterion: it is the sequence with the      highest total score. For Part A, the total score is the sum of individual scores per word. Formally          speaking, assume a sentence has n words, with each word w numbered from 1 to n. Assume F(n) gives the maximum score for a sentence, which we define as

where WC(w,c) corresponds to the score for colour c in word table w. The first term states that our goal is to the maximise the score given a sequence of words/colours The second term then simplifies this to      maximise the score for each individual word/colour.

The equation above only gives the maximum score: your code should generate the sequence of colours that gives this maximum score.

Part B (code)

Following testing of the previous program, Tala is a bit frustrated because it would always pick the same colour for each term. But as show in the example above with the word "problem", sometimes the same  word can be highlighted with different colours, depending on the sentence.

To solve this problem, Tala introduces an extra colour transition table. This table gives scores for colours given the previous colour. Here is an example:

In this example table, if the previous word is highlighted in blue and the current word is also blue (as in the "brute force" example above), this transition gives a score of 10.

For the second automatic highlighter, you should enhance the code in Part A. The input is now:

- A sentence. As in Part A.

- A set of word tables. As in Part A.

- A colour transition table. Each entry in this table has two integers, corresponding to previous colour and colour, and a score. Integers represents colours, as in Part A.

The output is the same as Part A: a sequence of integers that gives the optimal highlighting. However, the criterion of highest total score now needs to sum the colour transition scores as well. Your program           should follow a greedy approach: for every word from left to right, select the colour based on the               maximum sum of two scores: the one from the word table and the one for the transition table.

Part C (written solution)

Tala is pleased with the result but notices the colouring could sometimes still be better. They realise the greedy algorithm in Part B is not actually generating the optimal sequence. To see this, we can write the formal equation for the maximiser with the colour transition table: