Author: sevenkplus

0103 08SEP Practice Contest

3 Problems

A. Old Magician

Problem:

There are W white balls and B black balls. Once, the magician removes two balls. If the balls are in the same color, he will put back one white ball. Otherwise, he will put back a black ball. He does this until there is only one ball. Given W and B, we are to determine the color of the last ball.

Limits:

0<N≤1000 W+B>0

Small dataset:

0≤W≤1000 0≤B≤1000

Large dataset:

0≤W≤10^9 0≤B≤10^9

Analysis:

Small dataset:

Large dataset:

Consider the 3 types of operations:

(1) Take out two black balls. 

The number of black balls will decrease by 2, and the number of white balls will increase by 1.

(2) Take out two white balls.

The number of white balls will decrease by 1.

(3) Take out one black ball and one white ball.

The number of white balls will decrease by 1.

We can see that during the process, the parity of the number of black balls never changes. So if B is even, the last ball cannot be black. If B is odd, the last ball must be black.

The time complexity is O(1). The space complexity is O(1).

Programs:

Small dataset:

Large dataset:

/08SEP/A.pas

B. Square Fields

Problem:

Given n points in the plane. We are to cover the points with k same-size squares whose edges are parallel to the coordinate axes. Find the minimum size.

Limits:

0≤coordinates<64000 1≤N≤10

Small dataset:

1≤k<n≤7

Large dataset:

1≤k<n≤15

Analysis:

Small dataset:

Using brute-force search is enough.

Large dataset:

As the limits are still small, we can think of state compression dynamic programming. Binary searching the answer M and defining state f[k,S] as whether we can use k same suaqres with length M to cover the points in set S, we can find it easy to do state transition.

The time complexity is O(2^n*n^3*k*log ANS) and the space complexity is O(k*2^n) with rather basic implementation.

Programs:

Small dataset:

Large dataset:

/08SEP/B.pas

Futher idea:

Maybe we can binary search the answer and use greedy or similar algorithms to validate it. It is known that when n≤3, greedy is rather easy.

C. Cycles

Problem:

There is an complete undirected graph A with n nodes. We delete k undirected edges (x,y) from A and get another graph B. Calculate the number of Hamiltonian cycles in B.

Limits:

1≤N≤10 0≤k≤15

Small dataset:

3≤n≤10

Large dataset:

3≤n≤300

Analysis:

Small dataset:

Easily solved with state compression dynamic programming.

Large dataset:

We cannot easily get the number of Hamiltonian cycles that EXCLUDES some edges, but we can get the number of Hmiltonian cycles that INCLUDES some edges and use inclusion–exclusion principle to get the answer.

How to get the number of Hmiltonian cycles that includes some edges? We can construct a graph that contains the edges. If one or more of the nodes has degree larger than 2 then the number is 0. If there are cycles in the graph the number is easy to get. Otherwise the graph is made up of some chains. The number is also not hard to get.

We must output the answer mod 9901, but during the calculation, we must divides 2*n. Note that 9901 is a prime, we can use 1/n≡n^(p-2) (mod p) when p is prime. We can also mod 2*n*p during calculation.

Programs:

Small dataset:

/08SEP/Cs.pas

Large dataset:

/08SEP/Cl.pas