Soluţii Urmasii lui Moisil 2017

Solutiile de pe site-ul concursului (ceva mai complet):

Electoral

Lift

Autor: Student Valentin Roşca, Facultatea de Informatică, Universitatea Al. I. Cuza Iaşi

Soluţii – stud. Valentin Rosca, stud. Liana–Ştefania Ţucăr

Presupunem că x este pozitiv.

Calculăm suma s=F1+F2+…+Fk cu număr minim de termeni consecutivi din Şirul lui Fibonacci, astfel încât s≥x şi s-x să fie par.

Cazul 1. Dacă x=s, atunci soluţia este: k ++…+ (k semne de +).
Cazul 2. Dacă x<s, fie y=s-x=2*z (y este număr par, prin construcţia lui s).

Îl scriem pe z ca sumă cu număr minim de termeni consecutivi din şirul lui Fibonacci: z=Fi1+Fi2+…+Fip.
Din relaţia s-x=2*z deducem că x=s-2*z= F1+F2+…+Fk -2*(Fi1+Fi2+…+Fip).
Se obţine astfel o sumă algebrică de termeni consecutivi din Şirul lui Fibonacci. Din această reprezentare a lui s, construim soluţia.
Dacă x este negativ, atunci procedăm în mod similar pentru –x urmărind acelaşi algoritm, dar schimbând la sfârşit semnele (din plus în minus şi invers).

Demonstrăm că suma astfel formată are număr minim de termeni.
Presupunem prin reducere la absurd că există o altă reprezentare a lui x, care să conţină un număr q de termeni din şirul lui Fibonacci, mai mic decât k.
În această ipoteză x=F1+F2+…+Fm – 2*( Fi1+Fi2+…+Fiq) (q≤m)
Rezultă că F1+F2+…+Fm-x este par şi pozitiv, cu m<k, ceea ce este absurd, din modul de construcţie a lui k.

Mostenire2

Autor: Cosmin Mihai TUTUNARU, Univ.Babeş-Bolyai Cluj

În primul rând Fibocel vrea să vă mulţumească pentru ajutorul oferit, iar acum se poate apuca să transforme pădurea moştenită în parcul de distracţii mult dorit.
Se observă că o suprafaţă dreptunghiulară de dimensiune W * H este pădurice dacă:
● min(w, h) > 2
● Pe prima şi pe ultima linie se află doar valori de 1
● Pe prima şi pe ultima coloană se află doar valori de 1
● Suma tuturor valorilor din dreptunghi este diferită de (w-2) * (h-2)

Soluţie 40-50 puncte
Se încearcă toate combinaţiile posibile de a fixa colţul din stânga sus respectiv colţul din dreapta jos şi se verifică
dacă suprafaţa dreptunghiulară este o pădurice sau nu. Pentru a verifica dacă suprafaţa dreptunghiulară este o
pădurice sau nu se pot folosi sume parţiale.
Complexitate: O(N*N*M*M)

Solutie 100 puncte
Este destul de evident că trebuie să încercăm să numărăm mai multe pădurici deodată pentru a putea optimiza
soluţia de mai sus. În acest sens ne fixăm toate combinaţiile posibile pentru linia de sus respectiv linia de jos. Se
observă că putem împărţi coloanele dintre cele două linii fixate în următoarele categorii:
1. Avem doar valori de 1 atât în capete cât şi în interior
2. Avem doar valori de 1 în capete şi cel puţin o valoare de 0 în interior
3. Unul din cele doua capete conţine valoarea 0

Acum trebuie doar să numărăm în timp liniar câte perechi de coloane avem care să respecte următoarele condiţii:
● Fac parte din Categoria 1
● Între ele se regăseşte cel puţin o coloană din Categoria 2
● Între ele nu se regăseşte nicio coloană din Categoria 3
Pentru a identifica din ce categorie face parte o coloană se pot folosi sume parţiale.
Complexitate: O(N*N*M)

Suma6

