sábado, 22 de fevereiro de 2014

Contest Delta - Editorial (English Version)

Hey, today occurred tha second open contest at URI, the Contest Delta, where I wrote 5 from the 13 problems available at the contest. I thank Ricardo Oliveira for reviewing my problems. The other problems were written by Neilor Tonin, Lucas Negri, Márcio Oshiro and Gabriel Dalalio.

[Se você fala Português, venha aqui:]
http://crbonilha.blogspot.com/2014/02/contest-delta-editorial.html

Congratulations to the winners of the contest:
1st place: Fernando Fonseca
2nd place: Igor Wolff
3rd place: Márcio Barbosa

The winners got the following shirt:
https://www.dropbox.com/s/t973nyp3cl98khz/1901876_621867837882912_1664611302_n.png
Cool, no?

I wrote less than half of the problems in this contest, so my editorial will be incomplete for an undetermined time. After the contest ends, I will try to make the other problems, and then I will share my solution here, but I don't know how long it is going to take.
Click at the link below to see the editorial.


The Guilty - [link]
This exercise is quite simple: a student would always say another's student number, or his own number. To find out who will end up turning himself, it is enough to follow the given tips starting by the K-th student, until some student turns himself.

Here is the Pseudocode:
while n[k] != k
      k = n[k];
print k;
Linear Parking Lot - [link]
Doesn't the parking lot remember any particular data structure? What about stack? It is only possible to park the car at the top of the stack, and to remove the car that is at the top of the stack.

To solve the exercise, it is enough to simulate the order at which the cars enter and leave the parking lot, verifying if the stack rules are respected.
One solution would be to fill an arrive array with the index i of the car that arrives at time t, in other words, arrive[t] = i. In a similar way, fill a leave array. If there is no car that arrives and/or leaves at the time t, arrive[t] = leave[t] = 0.

The pseudocode would look like this:
for i from 1 until greatest_t
     if leave[i] != 0
          if !stack.empty AND stack.top = leave[i]
               stack.pop;
          else
               print "Nao";
               end loop;
     if arrive[i] != 0
          if stack.size < k
               stack.push(arrive[i]);
          else
               print "Nao";
               end loop;

Gruntz - [link]
There are two ways to approach this problem, and more two to implement.
- One of them is to position the character in all of the borders of the map and verify if he can get to the middle.
- The other is to position the character in the middle of map, and verify if he can go to any of the borders (he will walk at the opposite direction of the arrows).

Once chosen one of the two approaches, there are two ways to implement:
- Using a depth-first-search with backtracking, in other words, walking at the direction the arrows point, or walking at the opposite direction the arrows point and spending a value of K. If K is equal to 0, it is only possible to walk at the pre-defined directions. If you ge to the middle (or the borders, depending on your previous choice), then the answer is "Sim".
A piece of the code: https://github.com/crbonilha/codes/blob/master/contest_delta/gruntz.cpp

- It is possible to create a graph where the edges have weight 0 (when they follow the arrows flow) or weight 1 (when they follow the opposite arrows flow). With this graph, it is enough to find the minimum path between the border and the middle (or vice-versa), and verify if this path has cost <= K. For such, the Dijkstra code is a nice choice.
A piece of the code: [soon]

Guilds - [link]
This exercise requires an efficient implemention to:
- Find which Set a player A is in.
- Unite two Sets.
- Find out how many points a Set has.

The first two operations are classic from a data structure called Disjoint-set. The third operation is easily added once the other two are implemented.
For more details, you can follow this link:
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=disjointDataStructure

To find out if Rafael was in the guild that won a battle, first you verify if he was at one of the guilds that were fighting, and then verify if his guild won. Here is a pseudocode:
guild_a = find(A);
guild_b = find(B); 
if guild_a = find(1) AND guild_a.points > guild_b.points
     counter++;
else if guild_b = find(1) AND guild_b.points > guild_a.points
     counter++; 
Abbreviations - [link]
To solve this exercise it is enough to have some experience with strings manipulation, such as words splitting, and make use of a good data structure to save all the words and the number of times each of them appears at the text.

With the Map structure it is possible to manage all the words that appears at the text. After you find all the words with more than two characters, it is possible to fill a Vector, along with the number of times the word appear and the number of saved characters.

With this Vector filled separately for each initial letter, it is possible to sort it according to the number of saved characters, and the one that has the greater value will be printed at the end of the algorithm.

