Re: [SPOILER] Medium QOTW 1 solution

Well, your solution contains the following lines for handling the exceptional 
case of a whole power of 2:

<<<
  if (($n & ($n-1)) == 0) {
    # power of 2 - special-case this
    return mapr {
        my($a) = $_;
	mapr {$a^$_} [0..$n-1]
      } [1..$n-1];
  }
>>>

First of all let me say, that it's a very nice way of finding whether $n is a 
whole power of 2. I did not think of it when I solved the problem for this 
case, back when I was given it in the Technion. 

But otherwise, this part is not needed. You can generate the solution for $n 
== 2 manually, and then use the double_prev_solution() function to generate 
the greater powers based on it.

Changing these lines with:

<<<
  if ($n == 2)
  {
      return [[1, 0]];
  }
>>>

Also yields a correct algorithm.

And, BTW, in order to pass -w or "use warnings", one needs to append the line:

<<<
sub allocate_schedule ($);
>>>

Right before the definition of allocate_schedule.

Otherwise, a very nice solution.

Regards,

	Shlomi Fish


On Monday 17 January 2005 23:47, Daniel Martin wrote:
> Well, it appears that my building a verifier was for naught, since by
> the time I had posted mine a more complete version had been posted by
> the quiz author, but here's a solution approach which I don't think
> has been tried before.
>
> First off, I did as was suggested in the problem and solved the case
> when N is a power of 2 separately - there's a very short solution
> available in that case, that unfortunately does not generalize to
> other N at all.
>
> Then, I tried to attack the problem recursively - if I had a
> tournament sheet for a tournament of N teams, what other size
> tournaments could be constructed?
>
> Well, it turns out that it's fairly easy to construct a tournament for
> 2*N teams: just split the teams into two brackets, have each bracket
> play the tournament of size N among themselves, and then have N days
> in which you match teams from different brackets.  The last N days are
> handled by having team $a in the lower bracket play team $a + $d in
> the upper bracket, for $d in 0..N-1.  (Assuming the teams are renumbered
> within each bracket, and with the appropriate % $whatever thrown into
> the expression)
>
> Now, going from 2*N to 2*N-2 is a bit trickier.  The teams are split
> into two brackets as before, and a ghost team is added to each
> bracket.  (So that each bracket has N teams, including the ghost)
> Then, each bracket plays the tournament of size N, but each team that
> would play the ghost team instead plays the corresponding team in the
> other bracket.  The last N-2 days are then filled as before, except
> that $d is restricted to the range 1..N-2.
>
> Of course, this is all shamed by the simplicity of Zsban Ambrus's
> algorithm, but it was already written, so I'll post it anyway.

---------------------------------------------------------------------
Shlomi Fish      shlomif-ik1l9ssToec+JF/[email protected]
Homepage:        http://www.shlomifish.org/

Knuth is not God! It took him two days to build the Roman Empire.