Soluţii Algoritmiadă 2022, Runda 1

• Lista de probleme
• Tigri
• Twinperms
• Kxorbonacci

Soluţia problemei Tigri

Recomandăm înţelegerea editorialului acestei probleme în toate detaliile sale, întrucât a fost scris cu scop educaţional. Pentru o cât mai bună instruire, vă suntem disponibili prin intermediul forumului să vă răspundem la întrebările care ar răsări.

Ignorând pentru moment tipurile de date ale variabilelor X, Y, lei şi tigri, operaţiile în C++ pe care am vrea să le efectuăm sunt:

I

/// iniţializare
lei = 0;
tigri = 0;

D

/// depositum X
if (lei + X >= 0) {
    lei += X;
}

E

/// emptum X Y
if (lei - X * Y >= 0 && tigri + X >= 0) {
    lei -= X * Y;
    tigri += X;
}

V

/// vendere X Y
if (lei + X * Y >= 0 && tigri - X >= 0) {
    lei += X * Y;
    tigri -= X;
}

Ce tipuri de date să folosim?

Dacă s-ar fi garantat că X, Y, lei şi tigri pot fi reprezentate pe tipul de date int din C/C++, ar fi fost suficient să le declarăm ca fiind de tip int. Dar garanţia nu este dată decât pentru lei, prin urmare implementarea banală nu va obţine 100 de puncte.

De asemenea, soluţia nu stă în întrebuinţarea unui tip de date precum BigInteger din Java sau implementarea de mână a numerelor mari, din pricina limitei de timp. Fără să ne folosim de garanţia că 0 ≤ lei < 2³¹ (1), nu putem rezolva complet problema.

Din fericire, operaţiile sunt fie efectuate complet, fie practic ignorate. La finalul unei operaţii efectuate, (1) se respectă. Prin urmare, orice operaţie efecutată are proprietatea că 0 ≤ lei + X < 2³¹ pentru D, 0 ≤ lei - X * Y < 2³¹ pentru E şi 0 ≤ lei + X * Y < 2³¹ pentru V. Luând în calcul invariantul (1), deducem că:

• Un D efectuat are proprietatea că -2³¹ < X < 2³¹.
• Un E sau V efectuat are proprietatea că -2³¹ < X * Y < 2³¹. Atunci când X este nenul, mai deducem că -2³¹ < X, Y < 2³¹. Atunci când X este nul, observăm că valoarea lui Y nu contează - mai mult, putem chiar ignora operaţia.

Ce avem de înţeles din aceste proprietăţi şi observaţii? Că atunci când X este 0 sau când X sau Y sunt, în modul, mai mari sau egali ca 2³¹, ignorăm direct operaţia. Codul de la D, E sau V nici nu este apelat în aceste cazuri. Prin urmare, atunci când codul este apelat, putem ţine lei, X şi Y pe tipul de date int, cu atenţie să calculăm produsul X * Y pe long long.

Despre tigri, acum putem şti că, în modul, este mai mic sau egal cu suma modulelor tuturor valorilor X din fişier, prin urmare -N * (2³¹-1) ≤ tigri ≤ N * (2³¹-1). Deci tigri poate fi reţinut ca un întreg pe tipul de date long long.

Cum să citim fişierul de intrare?

Linie cu linie, desigur, dar cum să facem în aşa fel încât să decidem dacă să ignorăm direct operaţia sau să obţinem în variabilele X şi Y valorile corespunzătoare şi să lăsăm implementarea de la D, E şi V să-şi facă treaba?

Sunt două metode. În timp ce procesăm caracter cu caracter cifrele (şi semnul „-”) care compun numerele X şi Y din fişier,

• fie reţinem într-o variabilă de tip bool, numită, să zicem, valid, dacă cifrele procesate compun valori care dau şansa ca operaţia să aibă rost să o efectuăm, iar apoi condiţionăm în funcţie de valoarea lui valid dacă intrăm în codul de la D, E sau V;
• fie, în caz că ne dăm seama că operaţia poate fi direct ignorată, să ne asigurăm că valorile finale ale lui X şi Y vor fi în aşa fel încât codul de la D, E sau V să nu producă schimbare în valorile lui lei şi tigri. Codul va fi apelat oricum, deci practic nu mai ignorăm direct operaţia, dar ne asigurăm că urmează să fie ignorată.

Desigur, trebuie reţinut primul caracter al liniei ( d, e sau v) pentru a şti care dintre codurile D, E şi V să le efectuăm, dar şi ca să ştim câte numere să citim.

În ambele variante, se recomandă folosirea unei funcţii care să citească un număr şi care să fie apelată pentru X şi, dacă e nevoie, pentru Y. De asemenea, avem grijă să reţinem dacă întâlnim semnul „-” înainte cifrelor, respectiv să înmulţim modulul numărului citit mai apoi cu -1, dacă e nevoie.

În prima variantă, numărul nenegativ nr (adică viitorul modul al lui X sau Y) este actualizat după fiecare cifră citită 0 ≤ cifrăNouă ≤ 9 (pe care o deducem ca fiind egală cu valoarea ASCII a caracterului citit - verificat ca fiind cifră -, minus valoarea ASCII a caracterului „0”) în felul următor:

/// 1 şiftat la stânga de 31 de ori înseamnă 2^31 când e reţinut pe „long long”, dar nu şi când e reţinut pe „int”
static const long long doiLa31 = 1LL << 31;
/// „nr” e de tip „int”
if (10LL * nr + cifrăNouă < doiLa31) {
    nr = 10 * nr + cifrăNouă; /// nu mai e nevoie de conversia la „long long”, pentru că ştim că rezultatul se încadrează pe „int”
} else {
    valid = false; /// nu mai e nevoie să actualizăm „nr” pentru că nu vom mai folosi conţinutul variabilei la actualizarea lui „lei” sau „tigri”
}

