URI – Warm up Contest to OBI 2016 – first phase

Hey there,

Recently happened the Warm up Contest to OBI 2016 and I was one of the authors, it was a nice experience!

I wrote 3 problems: Prant and the Indecision, Odd, Even or Cheating e Setting up a Date.

The portuguese editorial is in this link. Soon may be an english editorial :)!

Since an english editorial is not available, I’ll make a fast editorial of my problems, hope this helps!

Odd, Even or Cheating

By: Marianne Linhares

In this problem the rules of the game must be well understood and correctly implemented.
There are only 2 possibilities of result, player 1 wins or player 2 wins, a draw is not possible.
The possible cases of player 1 to win are:

  • The numbers chosen doesn’t matter, player 1 cheats and player 2 doesn’t accuse player 1
  • The numbers chosen doesn’t matter, player 1 doesn’t cheat and player 2 accuses player 1
  • Player 1 chooses even, player 1 doesn’t cheat, player 2 doesn’t accuse player 1 and the sum of the chosen numbers is even
  • Player 1 chooses odd, player 1 doesn’t cheat, player 2 doesn’t accuse player 1 and the sum of the chosen numbers is odd

If none of these cases happen then player 2 wins.

  • Complexity: constant.

Setting up a Date

By: Marianne Linhares

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.

l.png

 

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).

  • Complexity: basically constant.

Prant and the Indecision

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)
URI – Warm up Contest to OBI 2016 – first phase

#Random Code 1 – Books Catalog/Catálogo de Livros 1802 (URI)

Hi! In this article we’ll discuss the Books Catalog from URI.
It’s a nice question that’s involves the following concepts: algorithm efficiency, think a bit, and Brute force.

So, talking about the problem! In summary we have different set of books, where each set defined by a subject (portuguese, math, physics, chemistry and biology). We know that each book of a certain subject has a value associated and we want to make a set composed by one book of each subject. Given a number K we want to know the sum of the K most valuable sets.

If is not clear, try to understand with the example bellow:

The input is composed by 6 lines, the 5 first are defining  the values of the books of a certain subject where the first number is how many books of this subject there is (1 <= n <= 5). Then there is n numbers, (v1,v2,v3,…vi, where i <= n and 1 <= vi <= 1000), these are the values of each book in the set. The next line is just K.  Sample:

5 2 5 6 3 8
5 9 6 3 1 5
5 4 8 5 2 6
5 3 2 4 9 5
5 7 8 5 1 4
1


In this case what is the answer? Well, K = 1 so we want to know the most valuable set possible. In this case a greedy solution works, we get the most valuable book of each subject and the sum is the answer  of the most valuable set possible.
Bellow in green there are the elements we are present in the set, and the answer would be 42.

5 2 5 6 3 8
9 6 3 1 5
5 4 8 5 2 6
5 3 2 4 9 5
5 7 8 5 1 4
1

8 + 9 + 8 + 9 + 8 = 42.

If K was equal to 2. We would be looking for the sum of the most valuable set + the second one. The second most valuable set, that is represented bellow in yellow, that sums up 41, so the answer is 42 + 41 = 83.
 
5 2 5 6 3 8
9 6 3 1 5
5 4 8 5 2 6
5 3 2 4 9 5
7 8 5 1 4
1
8 + 9 + 8 + 9 + 7 = 41.

Ok, nice… But when K > 1 we’ll have to choose some book to be removed and another one to be inserted in the set… that seems a hard choice…

So, how to use this idea in a simpler way?
Tip: always look at the input size.

 
 (number of books of each different set) is <= 5. That’s a pretty small number, and we can implement a “not so efficient” solution. We also know that K is less than P*M*Q*F*B

This make sense because we have to compose a set of (p, m, q, f, b),  p is portuguese book, m is a math book, …, so P*M*Q*F*B possibilities exists.

 

With these information we know that in the worst case P = M = Q = F = B = 5, so K5*5*5*5*5 = 5⁵ = 3125.

So…we can try all the possibilities!

 

for p in portuguese:
   for m in math:
      for f in physics:
          for q in chemistry:
             for b in biology:
                 (p + m + f + q + b) is a value of a possible set!

So if you put these possible values in a list, sort the list, and you’ll get your answer, right?

https://gist.github.com/mari-linhares/f4455cdf1115041d723c.js

#Random Code 1 – Books Catalog/Catálogo de Livros 1802 (URI)