The greatest challenge is at the implementation, that can be tiring and/or tricky, taking some time from the contest. Exercises like this are better availed if saved to the end of the contest, when all the other exercises are done OR when you don't know how to solve the other exercises (Just my opinion).

EDIT: There will have no test cases where two different words with the same initial letter would result in the same amount of saved characteres. I assured this didn't happen, but I forgot to make it clear at the problem description.

Screws and Nuts - [link]
There are more than one way to solve this problem, and I am going to describe two.

1- For each given interval, add all the values that belong to that interval to an array. After that, sort the array, and make a loop that finds the first and the last position where the Num value appears (one alternative would be to use binary search here).

2- Because the values of each interval are always between 1 and 100, it is possible to maintain an array count that describes how many times each value i appears. After that, we can find out how many values are before Num just by adding thet count array values from 1 to Num-1, in linear time, and find out if Num appeared at least one time in constant time, verifying if count[Num] == 0.

Stack Game - [link]
This exercise can be solved testing all the possible allowed card removes, until at one of them the stacks are finally empty.

Implement a recursive function that has a base case that all the three stacks are empty, and that calls itself recursively otherwise, indicating which cards were removed.
It is possible to remove cards in 7 different ways: A,  B,  C,  A and B,  A and C,  B and C,  A and B and C.

Be 0 the position at the top of the stack initially, and N-1 the position of the last card at the stack, the recursive function would be like this:
https://github.com/crbonilha/codes/blob/master/contest_delta/jogo_das_pilhas.cpp

Unite this to a way to prevent that the same state is called million of times.

Max, the Mad - [link]
The search this exercise presents may be a little differente from the usual. Not only you need to get from a vertex A to a vertex B, but you need to buy as little gasoline as possible.

Leave to buy gas only when you need may be more expensive than buying it previously, or vice-versa. But this kind of situation is hard to forecast.

Note now that the limits are very small. There are at most 10 cities and 20 roads. If it is hard to think about an optimal strategy, maybe testing all the possibilities is the solution.

Solution: for each city, go to all the adjacent cities, buying all the possible amount of gasoline that is possible (between 0 and limit-tank, inclusive), and see which of the alternatives gives you the best amount of saved money.

Here is a piece of code to exemplify:
https://github.com/crbonilha/codes/blob/master/contest_delta/max_o_louco.cpp

Transporting Snacks - [link]
The challenge here depends on the way you approach to the problem. I will explain a little bit of how I interpreted, that would be to calculate the number of trips between each adjacent position, and try to generalize this value for more than one adjacent position.

Let's say that he has 15 snacks to be transported, and he can carry 10 stacks per trip. The final distance doesn't matter for now. Be A the initial point, and B a point 100 meters ahead of A.
There are initially 15 snacks at point A, and 0 at point B. Let's say he is going to carry 10 snacks to the point B. Because he eats one snack after each 100 meters, only 9 snacks will get to point B.
We have now 5 snacks at point A, and 9 at point B. Let's say that he wants to come back to point A to get the remaining snacks. For that he takes one of the snacks with him so he can eat after the 100 meters trip, gets the 5 remaining snacks there, and comes back to point B, eating one more snack.
We have now 12 snacks at point B, and 0 at point A.

Notice now that the amount of necessary eaten snacks to carry all the snacks between two adjacent points is not so hard to forecast. To take L snacks, how many trips is it going to be necessary? And for each trip, how many snacks are eaten?
Tip: trips = ceil(L/C);
eaten_snacks = ?

All would be fine we could apply this D times, but D may be a very large number.
The second stage is to count what is the distance in what the number of trips is the same, decreasing the number of iterations in D.


More exercises may be added here soon.

Any doubt, suggestion, or correction?
Send me and e-mail, or leave a comment below.

See you later :)

5 comentários:

  1. Please add the editorials for the remaining questions also...( especially the fib(fib(n)) :) )

    ResponderExcluir
    Respostas
    1. Haha sorry the delay, I am a bit busy these days, but I will do what I can.

      Excluir
    2. just want an AC code of fib(fib(n)) :)

      Excluir
    3. for now, here a portuguese explanation of the other exercises:
      http://crbonilha.blogspot.com.br/2014/02/contest-delta-editorial-continuacao.html

      try using google translate.

      Excluir
    4. AC :)
      very elegant problem .... thanku

      Excluir