Home Page | Web Board | Problems | Standing | Status | Statistics | Award Contest |

**Contest - PKU Local 2007 (POJ Monthly--2007.04.28)**

Start time: 2007-04-28 12:00:00 End time: 2007-04-28 17:00:00

Current System Time: 2024-02-23 18:59:15.187 Contest Status:
Ended

Problem ID |
Title |

3218 Problem A |
Alignments |

3219 Problem B |
Binomial Coefficients |

3220 Problem C |
Context-Free Languages |

3221 Problem D |
Diamond Puzzle |

3222 Problem E |
Edge Pairing |

3223 Problem F |
Football Game |

3224 Problem G |
Go for Lab Cup! |

3225 Problem H |
Help with Intervals |

[Standings] [Status] [Statistics]

Contest Report |

Problem A: The four alignments have to be handled separately. Possibly the most tricky point lies in the calculation of gap widths, which demands some care. Problem B: The parity of Problem C: An efficient solution is based on dynamic programming. We first decide what variables each terminal in the string can be derived from using rules of the form Problem D: The minimum numbers of steps required for every configuration of the puzzle can be precomputed by performing a (backward) breadth-first search from the final configuration and stored in a table. Rest of the job is merely table lookups. Problem E: A simple undirected graph with an even number of edges can always have its edges grouped into incident pairs. Below is a proof by construction. Let Problem F: Let’s first consider the simplified case where In the above figure, a circle through - for any point
*P*on the ray*RQ*, ∠*APB*≤ ∠*AQB*; - ∠
*APB*is a convex function with respect to the position of*P*; - ∠
*APB*reaches its maximum when*P*coincides with*Q*.
These three lemmas allow the employment of the bisection method. And the method also works with the original case where the choice of Additionally, the tangent point Problem G: Intended as the easiest one, this problem requires only a straightforward implementation of its ideas. Problem H: Efficient representation and manipulation of the set |

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator