## quarta-feira, 5 de fevereiro de 2014

### Contest Bonilha - Editorial (English version)

Hi programmers! I had the honor of writing the exercises for the first open to the public contest at URI, entitled "Contest Bonilha". I thank the opportunity to the portal staff, specially to the support given by Neilor and Jean, and also to the programmer Ricardo Oliveira, who revised all the exercises and eventually corrected the exercise and/or the files of some of them.

Se você quer ver a versão em Português do editorial, venha aqui.

Congratulations to the best placed programmers:
Marcos Kawakami
dilsonguim
Hasan0540

For those who couldn't participate, the exercises are already available at the URI site.

I am going to write a small editorial with some resolution tips for the exercises. I advise you to read the editorial only after thoroughly tries of solving the problems, and I ask you to correct me if I say something non-sense.

Click at the link below to see the editorial.

How to find out the year that some planet sent the message?
R: Subtracting the travel time from the arrival year.

So, the first planet to send the message is the one who has the minimum value at arrivalTime - travelTime.

The characteristics may seem confuse, but the solution to the exercise doesn't hide any secret: it is enough to check each of the characteristics and print the result.

1 - Nobody solved all the problems.
If there is at least one line with only 1's, this characteristic is false, because such line correspond to a contestant that solved all the problems.

2 - Every problem was solved by at least one person.
If there is at least one column with only 0's, this characteristic is false, because such columns correspond to a problem that wasn't solved by anyone.

The other two are very similar.

It is enough to repeat each line A/N times, and each column B/M times. For example, if N = 3 and A = 12, it is enough to repeat each line 4 times, because 3 lines repeated 4 times is equal to 12 lines (3 * 4 = 12).

The problem falls to the repetition implementation. There are several ways to implement it, so I will leave this piece of code of how I did it:
https://github.com/crbonilha/codes/blob/master/imagem.cpp

The goal of this exercise was to present the Set Union concept, more specifically the Inclusion-Exclusion theory.

Let's see, a fast way of finding how many tiles are going to be painted is the following:
total = floor(N/A) + floor(N/B)

But it is not hard to notice that some tiles may be counted more than once, as shows the image below.

total = floor(6/2) + floor(6/3)
total = 3 + 2 = 5
However, we can count only 4 painted tiles.

There goes the Inclusion-Exclusion theory: we have two sets, and when we add them we are adding repeated elements. To fix it, we must subtract the intersection of such sets.
Notice, a number is multiple of A and B if and only if is multiple by LCM(A, B) (google least common multiple).

Solution: A + B - (A U B)

At the transition between the time t and the time t+1, you have two choices: move or stay where you are. The problem is to decide which of these choices is going to raise the maximum number of apples.

There is no exit unless to test all the options, and nothing better to do it than the reuse of information: Dynamic Programming.

If this concept is new to you, it may be a good opportunity to learn it. Dynamic Programming is about reusing informations that, during the algorithm, may be calculated more than once.

The first step is to divide the problem in states. Imagine that you are at the position [x, y] at time t. This is a state: [x, y, t].

Once you find out what is the best way of collecting apples from this state, save such information and reuse it every time that during the algorithm you find yourself at the same state.

The solution is: Total(x, y, t) = max(Total(new_x, new_y, t+1), for all [new_x, new_y] that correspond to a square adjacent to [x, y], or [x, y] itself).
Add 1 every time that there is an apple at the position [x, y], at time t.

For more details, search for Dynamic Programming.

EDIT:

The solution I mentioned was the one I thought when I wrote the exercise, but talking with some programmers I found out a second way of solving this exercise, with a lesser complexity.

Be x, y and t the information about a first apple, and nx, ny and nt the information about a second apple, it is possible to get from [x, y] to the position [nx, ny] in nt-t seconds? (Think about a mathematical formula).
If yes, we can capture both apples. If not, we can capture one of them, but not both.

Making use of Dynamic Programming, we can reuse informations and test all possibilities.

This exercise divides into two problems: finding out the shortest path between each of the pieces, considering the particularity of the horse jump; and finding the best capture sequence to be followed.

The shortest path can be solved using a Breadth First Search (BFS) from each of the pieces to the others. At the end, we will have a graph with K+1 vertices, all interconnected with edges that correspond to the shortests paths between them.

The second part involves, as in the previous exercise, the checking of all the possible paths.

We can start capturing any of the K pawns. After, we can capture any of the K-1 remaining pawns. After, K-2 pawns. Until we have captured all the pawns and we have to return to the initial position.
At the end we will have the following complexity: K! (K * K-1 * ... * 2 * 1).

As the maximum value of K is 15, we have a complexity of 15!, which is way too high.

To decrease this we can use a technique known as bitmask. It is a way of translating which pawns you have already captured to an integer number, in other words, a state.
Such state can be used to reuse information, and then we have our complexity decreased.

For more details, search for Bitmask, Dynamic Programming and Hamiltonian Cycle.

Here we have a variation of the previous exercise. We have to capture turtles this time, but they are always moving, and it is almost impossible to reuse information here. Fortunately, the number of turtles is small, and 3! is not a scary complexity.

See, we can capture the turtles in the following orders: 1->2->3;   1->3->2;   2->1->3;   2->3->1;   3->1->2;   3->2->1. At total 6 orders (3!).

The challenge is at finding how many seconds it takes to reach a moving target. There are at least two solutions: simulate the race, and see how many seconds it takes; try some values and use the concept of binary search to add precision to the choice.

For the second given soluction, here is a definition given by the programmer Ricardo Oliveira:
Be t the minimum necessary time to reach a turtle initially at (Tx, Ty) (and, after t seconds, at (Tx+t, Ty) (or (Tx, Ty+t), according to the direction)) from the position (Rx, Ry).
Be t' > t. It is valid to notice that, as Rafael can move faster than the turtle, Rafael can get to (Tx+t', Ty) *before* the turtle and wait for her at this position. Furthermore, if t' < t, the turtle will get to (Tx+t', Ty) before Rafael, and therefore not be captured.
So, the value of t is the minimum value of t' such that Rafael can get to the position (Tx+t', Ty) before (or at the same time) as the turtle. Soon, it is possible to find such value with a binary search: for each analysed number t', checks if Rafael can get before or at the same time at (Tx+t', Ty) as the turtle, and the interval is refreshed accordingly.
Obviously, the turtle takes t' seconds to go from (Tx, Ty) to (Tx+t', Ty). The problem falls to defining the amount of required time so Rafael can go from (Rx, Ry) to (Tx+t', Ty). One analysis of Rafael's movements, and mainly the fact that he takes 2 seconds to go from (Rx, Ry) to, for example, (Rx+2, Ry+2), *independently of the path he follows*, allows us to conclude that Rafael can always take a greedy path, that takes min(dx, dy) + ceil(abs(dx-dy)/2) seconds, where dx = (Tx+t' - Rx) and dy = (Ty - Ry).

So that is it. If you had some different solution and wants to share, or if you still have some question, leave your commentary below, or send me an e-mail.

I hope you have enjoyed the contest. See you later.

#### 11 comentários:

1. I just wanted to say thanks for having translated it to english, it was really helpful to me to understand some tasks that I couldn't solved by my self :)

1. No problems :)
Good luck!

2. Thank you very much :))

1. 3. can you please provide a working code of Maçãs . Not able to get it. thanks :)

1. Here's what I did: https://github.com/crbonilha/codes/blob/master/macas.cpp
If you have troubles, send me an e-mail and I will explain the code for you.

2. 4. In the Apple task, I think you should add this test case:
5 5 3
1 5 1
5 1 2
5 5 3
1 1
Or something like that, because you aren't controling when Rafael can't get any apple (I tell you this, because my code gives -1 as answer to this test case, what is obviously wrong, but got AC)

May be I'm getting some mistake, I don't konw...

Ps: thank you for the contest and the translation :)

1. You are right, I checked and there are no cases where the answer is 0. If I remember, later I am going to send them an update. Thanks for the advice :)

2. You're welcome! I've never done a contest yet, but I imagine that must be really hard!

I want to ask you about the task Horse. That problem is a TSP (Travelling Salesman Problem) for what I see. I've looked up a little bit on the internet, but I haven't found anything to make it less than O(N!). I've found some places said that with DP you can reduced it to O(N^2*2^N), but there doesn't say how, and still O(16^2*2^16) is a very large number (16777216, aprox 7*10^7).
How did you solved that part? It is a TSP, isn't it? Or am I wrong?

3. Yes, it is the TSP, and the expected complexity for this problem is O(N^2*2^N) (N is actually 15, instead of 16, because the horse is just the start and end of the cycle).
Well, I don't know how available the algorithm is at google, because I learned this on a book (Competitive Programming). The idea is to use bitwise operations (heard about?) to transform the pawns you have captured in a integer state, and this state you put on your DP, reusing them later.
If you want I can send you my code, and maybe you can understand the idea, but first try studying bitwise operations, or more specifically, bitmask.