Problemset 9

[Adrian_Kosowski]

Problemset 9 has come to an end. You are most welcome to post any remarks or questions concerning the problems, as well as short descriptions of your accepted solutions.

[tomek_sof]

The Secret Fellowship of Byteland

I start by sorting all the n^2 distances and then I do binary search on them, trying to find the maximum diameter for which I can find a solution.

Given a maximum distance, I am left with a problem of splitting a graph into k cliques of size at least 2.

I start by putting every node in a separate clique. Then I try joining cliques (if they two are fully connected to each other) until there are only k of them:
- as long as there are singleton clusters, I take one of them (in random order) and connect it to some other cluster (with preference to other singletons)
- otherwise, I just connect cliques randomly

I keep an array of clique connectivity: when two cliques are joined, I can update this array in O(n) time. The whole clique-division algorithm is O(n^2) time. With the binary search: O(n^2 log n).

To improve the results slightly, if the clique-partition heuristic fails I repeat it once again (and for the third time with 30% probability).

[tomek_sof]

Oh well, noone else writes, so I will also explain my not-best solutions:

Enjoying a Multiplayer Game

The "can shoot" relation turned out to be symmetric.

The shortest scenario is always of length 1 - you can just find a maximal (not neccessarily the maximum) matching in the graph and have those pairs of people shoot each other. The rest can shoot whoever they want. The remaining graph after this round will have no edges.

The long scenario: In each step I try to find a small set of people that should die this round. This set must "cover" everybody - so I am looking for a small set cover, where each set covers the neighbors of a vertex.

Start by choosing neighbors of degree-1 vertices - they must be chosen. Then I take guys that are not covered yet, from the smallest degree (resolve ties randomly). For each of them, pick one neighbor to shoot. I ended up picking the neighbor with the smallest number of already chosen neighbors (ties randomly).

Repeat the long scenario algorithm 7 times and choose the longest

[tomek_sof]

The Tall Windmills

I ran a brute-force search for small n and after staring at the resulting sequences, I found a pattern for an optimal solution. I am not totally sure why it is optimal.

In Haskell:

f n =
  let k = n `div` 2 in
  if n==1 then [1]
  else if n==3 then [2,4,1]
  else if even n then take k [k+1,k+n..] ++ take k [1,n..]
  else take k [k+4,k+4+n..] ++ [1] ++ take (k-1) [2*k+4,2*k+4+n..] ++ [k+2]

take k a - take the first k elements from the list
[a,b..] - arithmetic sequence
++ - concatenation

[tomek_sof]

The whole Windmills code (to show how I like composing functions in Haskell):

main = interact main2
main2 input = output where
  nums = tail $ map read $ lines input :: [Int]
  output = unlines $ map (unwords . map show . f) nums
f n =
  let k = n `div` 2 in
  if n==1 then [1]
  else if n==3 then [2,4,1]
  else if even n then take k [k+1,k+n..] ++ take k [1,n..]
  else take k [k+4,k+4+n..] ++ [1] ++ take (k-1) [2*k+4,2*k+4+n..] ++ [k+2]

[PradeepMathesh]

Solving Zebra crossing ?