Editorial of MindCoding 2014 Round 4

100 - Phone

Problema se rezolva cu un algoritm de tip backtracking. Pentru a genera in ordine lexicografica toate variantele cerute in enunt, fiecare string dat in primele 10 linii din input va fi, mai intai, sortat crescator. Backtracking-ul apoi se implementeaza in mod clasic, atunci cand am reusit sa generam o solutie de lungime egala cu cea a string-ului model, afisam solutia curenta si continuam cu algoritmul.

250 - Death by Taxes

O prima solutie implica multe ifuri, dar se poate gasi una mai scurta: 
    1 #!/usr/bin/perl -w
    2 use v5.14;
    3 
    4 my @taxes = (10, 15, 25, 28, 33, 35, 39.6);
    5 
    6 my %types; # Hash de la tipuri de persoane la punctele unde se schimba taxa
    7            # Daca valoarea e mai mica decat $types{$type}[$i], taxa e $taxes[$i] / 100.
    8 $types{Single}                      = [9075,  36900, 89350,  186350, 405100, 406750, 500000];
    9 $types{'Married joint filer'}       = [18150, 73800, 148850, 226850, 405100, 457600, 500000];
   10 $types{'Head of household'}         = [12950, 49400, 127550, 206600, 405100, 432200, 500000];
   11 $types{'Married filing separately'} = [9075,  36900, 74425,  113425, 202550, 228800, 500000];
   12 $types{'Surviving spouse'}          = $types{'Married joint filer'};
   13 
   14 my ($type, $amount) = <>;                     # Citim tipul de persoana si valoarea taxabila
   15 chomp $type;                                  # Stergem newline-ul din $type
   16 
   17 for my $i (0 .. $#taxes) {                    # Luam pe rand tax bracket-urile
   18     if ($types{$type}[$i] > $amount) {        # Daca valoarea se incadreaza in acest bracket...
   19         say int ($amount * $taxes[$i] / 100); # ... scriem raspunsul
   20         exit                                  # ... si ne oprim
   21     }
   22 }

500 - Last Vector Standing

Problema a fost propusa in ideea de a fi o buna tema de gandire pentru participanti. Pe de o parte ea avea o solutie destul de simpla ca idee, folosind un algoritm de cuplaj in graf bipartit (care trebuia sa aiba o complexitate cel putin la fel de buna ca Algoritmul Hopcroft-Karp, in cazul limitelor din problema). Pe de alta parte, s-a lasat ca tema concurentilor gasirea unui algoritm de tip greedy corect la aceasta problema.

Solutia folosind cuplaj s-a bazat pe urmatoarea idee: Fiecare numar x are M stari: starea x, starea x-b[1], x-b[2], …, x-b[m]. Dupa o normalizare (cel mai usor se implementa cu un std::map), cuplajul se realiza intre multimea elementelor initiale si multimea elementelor finale, unde elementele finale se comprima, elementele duble fiind eliminate. Asteptam explicatia oricarei solutii greedy corecte (demonstrabil, sau macar intuitiv) pe facebook.

900 - Palarb

Observatia cheie la aceasta problema era aceea ca putem calcula prin intermediul unei parcurgeri DFS valorile hash pentru lanturile 1 -> x, respectiv x -> 1 (unde x este nodul curent din parcurgere), daca acestea corespund, probabilitatea ca cele siruri sa difere este foarte mica, mai ales daca nu calculam o singura valoare hash, 2 sau chiar 3 valori hash diferite. Implementarea efectiva o lasam ca tema cititorilor.
Questions?

Sponsors Gold