These are problems I've heard about recently and seem cute.

*Merge arrays*. You are given an array *x* with *m* comparable objects
followed by *n* empty cells. You are also given an array *y* with *n*
comparable objects. Both *x* and *y* are sorted. Your task is to add
to *x* the element of *y* such that *x* remains sorted. You may use only a constant amount of memory. [From TopCoder forums.]

*Election winner*. You are given an array containing votes. A candidate
wins if he has more than half the votes. Your task is to find the winner.
If there is no winner by the previous definition than you can choose
as winner whoever you want. You may use only a constant amount of memory. [From
the 0xDE blog.]

*Handshake party*. You are invited to a party. At the end you ask
each person how meny times they shook hands. You notice that the
response you receive is an odd number for an even number of people.
Why? [Henry. Also in Combinatorics by van Lint.]

*Handshake party, continued*. You then ask each person with how
many other people they shook hands. If no one is handshakeless then
you expect to receive at least two identical answers. Why? [Combinatorics
by van Lint.]

*Sex in New York (Times)*. You are given a bipartite graph. Show
that the sum of the degrees for the left nodes is equal to the sum
of degrees for the right nodes. What is the relation between the average
number of sexual parteners of women and the average number of sexual
parteners of men? [From NYT, via WebDiarios de Motocicleta blog.]

*Graphs at IOI 2007.* Find a maximum weighted matching in an
arbitrary graph knowing that the degree of the vertices is bounded
by a constant. You are supposed to give a nice and simple implementation.
[Via WebDiarios de Motocicleta; I don't know (yet) the `nice' answer.
Here is the general case.]

PS1: Some of these are also on my webpage.

PS2: Did you notice the list of nice blog posts below?

## No comments:

## Post a Comment

Note: (1) You need to have third-party cookies enabled in order to comment on Blogger. (2) Better to copy your comment before hitting publish/preview. Blogger sometimes eats comments on the first try, but the second works. Crazy Blogger.