November 5, 2009

SRM 452

Match Summary

Round Overview
Discuss this match

Last summer, I (rng_58) became 18. What does it mean? It means I can write problems :)

EggCartons

Problem Details

Used as: Division Two - Level One:

Value250
Submission Rate898 / 946 (94.93%)
Success Rate650 / 898 (72.38%)
High ScoreAleks for 249.37 points (1 mins 25 secs)
Average Score213.46 (for 650 correct submissions)

This problem is pretty straightforward. As the constraints are small, we can try all possible numbers of cartons.

1
2
3
4
5
6
7
8
9
10
11
12
int ans = INF, i, j; // INF is a very big number

for (i = 0; i <= n; i++)
  for (j = 0; j <= n; j++) { // buy i cartons containing 6 eggs and j cartons containing 8 eggs
    int eggs = i * 6 + j * 8; // the total number of eggs
    if (eggs != n) continue;
    int cartons = i + j; // the number of cartons
    ans = min(ans, cartons);
  }

if (ans == INF) return -1; // it's impossible to buy exactly n eggs
return ans; // otherwise, return the answer

We may easily notice that n need to be even, or we may just return -1. Let d=n/2, and we can try by finding min{x+y} that satisfies 3*x+4*y==d, which is 4*(x+y) - x == d, which can be easily written as for (int i=0;;i++) if ((d+i)%4==0) return (d+i)/4.

What’s more, let x1=-1, y1=1, we’ll get 3*x1+4*y1=1, and let x=d*x1, y=d*y1, we’ll get one solution for the equation 3*x+4*y=d, then we simply need to find one non-negative solution by adding ceil((x+1)/4)*4 to x and then minus y by ceil((x+1)/4)*3, which can obtain a solution within O(1) even given huge datasets.

NotTwo

Problem Details

Used as: Division Two - Level Two:

Value500
Submission Rate622 / 946 (65.75%)
Success Rate416 / 622 (66.88%)
High ScoreDD.tt for 491.35 points (3 mins 46 secs)
Average Score329.36 (for 416 correct submissions)

Used as: Division One - Level One:

Value250
Submission Rate565 / 592 (95.44%)
Success Rate435 / 565 (76.99%)
High ScoreEryx for 249.30 points (1 mins 30 secs)
Average Score204.74 (for 435 correct submissions)

First, let’s solve the problem “NotOne”, where the distance of 1 is not allowed. It’s not hard to see that one of the optimal placements looks like the chess board.

1
2
3
4
5
6
7
8
9
*- * - * ...
- * - * -...
*
- * - * ...
- * - * -...
*
- * - * ...
.....
.....

(Or, if you want to prove it strictly, divide the above figure into 13 rectangles of 1*1 or 1*2. Within each of these rectangles you can place at most one stone, so it’s not possible to place more than 13 stones. Similar argument can be made for a board of arbitrary size.)

To solve NotTwo problem, write ‘A’-‘D’ characters to the cells:

1
2
3
4
5
6
7
A B A B A...
  C D C D C...
  A B A B A...
  C D C D C...
  A B A B A...
  .....
  .....

If the distance between two cells is two, those two cells have the same character. So the placements for ‘A’ cells, ‘B’ cells, ‘C’ cells and ‘D’ cells are independent.

The solution therefore is to compute the maximal number of stones for each of sub-problems corresponding to the same character (this subproblem is of type “NotOne”), and return the sum. See Eryx 's fastest solution for implementation.

HamiltonPath

Problem Details

Used as: Division Two - Level Three:

Value1000
Submission Rate119 / 946 (12.58%)
Success Rate34 / 119 (28.57%)
High Scorelxx1991 for 832.33 points (13 mins 19 secs)
Average Score531.11 (for 34 correct submissions)

The set of required edges must be a subset of some hamiltonian path. If there is a node with degree >= 3, or the graph contains cycle, return 0.
(If you are not familiar with graph theory, check this link, for example. You can find cycles using DFS.)

Otherwise, each connected component is either chain or isolated point. If there are C chains and I isolated points, there are (C+I)! ways to order the connected components (the number of their permutations), and 2^C ways to direct chains (each chain can be directed by one of two possible ways), so the answer is (C+I)! * 2^C.

lxx1991’s fastest solution uses different approach. It doesn’t require checking for the existence of cycle and is easier to implement. If there is a node with degree >= 3, return 0. Next, run dfs from all nodes with degree <= 1. If unvisited node remains, return 0.

IOIString

Problem Details

Used as: Division One - Level Two:

Value500
Submission Rate65 / 592 (10.98%)
Success Rate19 / 65 (29.23%)
High ScorePetr for 345.67 points (21 mins 4 secs)
Average Score233.55 (for 19 correct submissions)

The number of IOI Strings can be very large, but the number of non-IOI Strings is around 10,000,000 in worst case. To prove this, let’s find the pattern of non-IOI Strings.

First, if a string contains zero or one ‘I’, it’s clearly non-IOI String.

  • O…O

  • O…OIO…O

When a string contains exactly two 'I’s, and the positions of 'I’s are x-th and y-th (x < y), the string is non-IOI if and only if the parity of x and y are different. (Otherwise, it’s IOI String because x-th character is ‘I’, (x+y)/2-th character is ‘O’, and y-th character is ‘I’). In other words, the distance between two 'I’s in any non-IOI string must be odd.

When a string contains three or more 'I’s, what happens? Consider the following string:
O…OIO…OIO…OIO…OI…

Let positions of first, second, third ‘I’ be a-th, b-th, c-th, respectively. Because of the same reason as in previous case, b-a must be odd, and c-b must be odd too. So c-a is even. If a-th character is ‘I’, (a+c)/2-th character is ‘O’, and c-th character is ‘I’, it’s IOI String. We can avoid it if and only if b-a == c-b. Finally, we proved that the only pattern of non-IOI String that contains two or more 'I’s is:

  • O…OIO…OI…IO…OIO…O

where the distance between two consecutive 'I’s is the same odd number.
How many such strings are there? These strings can be represented using three variables: (starting position, ending position, interval). If the starting position is i-th, and interval is d, there are about (N-i)/d possible ending position, where N is the length of input string. (In this problem, at most 2500.) So the total number of non-IOI Strings is the sum of (N-i)/d for all possible (i,d) pairs. It’s O(N^2logN) because 1/1 + … + 1/N is O(logN).

If you find it, this problem is easy: just check all non-IOI String and substract it from 2^(the number of '?'s). See vlad89’s solution (iterative approach) or Vasyl(alphacom)'s solution (recursive approach) for implementation.

And O(N^2) is also possible (though it’s a little harder). See Petr’s fastest solution for this approach.

IncreasingNumber

Problem Details

Used as: Division One - Level Three:

Value1000
Submission Rate3 / 592 (0.51%)
Success Rate0 / 3 (0.00%)
High Scorenull for null points (NONE)
Average ScoreNo correct submissions

Usually, if you see 1,000,000,000,000,000,000 or something in Dynamic Programming problem, the power of matrix is very useful. But this problem is an exception. Instead, we should notice that Increasing Numbers can be written as

a + 11b + 111c + … (a + b + c + … <= 9)

where a, b, c, … are non-negative integers. And Increasing Numbers of digits digits can be written as

(a + 11b + 111c + …) + 11…(digits 1s)…11 (a + b + c + … <= 8)

where a, b, c, … are non-negative integers. So the task is to count the number of (a, b, c, …) such that

  • a + b + c + … <= 8

  • r = -11…(digits 1s)…11

  • (1 % divisor) * a + (11 % divisor) * b + (111 % divisor) * c + … = r (mod divisor)

And we can rewrite the last equation as

  • (x_0_0 + … + x_0_cnt[0]-1) + (x_1_0 + … + x_1_cnt[1]-1) + … <= 8

  • 0 * (x_0_0 + … + x_0_cnt[0]-1) + 1 * (x_1_0 + … + x_1_cnt[1]-1) + … + (divisor - 1) * (x_divisor_0 + … + x_1_cnt[divisor]-1)= r (mod divisor)

where cnt[i] is the number of i in {(1 % divisor), (11 % divisor), …}.

We can easily compute cnt[i] because the sequence {(1%divisor), (11%divisor), …} has a cycle from some early point (because each next element of the sequence depends only on the value of previous element).

Let’s solve this problem using Dynamic Programming.

Let dp[i][j][k] be the number of solutions of

  • (x_0_0 + … + x_0_cnt[0]-1) + (x_1_0 + … + x_1_cnt[1]-1) + … + (x_i_0 + … + x_i_cnt[i]-1) = k

  • 0 * (x_0_0 + … + x_0_cnt[0]-1) + 1 * (x_1_0 + … + x_1_cnt[1]-1) + … + i * (x_i_0 + … + x_i_cnt[i]-1) = j (mod divisor)

And we use combinatorics. See “Number of combinations with repetition” chapter here.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
long long dp[divisor + 10][divisor + 10][12];

dp[0][0][0] = 1;

for (i = 0; divisor > i; i++)
  for (j = 0; 8 >= j; j++) {
    long long tmp = (The number of ways to choose j things from cnt[i] types of things with repetition)
    for (l = 0; 8 >= l; l++)
      if (8 >= j + l)
        for (k = 0; divisor > k; k++) dp[i + 1][(k + i * j) % divisor][l + j] += dp[i][k][l] * tmp;
  }

long long ans = 0;
for (i = 0; 8 >= i; i++) ans += dp[divisor][r][i];
return ans;

See Jedi_Knight’s solution for detailed implementation. (It’s almost correct).

Group 9
Group 9