This problem can be solved using Geometric Probability. We can define the possible arrival times of Mel and Tob as points in the cartesian coordinate system, each possible time is a (x, y) inside the square determined by (0, 0) and (t2-t1, t2-t1) that represents the possible meeting interval.

We also have the maximum wait time N as a constant that will determine the possible area of meeting. This whole situation can be represented bellow.

So, the probability of happening a meet is defined by A1/AT.

To get the irreductible fraction just divide each term by gcd(A1, AT).

*By: Marianne Linhares*

The problem can be easily understood through the sample. But summarizing the problem situation: given a string of size m and n changing letters operations (1 ≤ m, n ≤ 100 000), such that a change letter operation consists of changing all letters a to b and all letters b to a in the current word, you should make a program that determines which word contains more favorite letters. Then, the difficulty of the problem is how to obtain such word in an efficient way, because a solution that simulates the changes directly would be O(m * n) and would not be fast enough.

A possible solution is instead of update the entire word at each change just update the letters involved in the change. This can be done through an array that relates each letter to some other (in other words, it holds the current status of the changes), besides another array that holds how many times each letter appears in the word. Bellow there is an example of how a change could be simulated following the described implementation, where ch is the array that holds the “relations” and value holds the number of occurrences of each letter in the current word:

scanf(" %c %c", &c1, &c2);
int , ;
for(int j = 0; j < 26; j++) {
if(ch[j] == c1) pos_c1 = j;
if(ch[j] == c2) pos_c2 = j;
}
aux = ch[pos_c1]; ch[pos_c1] = ch[pos_c2]; ch[pos_c2] = aux;
aux = value[c1 - 'a']; value[c1 - 'a'] = value[c2 - 'a']; value[c2 - 'a'] = aux;

So, after update these arrays you should verify if the sum of the occurrences of the favorite letters (you can get this information trough the value array in O(26) is the greatest until now, if this happens just copy the ch array into another so in the end you can print the word.

PS: Another way to implement this is using a map. The solution will be more intuitive but a little less efficient(a constant irrelevant will be added).

**Complexity**: O(26 * n)
**Complexity using a map**: O(26 * n * log(26)