Solutions for Round 3

Problem 1: Channels against Floods
Problem 2: Choosing the Stones
Problem 3: Numbers


Problem 1: Channels against Floods

We can see that several rivers have a bigger flow and others have a lower flow when entering, compared to the maximum flow admitted on every river. The Ford Fulkerson algorithm for finding out a maximum flow is used as follows:

Tests

The evaluation was done with a program which, for every solution, wrote the message:
      The evaluation of the problem "Channels against Floodings"
      The program 'CHANNELS' of the 'Author' competitor

      Test 1 -> Time 110ms -> O.K. -> Score 3 points
      Test 2 -> Time 110ms -> O.K. -> Score 3 points
      Test 3 -> Time 110ms -> O.K. -> Score 4 points
      Test 4 -> Time 165ms -> O.K. -> Score 4 points
      Test 5 -> Time 110ms -> O.K. -> Score 4 points
      Test 6 -> Time 660ms -> O.K. -> Score 4 points
      Test 7 -> Time 220ms -> O.K. -> Score 4 points
      Test 8 -> Time 110ms -> O.K. -> Score 4 points

      Total Score : 30 points.
Remarks:


Problem 2: Choosing the Stones

There are many beautiful solutions to this problem, based on the Fibonacci representation of the integers. Here are a few results, useful for a better understanding of the solutions.

Definition 1:

Let x be an integer. We define xk xk-1 ... x1, the representation of x in Fibonacci base system in the following way:
  1. xi is in {0, 1} for any i=1, 2, ..., k (we use only figures 0 and 1).
  2. xi+xi+1 < 2, for any i=1, 2, ..., k-1 (a figure of 1 can occur only after a 0).
  3. x = x1*f1 + x2*f2 + ... + xk*fk, where f1 = 1, f2 = 2, fi = fi-1 + fi-2, for any i > 2 (f is the string of the Fibonacci numbers).
Definition 2:

Let (n, m), n < m, be a pair of integers. We say that (n, m) is a distinguished pair if:
  1. the Fibonacci representation of n ends with an even number of 0 figures.
  2. the Fibonacci representation of m can be obtained from the Fibonacci representation of n, adding a final 0.
Examples:

  1. n=1 ("1") , m=2 ("10")
  2. n=3 ("100"), m=5 ("1000")
  3. n=4 ("101"), m=7 ("1010")
Remarks:

  1. Any integer number belongs to a single distinguished pair.
  2. In the string {m-n | (n,m) distinguished pair, n<m} any integer occurs exactly once.
Remark:

If n and m, the numbers of stones from the two heaps, do not represent a distinguished pair, then the first player has a winning strategy (he wins in a single step, or he can bring the game through a single step to a situation where (n, m) is a distinguished pair).

Demonstration:

  1. If n=m or n=0 the first player wins in a single step.
  2. If 0 < n < m, we determine the distinguished pair (n, p) and the distinguished pair (a, b), so that b - a = m - n.
    • If p < m, then the first player should take m-p stones from the second heap, bringing the game to a losing position for the second player (the distinguished pair (n, p)).
    • If p > m, then p - n > b - a = m - n, so the distinguished pair (n, p) is bigger than the distinguished pair (a, b), so p > m, a > n. Therefore, n - a = m - b and player 1 should take n-a stones from both heaps, bringing the game to a losing position for the second player (the distinguished pair (a, b)).
  3. If (n, m) is a distinguished pair, after any move it will not be distinguished anymore.
  4. The best programs of the participants are based on the relations between Fibonacci numbers and phi, the golden section:
    phi = (1 + sqrt( 5 )) / 2 = 1, 6180339887...
    So we can generate the string of the distinguished pairs (an, bn) using the following formulas:
    an = trunc(1 + sqrt (5)) / 2)
    bn = trunc(3 + sqrt (5)) / 2).

    Tests

    Examples of beautiful sources (Pascal and C):

    Solution no. 1 (Pascal)
    Solution no. 2 (C)


    Problem 3: Numbers

    To check the problem, because the interval in which N could exist was very big ([0, 2 000 000 000]), we came out with 20 tests, each of them scoring one point. There were sources that tried to determine the solution (x, y), using looping structures... of course, the time limits have been outrun.
    The solution is based on the simple calculation of x and y, after some mathematical considerations:
          m := trunc ((-1 + sqrt (1+8*n))/2);
          x := n-m*(m+1)/2;
          y := m-n+m*(m+1)/2;
    

    Tests

    Good sources:

    Solution no. 1 (Pascal)
    Solution no. 2 (C)

    Remarks:


    [The problems] [First Round] [Previous Round] [Next Round] [Current Round] [Romāna] [Go Back!]

    Go Back!