[Moscow.pm] Сложить 5000000 чисел

[Andrew Shitov]

> Плохой тесткейс: http://dl.dropbox.com/u/360558/input_big.txt.gz
(распакуется в 14 мег)

Пример какой-то странный. На нем нельзя убедиться, что программа
работает правильно: все пути дают одинаковый результат, и
пооптимизировать для случая со случайными данными не получится. Откуда
этот файл?


Моя вторая попытка (после прямолинейной первой) - начать считать не
сверху, а снизу, отсеивая пути, которые на очередном шаге добавляют в
результат меньше других.

use v5.10;
#use Data::Dumper;
<>;@v=reverse map{[split/\s/]}<>;
$s=$v[0];
for(1..$#v){
    if($q==1){$q++;next}
    if($q==2){$q=0;$s=$v[$_];next}
    #say Dumper($s);
    $c=$v[$_];
    $n=$v[$_+1];
    if(@$c!=@$n){
        #say join',',@$c;
        $m=0;
        for(0..@$c-1){
            if($$s[$_]){$$s[$_]=$$c[$_]+($$s[$_]>$$s[$_+1]?$$s[$_]:$$s[$_+1]);$m=$$s[$_]if$$s[$_]>$m}
        }
        pop@$s;
        @$s=map{$_!=$m?0:$_}@$s
    }else{
        push на r,$$c[0]+($$s[0]>$$s[1]?$$s[0]:$$s[1]);
        $q=1;
        #say '-'x20;
    }
}
say for reverse на r;

На простых тестовых данных вроде работает, хотя я не уверен, что здесь
все правильно и будет работать на других данных, например, если
вставить большое число где-то на краю треугольника. Короче, на свалку.

Третий подход через рекурсию. Даже получается уложиться в 256 байт,
причем не убирая "my". Не очень понятно, правда, как отсеиваются
неверные пути, но работает :-)

for(1..<>){
    @v=();$h=<>;for(1..$h){push на v,[split/\s+/,<>]}
    print path(0,0),"\n";
}
sub path{
    my($x,$y)=@_;
    return 0 if $y==$h;
    my$l=path($x,$y+1);
    my$r=path($x+1,$y+1);
    $v[$y][$x]+($l>$r?$l:$r);
}

Но spoj.pl все равно говорит: "time limit exceeded" :-( Пробовал
избавиться от повторных вычислений:

for(1..<>){
    @p=();@v=();$h=<>;for(1..$h){push на v,[split/\s+/,<>]}
    print p(0,0),"\n";
}
sub p{
    my($x,$y)=@_;
    return $p[$y][$x]if defined $p[$y][$x];
    return 0 if $y==$h;
    my$l=p($x,$y+1);
    my$r=p($x+1,$y+1);
    return $p[$y][$x]=$v[$y][$x]+($l>$r?$l:$r);
}

И здесь "time limit exceeded". Если я правильно понимаю, все равно
приходится пройтись по всем путям? Нет?

-- 
Andrew Shitov
______________________________________________________________________
andy на shitov.ru | http://shitov.ru