ALP Laborator 4
Algoritmi de sortare
Probleme L3 - The Game!
Exemplu:
1 4 19 14 42 0 34 23
46 7 x 1 2 3 5
8 numere (n), 7 (n-1) miscari totale.
Primul jucator face 4 miscari (n-1)/2 +1, al doilea - 3 (n-1)/2
Probleme L3 - The Game!
Daca lista ar fi sortata:
0 1 4 14 19 23 34 42
246 x 7 5 3 1
Si daca incepem indexarea de la 1:
Jucatorul 1 ar putea face numarul minim sa fie cel de pe pozitia (n-1)/ 2+1 (4) DE LA CAPAT,
Solutia fiind urmatorul numar DE LA CAPAT, adica numarul de pe pozitia (n-1)/ 2+ 2 , adica pozitia 5 DE LA CAPAT.
Jucatorul 2 ar putea face numarul maxim sa fie cel de pe pozitia (n-1)/ 2 , adica 3
Solutia ar fi numarul de pe pozitia (n-1)/2 + 1, adica pozitia 4 DE LA INCEPUT.
Pozitia 5 de la capat = Pozitia 4 de la inceput [14]
Solutia este pentru 1-indexed. Majoritarea limbajelor de programare sunt 0-indexed.
Probleme L3 - The Game!
Exemplu:
1 4 19 14 42 0 34
46 5 x 1 2 3
7 numere (n), 6 (n-1) mutari totale. Primul jucator face 3 (n-1)/2 miscari, al doilea -
trei. (n-1)/2
Probleme L3 - The Game!
Daca lista ar fi sortata:
0 1 4 14 19 34 42
246 x 5 3 1
Si daca incepem indexarea de la 1:
Jucatorul 1 ar putea face numarul minim sa fie cel de pe pozitia (n-1)/ 2 (3) DE LA CAPAT,
Solutia fiind urmatorul numar DE LA CAPAT, adica numarul de pe pozitia (n-1)/ 2+ 1 , adica pozitia 4 DE LA CAPAT.
Jucatorul 2 ar putea face numarul maxim sa fie cel de pe pozitia (n-1)/ 2 , adica 3
Solutia ar fi numarul de pe pozitia (n-1)/2 + 1, adica pozitia 4 DE LA INCEPUT.
Pozitia 4 de la capat = Pozitia 4 de la inceput = [14]
Solutia este pentru 1-indexed. Majoritarea limbajelor de programare sunt 0-indexed.
Probleme L3 - Kill the enemy
Cea mai optima solutie ar fi sa folosim alternat doua cele mai mari arme.
Fie i cea mai mare arma si j a doua cea mai mare arma.
In primul caz avem 7 (i) si 3(j)
Daca viata este 1, 2 … 7 ar trebui sa atacam cu o singura arma - [], 7 ⇔ 1 data
Daca viata ar fi 8, 9 sau 10 ar trebui sa atacam cu ambele arme. [7, 3], ⇔ 2 ori.
Daca viata ar fi 11, 12 … 17 ar trebui sa atacam cu [7,3],7 ⇔ 3 ori.
Daca viata ar vi 18, 19 sau 20 ar trebui sa atacam de [7, 3] ,[7 ,3] ⇔ 4 ori
Daca viata ar fi 21, 22 … 27 ar trebui sa atacam cu [7,3],[7,3],7, ⇔ 5 ori.
Daca viata ar vi 28, 29 sau 30 ar trebui sa atacam de [7, 3] ,[7 ,3], [7,3] ⇔ 6 ori
Probleme L3 - Kill the enemy
Ca regula generala, observam ca atacam de exact 2 * H / (i+j) ori,
Daca H se imparte exact la (i+j) 10 ( ⇔ 2), 20 ( ⇔ 4), 30 ( ⇔ 6).
Daca impartirea are un rest mai adaugam 1 sau 2 atacuri in functie de cata viata
ramane:
Daca mai ramane <= i viata, mai atacam o data dupa, deci 2 * H / (i+j)+ 1
Altfel mai atacam de doua ori dupa 2 * H / (i+j), deci 2 * H / (i+j) + 2
Probleme L3 - Barrels
Solutia ar fi sa luam k+1 cele mai mari butoaie si sa turnam toata apa in unul din
ele.
Ex:
Barrels = 4 5 6 7
K=1
Deci luam butoaiele 6 si 7, si dintr-o miscare mutam din 6 in 7 sau invers.
Practic, solutia ar fi suma a k+1 cele mai mari butoaie.
Cautare secventiala
Item = 16
0 1 2 3 4 5
42 8 4 16 23 15
=16? 0 1 2 3 4 5
42 8 4 16 23 15
=16? 0 1 2 3 4 5
42 8 4 16 23 15
0 1 2 3 4 5
=16?
42 8 4 16 23 15
=16?
3
Cautare secventiala multipla
Item = 16
0 1 2 3 4 5 6
42 8 4 16 23 15 16
=16? 0 1 2 3 4 5 6
42 8 4 16 23 15 16
0 1 2 3 4 5 6
=16?
42 8 4 16 23 15 16
0 1 2 3 4 5 6
=16?
42 8 4 16 23 15 16
=16?
[3]
Cautare secventiala multipla
0 1 2 3 4 5 6
42 8 4 16 23 15 16
=16? 0 1 2 3 4 5 6
42 8 4 16 23 15 16
=16?
0 1 2 3 4 5 6
42 8 4 16 23 15 16
=16?
[3, 6]
Cautare secventiala in liste ordonate
Item = 15
0 1 2 3 4 5
4 8 15 16 23 42
=15?
>15? 0 1 2 3 4 5
4 8 15 16 23 42
=15?
0 1 2 3 4 5
>15?
4 8 15 16 23 42
=15?
2
Cautare secventiala in liste ordonate
Item = 13
0 1 2 3 4 5
4 8 15 16 23 42
=13?
>13? 0 1 2 3 4 5
4 8 15 16 23 42
=13?
0 1 2 3 4 5
>13?
4 8 15 16 23 42
=13?
>13?
break; -1
Binary Search
Item = 61
0 1 2 3 4 5 6 7 8
4 8 15 16 23 42 51 61 88
Middle = 0 + (8-0)/2 = 4
0 1 2 3 4 5 6 7 8
4 8 15 16 23 42 51 61 88
= 61?
> ? left = 5
Middle = 5 + (8-5)/2 = 5 + 1 = 6
0 1 2 3 4 5 6 7 8
4 8 15 16 23 42 51 61 88
= 61?
> ? left = 7
Binary Search
Middle = 7 + (8-7)/2 = 7
0 1 2 3 4 5 6 7 8
4 8 15 16 23 42 51 61 88
= 61?
7
Binary Search Tree
17 45
45
9 55
9 55
3 17 53 59
3 17 53 59
20
20
Binary Search Tree
45
9 55
3 17 53 59
20
Probleme L1 - Angry Professor
Solutia 1 O(n). Traversam toata lista de studenti si ii numaram pe cei care au venit
la timp si comparam totalul cu minimul acceptat.
Solutia 2 O(n). Filtram lista cu cei acceptati si numaram totalul elementelor din
acea lista.
Solutia 3. O(n logn). Sortam lista si verificam daca elementul pe indexul [minim
acceptat -1] este mai mare decat 0 (studentul este intarziat)
Probleme L1 - Max Product in Array
Solutia 1 O(n^2). Iteram prin toate elementele de 2 ori si le inmultim pe toate intre
ele, memorand si actualizand cel mai mare numar obtinut.
Solutia 2 O(nlogn). Sortam lista si verificam care dintre produse este mai mare:
index[0] * index[1] sau index[length-1] * index[length-2]
Solutia 3 O (n). Traversam o singura data toata lista si actualizam 4 numere: 2
cele mai mari si 2 cele mai mici. La final returnam produsul cel mai mare dintre 2
cele mai mici sau 2 cele mai mari numere.
Probleme L1 - Pair with given sum
Solutia 1 O(n^2) aka Brute Force. Iteram prin toata lista de 2 ori, adunam
numerele si daca suma este potrivita, afisam perechea.
Solutia 2 O(nlogn). Sortam lista, dupa care iteram si calculam prin ea actualizand
indecsii de traversare.
Solutia 3 O(n). Iteram o singura data prin lista si salvam numerele intr-un dictionar
(Map), verificand daca diferenta dintre suma si iteratorul curent exista in acel
dictionar.
Probleme L1 - DoorsAndKeys
Solutia consta in definirea unor liste “paralele” pentru usi si chei, dupa care in sirul
de caractere de test se va compara indexul pentru fiecare element din cele doua
liste. Daca cel din lista de chei este mai mic decat cel din lista de usi pentru toate
cele trei elemente, afisam “DA”, altfel - “NU”.
Probleme L1 - Not Shading
Exista 4 variante posibile.
Toate elementele sunt W, deci returnam -1.
Elementul este deja B, deci returnam 0.
Coloana sau randul pe care se afla elementul are o valoare B, deci returnam 1.
Coloana si randul nu contin o valoare B, insa o astfel de valoare exista in intreaga
matrice, deci returnam 2.
Another Game
You are playing a very popular computer game. The next level consists of n consecutive locations,
numbered from 1 to n, each of them containing either land or water. It is known that the first and last
locations contain land, and for completing the level you have to move from the first location to the last.
Also, if you become inside a location with water, you will die, so you can only move between locations with
land.
You can jump between adjacent locations for free, as well as no more than once jump from any location
with land i to any location with land i+x, spending x coins (x≥0).
Your task is to spend the minimum possible number of coins to move from the first location to the last one.
Another Game
10101
The only way to move from the first location to the last one is to jump between
them, which will cost 4 coins.
1011
You can jump from the first location to the third for 2 coins, and then jump to the
fourth location for free, so the answer is 2.
Consecutive sum riddle
Tom Marvollo has a riddle for you and if you manage to solve it, he will give you a Butterbeer.
You are given an integer n. You need to find two integers l and r such that −1018≤l<r≤1018 and
l+(l+1)+…+(r−1)+r=n.
0+1=1. => 0, 1
(−1)+0+1+2=2. => -1, 2
Consecutive sum riddle
6
1+2+3=6. => 1,3
100
18+19+20+21+22=100. => 18. 22
25
(−2)+(−1)+0+1+2+3+4+5+6+7=25. => -2, 7
H-index
Jorge is a physicist who has published many research papers and wants to know how
much impact they have had in the academic community. To measure impact, he has
developed a metric, H-index, to score each of his papers based on the number of times it
has been cited by other papers. Specifically, the H-index score of a researcher is the
largest integer H such that the researcher has H papers with at least H citations each.
Jorge has written N papers in his lifetime. The i-th paper has Ci citations. Each paper
was written sequentially in the order provided, and the number of citations that each
paper has will never change. Please help Jorge determine his H-index score after each
paper he wrote.
H-index
3 papers => 5 1 2 (citatations)
After the 1st paper, Jorge's H-index score is 1, since he has 1 paper with at least 1
citation.
After the 2nd paper, Jorge's H-index score is still 1.
After the 3rd paper, Jorge's H-index score is 2, since he has 2 papers with at least
2 citations (the 1st and 3rd papers).
H-index
6 papers => 1 3 3 2 2 15 (citations)
After the 1st paper, Jorge's H-index score is 1, since he has 1 paper with at least 1 citation.
After the 2nd paper, Jorge's H-index score is still 1.
After the 3rd paper, Jorge's H-index score is 2, since he has 2 papers with at least 2 citations (the 2nd and
3rd papers).
After the 4th paper, Jorge's H-index score is still 2.
After the 5th paper, Jorge's H-index score is still 2.
After the 6th paper, Jorge's H-index score is 3, since he has 3 papers with at least 3 citations (the 2nd, 3rd
and 6th papers).
