Diskuze: Algoritmy - Nejefektivnější řešení

PHP PHP Algoritmy - Nejefektivnější řešení American English version English version

Avatar
pluto-ppes
Člen
Avatar
pluto-ppes:

Ahoj,
rád bych se poradil a prodiskutoval s ostatními jaká by byla nejefektivnější cesta k řešení následujícího zadání níže. Přikládám i vlastní řešení, ať je nad čím diskutovat ;-) Bylo to zadání do jedné soutěže, tak ho možná taky někdo řešil, bohužel se neuvádělo výtězné řešení, ani hodnocení odeslaného kódu.

You want to spend your next vacation in a foreign country. In the summer you are free for N consecutive days. You have consulted Travel Agency and learned that they are offering a trip to some interesting location in the country every day. For simplicity, each location is identified by a number from 0 to N − 1. Trips are described in a non-empty zero-indexed array A: for each K (0 ≤ K < N), A[K] is the identifier of a location which is the destination of a trip offered on day K. Travel Agency does not have to offer trips to all locations, and can offer more than one trip to some locations.

You want to go on a trip every day during your vacation. Moreover, you want to visit all locations offered by Travel Agency. You may visit the same location more than once, but you want to minimize duplicate visits. The goal is to find the shortest vacation (a range of consecutive days) that will allow you to visit all the locations offered by Travel Agency.

For example, consider array A such that:
A[0] = 7
A[1] = 3
A[2] = 7
A[3] = 3
A[4] = 1
A[5] = 3
A[6] = 4
A[7] = 1

Travel Agency offers trips to four different locations (identified by numbers 1, 3, 4 and 7). The shortest vacation starting on day 0 that allows you to visit all these locations ends on day 6 (thus is seven days long). However, a shorter vacation of five days (starting on day 2 and ending on day 6) also permits you to visit all locations. On every vacation shorter than five days, you will have to miss at least one location.

Write a function:

int solution(int A[], int N);

that, given a non-empty zero-indexed array A consisting of N integers, returns the length of the shortest vacation that allows you to visit all the offered locations.

For example, given array A shown above, the function should return 5, as explained above.

Assume that:

N is an integer within the range [1..100,000];
each element of array A is an integer within the range [0..N − 1].

Complexity:

expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Vlasní řešení:

function solution($A) {
    // write your code in PHP5.5
    $places = array_unique($A);
    $values = array_unique($A);
    $last_position = array();
    for($i = 0;$i < count($A);$i++){
        $key = array_keys($values,$A[$i]);
        $last_position[$key[0]] = $i;
        if(!empty($places)){
            unset($places[$key[0]]);

            if(empty($places)){
                return max($last_position) - min($last_position)+1;
            }
        }
    }

}
 
Odpovědět 21. ledna 14:13
Avatar
coells
Redaktor
Avatar
Odpovídá na pluto-ppes
coells:

Máš tam tři problémy:

  1. když ke vstupnímu poli z příkladu připojím 7, měl bys vrátit 4, ale vracíš 5, takže řešení není správně
  2. array_unique nesplňuje zadání O(N), protože třídí, tyhle funkce nesmíš používat
  3. PHP není dobré na algoritmické úlohy, funkce jako array_unique a array_keys schovávají reálnou složitost algoritmu
 
Nahoru Odpovědět 22. ledna 10:30
Avatar
pluto-ppes
Člen
Avatar
Odpovídá na coells
pluto-ppes:

Díky za odpověď. Hned jsem zase o něco chytřejší :-)

 
Nahoru Odpovědět 25. ledna 21:32
Avatar
Ondrca
Redaktor
Avatar
Odpovídá na pluto-ppes
Ondrca:

To je to zadání z Alza developer challenge, že jo? :D

Nahoru Odpovědět 25. ledna 22:02
Zase jsem o něco chytřejší
Avatar
Drahomír Hanák
Tým ITnetwork
Avatar
Odpovídá na pluto-ppes
Drahomír Hanák:

Pro řešení v lineárním čase jde třeba využít fakt, že hodnoty jsou celá čísla od 0 do N - 1 takže můžeš mít pomocné pole indexované těmi hodnotami. S tím pak můžeš zjistit počet výskytů jednotlivých hodnot v dané sekvenci v konstantním čase, takže by mělo stačit projít jednou to pole a posouvat ukazatel na začátek uvažované sekvence, dokud se hodnota na začátku v sekvenci opakuje. Zkus to ale ověřit (buď najdi protipříklad, nebo dokaž, že tak skutečně narazíš na nejkratší sekvenci, která obsahuje všechny hodnoty alespoň jednou)

 
Nahoru Odpovědět 25. ledna 22:59
Avatar
pluto-ppes
Člen
Avatar
Odpovídá na Ondrca
pluto-ppes:

Jo přesně alza challenge, je to už delší doba od soutěže tak jsem si dovolil to zveřejnit, aby jsme si tu mohli podiskutovat.

 
Nahoru Odpovědět 26. ledna 7:55
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 6 zpráv z 6.