XIII Contest Algar Telecom – Editorial

This saturday, 03/29, happenned the XIII Contest Algar Telecom, online in the URI portal.

I collaborated writing four exercises, and I will comment the solution of them in this post. If I solve the others, I may comment them in here as well, but no hurry.

Click in the link below to see the rest of the post.

Detective Watson[link]
There are two very simples ways to solve this exercise.

If you know some sorting method, you just have to sort the values, in a way that you save the original position of them. In the end, just print the original position of the second largest value.

Another way would be to implement a method that searches for the greatest value in an array. Execute this method once, and change the resulting value to -1. In the second time you execute the method, the resulting value will be the answer.

Throwing Balls[link]
To solve this exercise, you need to test all the possible speeds in which you can throw the ball initially.

For each choosen speed, simulate the points in which the ball falls, and if in any moment the ball falls in the position N, the answer is “possivel”.
If the ball never falls in the position N, no matters which speed you throw, then the answer is “impossivel”.

Bank Line[link]
This exercise can be solved in many ways. The most straight-forward is using the concept of Equivalence Classes, in Combinatorial.

Let’s forget for one second the order in which the other people are in the line. Lets represent the line with a sequence of characters, being A André, B Bruno, C Carlos and X any other person.

Given the following orderings, how many are valid?

ABCXX
ACBXX
BACXX
BCAXX
CABXX
CBAXX

Just the first, because André must be behind Bruno, and Bruno must be behind Carlos.

So, independently of the position of the other people, for each 6 combinations, just 1 meets the requirements of the exercise.
Knowing that, the answer can be obtained by the following formula:
N! / 6

Now you just have to take care of the rest of division. Note that N! is divisible by 6, because 6 is part of the factorial, but (N! Mod 10^9+7) may not be divisible by 6.

Because N >= 3, one alternative is to divide by 6 before calculating the rest of the factorial, using the formula: fact[n] = n*fact[n-1].
Resulting in fact[3] = 1, fact[4] = 4, fact[5] = 20, and there it goes.

In case you pre-compute the factorials Mod 10^9+7, instead of dividing by 6 it’s possible to multiply by the modular inverse of 6 (namely, 833333341), that the effect is the same. Search about modular inverse for more details.

Board with Prizes – [link]
This exercise can be solved using the concept of Dynamic Programming. You just have to find out which patterns are compatible with which patterns, and the relationship between the sub-problems can be defined.

The first step, then, is to find out which patterns are compatible. A pattern m is compatible with a pattern k if, and  only if, for each position i of the size of the patterns, m[i] != k[i] || m[i] == “.” || k[i] == “.”.

After that we can apply the concept of dynamic programming to take advantage of the sub-problems that repeat itselves.

Be dp[n][m] the maximum sum that is possible to obtain using the patting m in the row n:
dp[n][m] = max(dp[n+1][k]) + sum(n, m),
for each pattern k that is compatible with m,
and where sum(n, m) results in the value obtained after applying the pattern m in the row n.

Note that the exercise asks “the maximum amount that is possible to achieve”. That doesn’t say that the value can’t be negative.

 

Any doubt, critic or suggestion, just leave a comment below.

I hope you have enjoyed the exercises, and see you later.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.