Skip to main content Link Search Menu Expand Document (external link)
    

Meeting july 2016

• meetings

café Fluctuat Nec Mergitur, July 9th, 2016, 9:00

Advices

To train for the programming contest

  • read many problems, to train quick translation into formal statement with all constraints
  • get to know your classical algorithms
  • know how to implement them, and also how to implement algorithmic easy problems

Hints

Teams

There are n ways to choose the team leader and then \( 2^{n-1} \) to choose the remaining team members among the n-1 other persons. So you have to output \( n\cdot 2^{n-1} \). Use fast exponentiation for that.

Mirror Clock

The main “difficulty” is to print integers with 2 digits. For this use a format string

print("%02d:%02d" % (hours, minutes))                            # Python
printf("%02d:%02d\n", hours, minutes);                           // C
System.out.println(String.format("%02d:%02d", hours, minutes));  // Java

Travel Company

Basically you are given a directed graph, where every arc \( (A_i,B_i) \) has the weight \(I_i-P*E_i\). We need to detect a negative cycle. Use Bellman-Ford or even Floyd-Warshall.

Fun with Strings

Basically you have to solve a linear equation system with two variables and two equations. The coefficients are Fibonacci numbers. In order to compute those numbers in short time use fast exponentiation on the matrix

\[ M = \left( \begin{array}{cc}1&1\\1&0\end{array}\right) \] which gives \( M(a,b) = (a+b,a) \).

Kisu Pari Na 2

Funny text, it starts with unrelated topic, so you cannot see immediately that this is a graph problem.

Given a forest and an integer K we want to know what is the length of the shortest path that can visit K distinct vertices. Clearly each tree forms an independent subproblem. It is not very clear from the examples whether a path can traverse a same vertex several times. But querying the uDebug website tells us that such paths have to be considered as well.

If you think about, for a given tree the first vertex is covered for free, the next ones need a single or two edges. Let P be the longest path in the tree. Its length is called the diameter of the tree. Then if K≤len(P), the answer is just K-1. For every additional vertex two edges are necessary to cover it from P, hence the answer is min(K, len(P)) -1 + 2 max(0, K-len(P)) if K is not more than the number of vertices in the tree, otherwise the answer is ∞.

To answer a query K, simply choose the tree with the largest diameter among all trees of size at least K. This tree can be found using binary search and some preprocessing (sorting).

Pizza cutting

The answer is n(n+1)/2. Simply think of an arrangement of lines such that no lines are parallel and no 3 lines intersect at the same point. Let all intersection points be inside the pizza. When you remove a line among the n lines, then it will merge n+1 pairs of pizza pieces. If you continue removing you reach the claimed bound.

What is the Card?

Boring simulation. But go ahead and code it quickly.

References

Comments

Related posts