(În plus, atunci când X este 0 iar valid este încă true după citirea lui Y, putem modifica valoarea lui valid în false. Mai pe larg despre de ce nu e nevoie de acest pas, urmăriţi a doua variantă de implementare propusă.)

În a doua variantă, vom reţine nr (respectiv X şi Y) pe long long şi îş vom plafona la o valoare precum const long long big = doiLa31 (condiţiile lui big, sunt, de fapt, ca pătratul său să intre pe long long şi să fie mai mare sau egal ca 2³¹). Plafonarea, mai bine cunoscută în varianta sa din engleză („to cap”), înseamnă că, după fiecare actualizare a valorii nr, inserăm următoarea bucată de cod:

#include <algorithm>
nr = std::min(nr, big);

Observăm că, în felul acesta, codul de la D, E şi V are aceleaşi urmări ca şi când valorile lui X sau Y ar fi fost cele din fişierul de intrare. Motivul e acela că, dacă X sau Y din fişier are modulul mai mare sau egal ca 2³¹, operaţia oricum va fi ignorată, iar misiunea codului de a nu modifica variabilele lei şi tigri e la fel de bine îndeplinită atunci când X sau Y (respectiv) este fix 2³¹.

Soluţia problemei Twinperms

Subtask 1: p_i = q_i

Pentru acest subtask, răspunsul va fi 0, deoarece putem sorta direct vectorul şi nu vom avea inversiuni. În mod evident, acesta este răspunsul minim.

Subtask 2: p_i + q_i = N + 1

Pentru acest subtask, observăm că dacă ne uităm la oricare două poziţii i şi j şi le interschimbăm, atunci suma totală de inversiuni nu se schimbă. Astfel, răspunsul va fi acelaşi, oricum am aplica operaţii. Aplicând operaţii astfel încât permutarea p să fie [1, 2, 3, ..., N], atunci permutarea q va fi [N, N - 1, N - 2, ..., 1]. Cum în p nu avem nicio inversiune, iar în q oricum am alege două elemente, ele vor fi în inversiune, răspunsul pentru acest subtask va fi N * (N - 1) / 2.

Subtask 3: 1 ≤ N ≤ 9

Pentru simplitate, vom considera cele două permutări ca şi un şir de perechi, unde x_i = (p_i, q_i). O interschimbare între două elemente i şi j este echivalentă cu interschimbarea perechilor x_i şi x_j. O observaţie ar fi că prin multiple operaţii de interschimbare, problema este echivalentă cu a reordona cele N perechi de numere, astfel încât dacă luăm în ordine primul număr din fiecare pereche şi în ordine cel de-al doilea număr, suma numărului de interschimbări să fie minimă. Astfel, o soluţie este să încercăm toate permutările posibile ale vectorului de perechi x. Putem calcula asta folosind un algoritm recursiv de generare al tuturor permutrilor.

Subtask 4: 1 ≤ N ≤ 16

Pentru acest subtask, putem folosi tehnica programării dinamice pe stări exponenţiale. Fie dp[mask] numărul minim de inversiuni în care toate elementele care aparţin mulţimii reprezentate de mask formează un prefix ("am folosit până acuma toate elementele din mask"). Putem să iterăm prin toate elementele din mask, iar pentru fiecare element, îl scoatem din mask şi verificăm câte inversiuni noi se formează dacă elementul ales este pus după toate celălalte elemente din mask, iar dintre toate variantele, alegem pe cea minimă. Complexitatea acestui algoritm va fi O(2^N * N²).

Subtask 5: 1 ≤ N ≤ 3.000

Putem clasifica elementele lui x în două tipuri de perechi:

• Perechile care contează cum sunt ordonate: dacă avem două perechi (a, b) şi (c, d) care respectă condiţiile a < c şi b < d, atunci contează în ce ordine le punem, deoarece dacă le punem în ordine inversă, obţinem două inversiuni, faţă de zero inversiuni.
• Perechile care nu conteaza în ce ordine sunt aşezate: două perechi (a, b) şi (c, d) unde a > c şi b < d nu contează în ce ordine le punem, deoarece ele vor forma de fiecare dată o singură inversiune.

Observăm că dacă sortăm elementele după oricare dintre permutări, atunci toate perechile de tipul 1 vor fi puse în ordinea potrivită. Astfel, putem să numărăm câte perechi avem de tipul 2 în complexitate O(N²)

Subtask 6: 1 ≤ N ≤ 100.000

Folosindu-ne de observaţiile de la subtaskul precedent, putem să sortăm toate perechile după unul dintre numere. Una din permutări, şi anume cea după care am sortat va genera zero inversiuni. Pentru cealaltă permutare, putem folosi mai multe metode clasice de a număra inversiunile dintr-o permutare, fie cu un Merge Sort modificat, fie cu structuri de date precum arbori de intervale sau arbori indexati binar.

Soluţia problemei Kxorbonacci

Observăm că un şir kxorbonacci generat de ( v₁, v₂, ..., v_n ) este periodic cu perioada n + 1. Deasemenea suma xor a orcăror n + 1 elemente alăturate este 0. Astfel este suficient să găsim perioada minima P a şirului primit ca input şi să verificăm dacă suma xor a acestei perioade este 0. Daca este 0, soluţia constă în primele P - 1 elemente ale şirului, altfel primele 2P - 1 elemente (dacă nu există, şirul generator este cel primit ca input).