Soluţii – stud. Cristian Vîntur, stud. Marta-Diana Filimon, stud. Cosmin Pascaru
Rezolvarea se bazează pe algoritmul lui Mo (https://www.hackerearth.com/practice/notes/mos-algorithm/)

Se vor procesa offline query-urile în doi paşi:
1. Se împart query-urile în bucket-uri astfel: din acelaşi bucket vor face parte acele query-uri L R care au [L/sqrt(N)] egal.
2. În cadrul unui bucket se vor sorta crescator query-urile după R.

Vom avea:
● Un indice L_cr reprezentând capătul din stânga al intervalului curent
● Un indice R_cr reprezentând capătul din dreapta al intervalului curent
● Un vector de frecvenţă, notat fr care va reţine frecvenţa valorilor din intervalul curent
● Un număr, notat sol, care reţine numărul de perechi a căror sumă este S.

Cele 4 variabile considerate ne vor ajuta la calcularea răspunsului pentru fiecare query dintr-un bucket.

Pentru răspunsul la query-uri se va proceda astfel:

● Pentru primul query dintr-un bucket vor fi iterate toate valorile din şirul cuprins între L si R si se va calcula fr,
sol, iar L_cr si R_cr vor fi egale si L respectiv R

● Pentru următoarele query-uri dintr-un bucket se va proceda astfel:

  c1. Dacă R > R_cr pentru toate numerele din şirul a ce au indici cuprinsi între R_cr+1 si R vom
actualiza sol şi vectorul fr.
Prin actualizarea lui sol înţelegem: pentru o valoare a[i] se va adăuga la sol numărul de valori egale cu s-a[i] din intervalul curent, valoare calculată cu ajutorul vectorului de frecvenţă.
În cadrul unui bucket vor fi maxim n modificări ale capătului R, pasul 2 de creare garantează acest lucru.

  c2. Dacă L_cr > L pentru toate numerele din şirul a ce au indici cuprinsi între L+1 si L_cr vom actualiza sol şi vectorul fr.
Prin actualizarea lui sol înţelegem: pentru o valoare a[i] se va scade din sol numărul de valori egale cu sa[i] din intervalul curent, valoare calculată cu ajutorul vectorului de frecvenţă.
Structura interna a unui bucket (pasul 1 de creare) garantează că acest pas nu va fi făcut în mai mult de sqrt(N) paşi.

  c3. Dacă L_cr < L se va proceda analog cu cazul R > R_cr.

Se vor reordona query-urile după ordinea apariţiei în fişierul de intrare şi se vor afişa răspunsurile.

Din precizările, făcute anterior, despre numărul de paşi pentru un query rezultă că algoritmul prezentat este de ordinul O(Q*sqrt(N) + N*sqrt(N)).

Game4

Autor: Drd. Paul Diac, Facultatea de Informatică Iaşi, student Liana-Ştefania Ţucăr
Soluţii – drd Paul Diac, student Liana-Ştefania Ţucăr, stud. Cristian Vîntur

Pentru a obtine cele 30 puncte pentru care valorile ai nu depasesc 20 se pot genera toate submultimile posibile asociand fiecarei submultimi starea de castig sau de pierdere.
O stare de pierdere poate duce prin toate mutarile posibile doar in stari de castig pentru adversar. Dintr-o stare de castig se poate efectua cel putin o mutare care duce la o stare de pierdere. O repetitie a unui numar este inutila in analiza jocului, deoarece doua valori ai egale vor ramane egale pe tot parcursul jocului.

Pentru solutii ce obtin mai multe puncte, vom considera cunoscute elementele de teoria jocurilor: jocul NIM si numere Sprague-Grundy. Pentru fiecare factor prim distinct al tuturor valorilor ai vom asocia o gramada in jocul NIM, analiza pentru fiecare factor prim fiind independenta. Vom considera separat exponentii la care apare acest numar prim in toate numele din sir. Si aici doi sau mai multi exponenti cu valori egale se modifica similar, deci putem retine doar multimea exponentilor distincti. Numarul acestora este log(106), maxim 20 pentru cel mai mic numar prim. Putem calcula pentru fiecare submultime de exponenti valoarea mex (minimal-exclusive) asociata (Sprague-Grundy). Aceasta se poate calcula recursiv pentru toate submultimile, aplicand definitia. Daca suma XOR (similar cu NIM), a tuturor valorilor mex asociate submultimilor exponentilor ale fiecarui numar prim este nenula, Alice are strategie de castig. Daca este nula, Bob va castiga.

Pentru a numara numarul de mutari posibile distinctepe care le poate realiza Alice la prima ei mutare (in cazul in care ea are strategie de castig), putem incerca toate valorile posibile pk prin care poate mutaAlice, actualizand de fiecare data sumaxor cu mex-ul multimii eliminate si adaugate si testand egalitatea cu 0. Complexitate O(NlogN).

Pentru a numara mutarile lui Bob in cazul in care el castiga, o posibila solutie este sa consideram toate posibilitatile pentru mutarea lui, si apoi sa testam daca ar fi putut exista o mutare anterioara a lui Alice, care sa produca impreuna cu mutarea fixata pentru Bob efectul de a readuce suma xor la 0. Se trateaza separat doua cazuri: atunci cand Alice foloseste acelasi numar prim ca si Bob, putem itera toate combitatiile celor doi exponenti cu care muta Alice si Bob. Complexitate O(Nlog2).

Daca Alice foloseste alt numar prim, modificarile in suma xor devin independente. Putem precalcula pentru fiecare valoare mex posibila (care e maxim 20), prin cate mutari initiale se poate produce aceasta diferenta in suma xor. Mutarea lui Bob fixata este optima, daca exista o astfel de mutare in vectorul precalculat excluzand numarul ales de Bob (pe cazul acesta, numerele prime sunt diferite). Impreuna, aceste mutari se anuleaza in suma xor si deci se revine la 0, stare de pierdere pentru Alice.

Trebuie sa actualizam frecventele din acest vector a numarului prim ales de Bob, iterand toti exponentii posibili. Complexitatea este O(NlogN) pentru acest caz.

Solutia care incearca toate combinatiile pentru primele doua mutari si retine doar mutarile distincte ale lui Bob, de complexitate O(N2 * log2) obtine punctaje partiale.

Prietene

Soluţie – 50 puncte (stud. Valentin Roşca, stud. Marta-Diana Filimon)

Este bine cunoscută formula de înmulţire a matricilor. Dată fiind o matrice pătratică A cu n linii si n coloane se
calculeaza B = A2 astfel Bi,j = Suma(pentru k=1 la N) Bi,k ∗ Bkj

Se observă că, dacă A este matricea de adiacenţă a unui graf orientat atunci Bi,j va reţine în câte moduri se poate
ajunge de la nodul i la nodul j pe un drum de lungime 2. Daca Bi,j > 0, atunci nodurile i si j sunt superadiacente.

Vom proceda astfel pentru operaţiile de tipul:

● q x y: pentru nodurile x si y se vor parcurge toate celelalte noduri şi, cu ajutorul matricilor A si B, vom
determina dacă aceste noduri sunt prietene sau nu.
● a x y:
 pentru fiecare nod z, dacă există arc între z şi x, atunci bx,z = bx,z + 1
 pentru fiecare nod z dacă există arc între y şi z, atunci bz,y = bz,y + 1
● d x y: se vor rezolvă analog cu operaţia a x y

Soluţie – 100 puncte (stud. Valentin Roşca, stud. Marta-Diana Filimon)
Operaţiile de tipul a şi q se vor rezolva la fel ca în varianta de 50 de puncte, însa pentru a verifica dacă x şi y sunt
prietene, se vor folosi funcţii hash. Pentru un nod x, funcţia hash asociată acestuia se va aplica pe vectorul de
apariţii corespunzător mulţimii nodurilor sale prietene.