On Mon, 25 Mar 2002 at 12:23:43 -0800, resi dencia wrote:
>
> Hmm.. very interesting.. each university has one team, each time has 3 people, total
>5 hours of programming. Languages C, C++, Java and Pascal are allowed to use.
> So, here is chance to prove either you are smarter than top college
> students, or Perl is a better programming language!:)
The latter...
> Give yourself 15 hours, solve more than 6 questions! (SJTU, MIT, UW,
> Tsinghua, Stanford solved 6 of 9 questions)
It's not as simple as that, of course - they only had one computer
between three people. Makes it a more subtle organisational problem. But
as an experiment, I solved the first problem. My solution produces the
right answer for the meagre and poorly-chosen test case (deliberately
poorly-chosen? hmm...) but I haven't checked in detail its solutions to
more complex setups.
The attached file (solution to problem A, "Balloons in a Box")
represents 72 minutes of effort on my part, starting from a familiar
environment. Not NT :-), but I did use exactly the version of text
editor that was available.
Students of perl style will find much to amuse them. I see that
some subs have prototypes, and some not. The code which wound up in
testball was inline to start with, until I thought about how to iterate
over all permutations. It became recursion, so we now have two instances
of @b. No time to fix it, of course. No time to fix anything.
I estimate I wasted about 10 minutes chasing stupid coding blunders,
mostly to do with indecisiveness about whether I was using arrays or
ref-arrays. I forgot to put "-w" on at the outset, which would have
saved about half of that time.
I had looked at the problems ahead of time, but didn't read the rules
closely or conciously think about the problem until I started. On
reading the others, some of them are noticably more difficult than the
balloons problem.
I now see that my script doesn't "Place a blank line after each test
case", so that's a 20 minute penalty :-(
Ian
#! /usr/local/bin/perl -w
# Subs
$pi = 2 * atan2(1,0);
sub min{
my $min = shift;
while(@_) { $min = $_[0] if $min > $_[0]; shift }
$min;
}
sub dist($$){
my($x1,$y1,$z1,$r1)=@{$_[0]};
my($x2,$y2,$z2,$r2)=@{$_[1]};
sqrt( ($x1-$x2)**2 + ($y1-$y2)**2 + ($z1-$z2)**2 ) - $r2;
}
sub towall {
my $b = $_[0];
min map{ (abs( $box1->[$_] - $b->[$_] ), abs( $box2->[$_] - $b->[$_] ) ) } 0..2;
}
sub testball
{
my @b = @_;
# Blow up balloons
for $ball (0..$#b) {
my $b = $b[$ball];
my $mindist = min towall($b[$ball]),
map { $ball==$_ ? () : dist( $b[$ball], $b[$_] ) } 0..$#b;
$b[$ball][3] = $mindist;
}
# Compute enclosure
my $enclosure = 0;
$enclosure += ($_->[3])**3*4*$pi/3 for @b;
#printf "%.1f ", $enclosure;
# Test for optimum ordering
$max_enclosed = $enclosure if $enclosure > $max_enclosed;
# We don't need the actual ordering, but remember it anyway:
# @best_order = @b;
# Deflate balloons
$_->[3]=0 for @b;
}
# Recursive random sort
sub recurse($$);
sub recurse($$) {
my( $pool, $filled ) = @_;
return testball(@$filled) if @$pool == 0;
for (0..$#$pool) {
my @p = @$pool;
my $f = splice @p,$_,1;
recurse( [@p], [@$filled,$f] );
}
}
# Parse
$testcase=1;
while( $count = <> )
{
last if $count == 0;
$box1=[ split' ', <> ];
$box2=[ split' ', <> ];
@b=();
push @b,[(split ' ',<>),0] while $count-- > 0;
$max_enclosed = 0;
# Iterate over every order of balloons
recurse(\@b, []);
# results
$boxvol = 1; $boxvol *= abs($box1->[$_]-$box2->[$_]) for 0..2;
$not_enc = int( 0.5 + $boxvol - $max_enclosed );
print "Box $testcase: $not_enc\n";
$testcase++;
}
