Solutii Algoritmiada 2018, Runda PreONI

Greutati

Un greedy corect cu care am putea rezolva conceptual problema este urmatorul: Luam cea mai mare putere de 2 si o punem in setul care are suma mai mica. Vom prezenta mai departe varianta optima de a pune in practica aceasta idee.

Consideram puterile de 2 in ordine descrescatoare. Sa retinem intr-o variabila S diferenta minima dintre sumele din cele 2 seturi de numere obtinuta pana acum (diferenta care poate fi si nula) si intr-o alta variabila T care este ultima putere de 2 procesata (desiur, exponentul ei). Din moment ce diferenta este multiplu de 2T, vom retine doar factorul cu care s-ar inmulti 2T pentru a obtine adevarata diferenta. Acum suntem la numarul 2Q care apare de F ori. In primul rand, inmultim variabila S cu 2T - F. Apoi, avem 2 cazuri.

  • daca F < S, punem toate numerele in setul cu suma mai mica: scadem F din S
  • daca F ≥ S, inseamna ca vom putea anula diferenta S, ramanand cu F - S numere si diferenta nula. Pe acestea le distribuim in mod egal, pe cat posibil, adica daca numarul este par, noua diferenta S va putea fi nula, iar daca e impar, S = 1

Pentru a termina procesarea numerelor 2Q, schimbam valoarea lui T in Q.

Dupa ce am procesat toate numerele, afisam S * 2T modulo MOD.

O problema cu aceasta solutie este ca S poate sa creasca pana depaseste maximul admis de long long si, desi stim ca, daca se intampla asa ceva, de acum incolo ne vom afla decat in cazul in care F < S, nu vom putea sa cunoastem valoarea lui S la final, pentru afisare. Putem trece peste acest impediment daca retinem si valoarea Smod, adica S modulo MOD, pe care o supunem tuturor modificarilor suportate de S, doar ca operatiile sunt facute modulo MOD. Observatie: A retine doar Smod este gresit intrucat comparatia F < Smod nu este echivalenta cu F < S.

Complexitate: O(N * (logN + logP))

Karma

O parantezare este corecta daca si numai daca, considerand paranteza deschisa +1 si una deschisa -1, toate prefixele sirului au suma nenegativa.

Pentru ca limitele sunt mici, putem sa ne fixam coloanele pe care le-am fixat ca prefix si sa calculam pentru submultimea aleasa, codficata binar drept numarul i, numarul D[i] care reprezinta numarul de moduri in care putem permuta coloane din submultimea i, astfel incat toate prefixele au suma nenegativa. In primul rand, daca exista vreun sir pentru care suma parantezelor alese (acelea din submultimea de coloane i) este negativa, D[i] = 0. Daca nu este cazul, cautam o posibila ultima coloana care sa fi fot adaugata unui sufix. Astfel, pentru orice coloana j care apare in i, adaugam D[i fara j] la D[i].

Complexitate: O(2M * (N + M))

Permbit

O traducere a conditiei de validitate a permutarii P
S_i_j = S_{(i+1)}_{P[j]}, \hspace{5} \forall \hspace{3} 1 \leq i < n, 1 \leq j \leq m
ar putea fi urmatoarea: Valoarea lui P[i] poate fi egala cu j daca si numai daca sirul de biti de pe coloana i a matricei date, fara ultima linie, este egal cu sirul de biti de pe coloana j a matricei, fara prima linie. Prin urmare, o sa fie mai multe perechi de multimi maximale de indici, cu proprietatea ca, pentru orice indice i din prima multime din pereche, P[i] poate fi egal cu oricare din indicii j din a doua multime. Cum existenta unei solutii este garantata, in fiecare pereche, cele 2 multimi vor avea cardinale egale, egale prin notatie, cu cardinalul perechii. In plus, fiecare indice apare exact o data intr-o prima multime dintr-o pereche si exact o data intr-o secunda multime dintr-o pereche. Prin urmare, toate grupurile sunt independente.

Pentru fiecare pereche de multimi, numarul de moduri de a da valori lui P[i], pentru indicii i din prima multime, este egal cu cardinalul perechii! (factorial). Din faptul ca perechile sunt independente, numarul de moduri devine egal cu produsul acestor factoriale, luate pentru fiecare pereche. Gasirea unei permutari valide oarecare necesita o simpla atribuire de valori pentru P[i] cu numere libere din multimea secunda din perechea in care i apare in prima multime. Pentru gasirea permutarii mediene atribuirea trebuie facuta cu grija suplimentara. Astfel, daca la un pas, cardinalul perchii este impar, atribuim lui P[i] valoarea mediana din multimimea secunda din pereche. Daca e par, alegem mediana inferioara si, de acum incolo, alegem maximul lexicografic in loc de medianul, ceea ce inseamna ca se alege cel mai mare numar liber din multime.

Complexitatea este data de gasirea perechilor de multimi, care poate fi realizata pentru 100 de puncte in O(N * M * logM) sau O(N * M). O solutie posibila ar fi sa sortam indicii coloanelor de doua ori, prima data considerand matricea fara ultima linie, a doua oara fara prima linie, caz in care multimile vor fi formate din valori care apar in intervale compacte pe sirul sortat de indici.