Nuputamiseks: Astendamine pinus

Mäletan, kui Ahto Ateena IOI-l pärast võistlust selle ülesande nuputamiseks andis. Minu leitud rekurrentne seos a[i]-de arvutamiseks oli eeltoodud Ahto lahendusest veidi kohmakam, aga see-eest leidsin viisi, kuidas optimaalse lahenduse otsimise asümptootilist ajakulu pisut vähendada. Pannes enda idee Ahto rekurrentsiga kokku, sain nüüd järgmise algoritmi.

const maxn = 1000000;
const leidmata = 'leidmata';
var a : array [1..maxn] of string;
var n, i, j : longint;
begin
   readln(n);
   a[1] := '';
   for i := 2 to n do
      a[i] := leidmata;
   for i := 2 to n do begin
      if (a[i] = leidmata) or (length(a[i]) > 8 + length(a[i - 1])) then
         a[i] := 'DUP ' + a[i - 1] + 'MUL ';
      for j := 2 to i do begin
         if i*j > n then
            break;
         if (a[i*j] = leidmata) or
                 (length(a[i*j]) > length(a[i]) + length(a[j])) then
            a[i*j] := a[i] + a[j];
      end
   end;
   writeln(a[n]);
end.

Põhimõtteliselt on siin Ahto algoritm lihtsalt "tagurpidi" pööratud: me ei hakka järjendit läbi vaatama mitte "ülevalt alla" (iga i jaoks tema tegureid läbi vaadates), vaid "alt üles" (kui saame mingi a[i] väärtuse lõplikult teada, siis uuendame ka i kordsete väärtusi), nagu Eratosthenese sõela puhul. Võit tuleb sellest, et "ülevalt alla" algoritm peab iga i jaoks läbi vaatama hulga arve j, mis ei ole i tegurid. Kui "ülevalt alla" algoritmi ajakulu on n*sqrt(n), siis "alt üles" algoritmi ajakulu on n*log(n).

Tõepoolest, iga i kohta tehakse vähem kui n div i sammu järgmiste a[i]-de uuendamiseks (sest i on teguriks ülimalt n div i arvule vahemikus 1...n), seega selliste sammude arv kokku ei ole suurem kui

n div 2 + n div 3 + n div 4 + ... + n div n < n(1/1 + 1/2 + 1/3 + ... + 1/n).

Sulgudes on harmoonilise rea osasumma, mis teadagi kasvab võrdeliselt n-i logaritmiga (selle nägemiseks võib nt. harmoonilise rea liikmeid lähendada kahe astmetega: 1 + 1/2 + 1/4 + 1/4 + 1/8 + 1/8 + 1/8 + 1/8 + 1/16 + ... < 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + 1/9 + ... < 1/1 + 1/2 + 1/2 + 1/4 + 1/4 + 1/4 + 1/4 + 1/8 + 1/8 + ...). Nii saab ajakulu ka alt hinnata, nii et n*log(n) on täpne asümptootiline hinnang.

Kui nüüd jälle "ülevalt alla" vaatenurgale üle minna, siis selle ajahinnangu tõestamisega tõestasime järgmise tulemuse: arvude 1...N tegurite arvude summa on suurusjärgus N*log(N), s. t. arvul vahemikust 1...N on keskmiselt suurusjärgus log(N) tegurit.

Muidugi n*log(n) ajakulu on endiselt väga suur võrreldes väljundiga, mis on O(log n), nii et võib-olla on olemas kiirem algoritm optimaalse lahenduse leidmiseks.

Järgnev Ruby-jupp leiab lühimad dupmul-jadad, kui sisend ei ületa väärtust 1037.

#### Data acquisition

$n = ARGV[0].to_i

#### Prime management

primep = [true] * ($n + 1)
primep[0 .. 2] = false, false, true
$primes = []

p = 2
while p * p < primep.length do
    if primep[p] then
        $primes.push p
        prod = p + p
        while prod < primep.length do
            primep[prod] = false
            prod += p
        end
    end
    p += 1
end

class Integer
    def each_factor_pair
        $primes.each do |f|
            yield f, self / f if self != f and self % f == 0
            return if f * f >= self
        end
        return
    end
end

#### Dynamic programming

def cache
    return Hash::new{|h,k| h[k] = yield k}
end

shortest_repr = cache do |arg|
    shortest_found = '(' + shortest_repr[arg - 1] + ')'
    arg.each_factor_pair do |f, g|
        candidate = shortest_repr[f] + shortest_repr[g]
        shortest_found = candidate if candidate.length < shortest_found.length
    end
    shortest_found
end

shortest_repr[1] = ''

#### User interface

words = {'(' => 'DUP', ')' => 'MUL'}
puts shortest_repr[$n].split('').map{|c| words[c]}.join(' ')

Mõnevõrra suuremate sisenditega saab majandada, kui enne väljundi genereerimist teha niimoodi:

(1 .. $n).each{|n| shortest_repr[n]}

Aga mis dünaamiline programmeerimine see siis enam on? Pealegi läheb suurte sisendite korral arvutamine aeglaseks:

tsume:tmp dig$ time ruby dupmul.rb 200000
DUP MUL DUP MUL DUP MUL DUP MUL DUP MUL DUP MUL DUP DUP MUL DUP MUL DUP DUP MUL DUP MUL DUP DUP MUL MUL DUP DUP MUL DUP MUL DUP MUL DUP MUL DUP MUL DUP MUL MUL MUL MUL

real    0m16.511s
user    0m16.371s
sys     0m0.074s

Reaalses maailmas võiks veel kaaluda mitmesuguseid ettearvutamise-lähenemisi. Näiteks on võimalik iga dupmul-jada pikkusega N kodeerida N + 1 bitiga; kui me jadad indekseerimise hõlbustamiseks oktabiti-piirini joondame, saame 64 kibibaidi sisse mahutada jadad kuni sisendini 14100. Veel on võimalik tulemuste asemel salvestada rekursiooniotsuseid. Kui me rekursiooniotsusena salvestame väiksema teguri või eriväärtuse 0 dekrementimise tähisena, saab 64 kibibaidi sisse mahutada rekursioonijadad kuni sisendini 65535. (Kuna väiksem tegur ei ületa kunagi ruutjuurt, mahub see 16-bitise sisendi korral 8 biti sisse. 0 ei ole kunagi väiksem tegur.)