InfoAs Atlas

<- Go back View preview

Problema Polihroniade

Identification properties

🔒 The following are read-only properties. If you wish to change them, please create a new problem.

Name

Content ID

Hash Note: The hash is stored in the filesystem.

Content properties

Task

![](https://i.ibb.co/R3VnRQf/image.png)

Figura 1: Elisabeta Polihroniade, 1979 în Rio de Janeiro

O matrice pătratică de dimensiuni `N × N` cu `N` par și elemente din mulțimea `{0, 1}` se numește **tablă de șah** dacă oricare două celule vecine pe o linie sau pe o coloană au valori diferite (cu alte cuvinte, dacă nu există două valori egale alăturate).  
  
De ziua ei, Victor i-a cumpărat Elisabetei o astfel de matrice `A`, care nu este neapărat tablă de șah. Aflând despre pasiunea ei, acesta vrea acum să transforme matricea `A` într-o tablă de șah. Timpul fiind limitat, el poate efectua doar următoarele tipuri de operații asupra matricei:

1. Interschimbă liniile `i` și `j` din `A` (celelalte linii rămân neschimbate, iar valorile din interiorul liniilor `i` și `j` rămân neschimbate și își păstrează ordinea). Operația are sens pentru `1 ≤ i, j ≤ N`.
  2. Interschimbă coloanele `i` și `j` din `A` (celelalte coloane rămân neschimbate, iar valorile din interiorul coloanelor `i` și `j` rămân neschimbate și își păstrează ordinea). Operația are sens pentru `1 ≤ i, j ≤ N`.

## Cerință

Dorind s-o impresioneze pe Elisabeta, Victor apelează la voi, programatori renumiți, să-l ajutați în a transforma matricea `A` într-o tablă de șah. Pentru aceasta, Victor are nevoie de următoarele informații:

1. Poate fi transformată matricea `A` într-o tablă de șah?
  2. Care este numărul minim de operații necesare pentru a duce la îndeplinire acest scop?
  3. Care ar fi o succesiune de operații care transformă matricea `A` într-o tablă de șah?

În cazul ultimei cerințe, pentru a intra în grațiile lui Victor va trebui ca numărul de operații efectuate să fie minim. Totuși, chiar și un număr neminim de operații va fi răsplătit, însă nu într-atât de mult.

Vi se dau două numere `P`, `T` și `T` matrice `A`, reprezentând mai multe instanțe ale problemei. Pentru fiecare matrice `A` dintre cele `T` va trebui să rezolvați cerința cu numărul `P ∈ {1, 2, 3}` dintre cele listate mai sus.
## Date de intrare

Pe prima linie se găsesc două numere întregi pozitive `P` și `T`, reprezentând numărul cerinței de rezolvat și, respectiv, numărul de scenarii pentru care va trebui să rezolvați problema. Urmează cele `T` instanțe ale problemei, fiecare fiind compusă din `N + 1` linii: pe prima linie se va afla numărul `N`, iar pe următoarele `N` linii câte `N` cifre binare **neseparate** prin spații, reprezentând câte o linie a matricei `A`.
## Date de ieșire

Pentru fiecare dintre cele `T` instanțe se va afișa răspunsul, începând de la o linie nouă, după cum urmează:

1. Dacă `P = 1`, atunci se va afișa pe o singură linie `1` dacă matricea `A` poate fi transformată în tablă de șah, și `0` altfel.
  2. Dacă `P = 2`, atunci se va afișa pe o singură linie un întreg reprezentând numărul minim de interschimbări de linii și/sau coloane necesare pentru a transforma matricea `A` în tablă de șah.
  3. Dacă `P = 3`, atunci se va afișa pe o linie un număr `X`. Apoi, pe fiecare dintre următoarele `X` linii se va afișa câte o interschimbare de linii sau coloane, după următorul format: `L i j` are semnificația că liniile `i` și `j` se interschimbă, iar `C i j` are semnificația că se interschimbă coloanele `i` și `j`. Matricea obținută după aplicarea celor `X` operații asupra lui `A` în ordinea dată trebuie să fie o tablă de șah.

## Restricții și precizări

* `1 ≤ T ≤ 350`
  * `1 ≤ N ≤ 1000`
  * `N` este par
  * Pentru cerințele de tip `P = 2` și `P = 3` se garantează că matricea `A` poate fi transformată în tablă de șah folosind interschimbări de linii și/sau coloane
  * Suma valorilor `N` pentru cele `T` scenarii nu depășește `2000`

### Pentru 40 de puncte

* `P = 1`

### Pentru alte 34 de puncte

* `P = 2`

### Pentru alte 26 de puncte

* `P = 3`
  * Dacă există mai multe operații, oricare este considerată corectă
  * Dacă numărul `X` de operații folosite nu este minim, atunci se acordă 50% din punctajul pe test

Examples

[{"input": "1 3\n2\n11\n11\n4\n1100\n1100\n0011\n0011\n2\n10\n01", "output": "0\n1\n1", "explanation": "Pentru primul exemplu, avem <code>P = 1</code>, deci pentru cele <code>T = 3</code> instan\u021be se cere numai dac\u0103 se pot transforma \u00een tabl\u0103 de \u0219ah prin interschimb\u0103ri de linii \u0219i/sau coloane. Pentru prima instan\u021b\u0103 acest lucru nu este posibil, deoarece nu avem niciun <code>0</code> \u00een matrice. Pentru cea de-a doua instan\u021b\u0103, putem efectua urm\u0103toarele opera\u021bii:\r\n<img src=\"https://i.ibb.co/bgNFhY3/image.png\" alt=Exemplul1>\r\nPentru ultima instan\u021b\u0103, matricea <code>A</code> este deja tabl\u0103 de \u0219ah.\r\nPentru al doilea exemplu avem <code>P = 2</code>, deci pentru cele <code>T = 2</code> instan\u021be se cere num\u0103rul minim de opera\u021bii pentru a le transforma \u00een tabl\u0103 de \u0219ah. Pentru prima instan\u021b\u0103, o solu\u021bie cu <code>2</code> opera\u021bii este prezentat\u0103 mai sus, \u0219i nu exist\u0103 solu\u021bii mai scurte. Pentru cea de-a doua instan\u021b\u0103, matricea este deja tabl\u0103 de \u0219ah, deci r\u0103spunsul este <code>0</code>.\r\nAl treilea exemplu este exact ca anteriorul, numai c\u0103 avem <code>P = 3</code>, deci trebuie tip\u0103rite exact care sunt opera\u021biile ce aduc matricea la forma de tabl\u0103 de \u0219ah. Pentru punctaj maxim pe acest exemplu, ar fi obligatoriu s\u0103 afi\u0219\u0103m o solu\u021bie cu <code>2</code> opera\u021bii (adic\u0103 num\u0103r minim), cum ar fi cea de mai sus. Cu toate acestea, cu scop demonstrativ, noi venim cu o solu\u021bie compus\u0103 din <code>3</code> opera\u021bii prin care ob\u021binem doar 50% din punctaj:\r\n<img src=\"https://i.ibb.co/WFCBvzy/image.png\" alt=Exemplul3>"}, {"input": "2 2\n4\n1100\n1100\n0011\n0011\n2\n10\n01", "output": "2\n0", "explanation": "Pentru primul exemplu, avem <code>P = 1</code>, deci pentru cele <code>T = 3</code> instan\u021be se cere numai dac\u0103 se pot transforma \u00een tabl\u0103 de \u0219ah prin interschimb\u0103ri de linii \u0219i/sau coloane. Pentru prima instan\u021b\u0103 acest lucru nu este posibil, deoarece nu avem niciun <code>0</code> \u00een matrice. Pentru cea de-a doua instan\u021b\u0103, putem efectua urm\u0103toarele opera\u021bii:\r\n<img src=\"https://i.ibb.co/bgNFhY3/image.png\" alt=Exemplul1>\r\nPentru ultima instan\u021b\u0103, matricea <code>A</code> este deja tabl\u0103 de \u0219ah.\r\nPentru al doilea exemplu avem <code>P = 2</code>, deci pentru cele <code>T = 2</code> instan\u021be se cere num\u0103rul minim de opera\u021bii pentru a le transforma \u00een tabl\u0103 de \u0219ah. Pentru prima instan\u021b\u0103, o solu\u021bie cu <code>2</code> opera\u021bii este prezentat\u0103 mai sus, \u0219i nu exist\u0103 solu\u021bii mai scurte. Pentru cea de-a doua instan\u021b\u0103, matricea este deja tabl\u0103 de \u0219ah, deci r\u0103spunsul este <code>0</code>.\r\nAl treilea exemplu este exact ca anteriorul, numai c\u0103 avem <code>P = 3</code>, deci trebuie tip\u0103rite exact care sunt opera\u021biile ce aduc matricea la forma de tabl\u0103 de \u0219ah. Pentru punctaj maxim pe acest exemplu, ar fi obligatoriu s\u0103 afi\u0219\u0103m o solu\u021bie cu <code>2</code> opera\u021bii (adic\u0103 num\u0103r minim), cum ar fi cea de mai sus. Cu toate acestea, cu scop demonstrativ, noi venim cu o solu\u021bie compus\u0103 din <code>3</code> opera\u021bii prin care ob\u021binem doar 50% din punctaj:\r\n<img src=\"https://i.ibb.co/WFCBvzy/image.png\" alt=Exemplul3>"}, {"input": "3 2\n4\n1100\n1100\n0011\n0011\n2\n10\n01", "output": "3\nL 2 4\nC 2 3\nL 1 2\n0", "explanation": "Pentru primul exemplu, avem <code>P = 1</code>, deci pentru cele <code>T = 3</code> instan\u021be se cere numai dac\u0103 se pot transforma \u00een tabl\u0103 de \u0219ah prin interschimb\u0103ri de linii \u0219i/sau coloane. Pentru prima instan\u021b\u0103 acest lucru nu este posibil, deoarece nu avem niciun <code>0</code> \u00een matrice. Pentru cea de-a doua instan\u021b\u0103, putem efectua urm\u0103toarele opera\u021bii:\r\n<img src=\"https://i.ibb.co/bgNFhY3/image.png\" alt=Exemplul1>\r\nPentru ultima instan\u021b\u0103, matricea <code>A</code> este deja tabl\u0103 de \u0219ah.\r\nPentru al doilea exemplu avem <code>P = 2</code>, deci pentru cele <code>T = 2</code> instan\u021be se cere num\u0103rul minim de opera\u021bii pentru a le transforma \u00een tabl\u0103 de \u0219ah. Pentru prima instan\u021b\u0103, o solu\u021bie cu <code>2</code> opera\u021bii este prezentat\u0103 mai sus, \u0219i nu exist\u0103 solu\u021bii mai scurte. Pentru cea de-a doua instan\u021b\u0103, matricea este deja tabl\u0103 de \u0219ah, deci r\u0103spunsul este <code>0</code>.\r\nAl treilea exemplu este exact ca anteriorul, numai c\u0103 avem <code>P = 3</code>, deci trebuie tip\u0103rite exact care sunt opera\u021biile ce aduc matricea la forma de tabl\u0103 de \u0219ah. Pentru punctaj maxim pe acest exemplu, ar fi obligatoriu s\u0103 afi\u0219\u0103m o solu\u021bie cu <code>2</code> opera\u021bii (adic\u0103 num\u0103r minim), cum ar fi cea de mai sus. Cu toate acestea, cu scop demonstrativ, noi venim cu o solu\u021bie compus\u0103 din <code>3</code> opera\u021bii prin care ob\u021binem doar 50% din punctaj:\r\n<img src=\"https://i.ibb.co/WFCBvzy/image.png\" alt=Exemplul3>"}]

Default code

Summary

Editorial

_Descriere oferită de propunători._

_Propunător: Andrei Constantinescu, University of Oxford_

Problema Polihroniade a fost gândită inițial ca o problemă de dificultate relativ mai scăzută a setului, deoarece aceasta nu necesită vreo tehnică cunoscută în prealabil. Deși ea poate părea greu de abordat la prima vedere, observăm în cele ce urmează cum câteva observații, relativ simple, fac problema mai ușor de atacat.

**1\. Operațiile comută**

Fie `i, j, k, l` numere între `1` și `N`, atunci operațiile `O1 = L i j` și `O2 = C k l` comută. Cu alte cuvinte, ne este indiferent dacă asupra matricei `A` efectuăm întâi `O1` și apoi `O2` sau invers (adică `O2` și apoi `O1`). În mod inductiv, deducem că dacă problema admite o soluție, atunci ea admite o soluție în care întâi permutăm liniile lui `A`, și apoi coloanele lui `A`. Mai mult, în mod informal putem spune că liniile și coloanele sunt independente, fiecare fiind o problemă de sine stătătoare. Așadar, este suficient să explicăm cum efectuăm operațiile pe linii, cele pe coloane fiind rezolvate analog. Totuși, rezolvarea este încă neclară – avem nevoie de alte observații.

**2\. Metoda mersului invers**

Să considerăm problema inversă: plecăm de la o tablă de șah și vrem ca prin interschimbări succesive de linii și/sau coloane să ajungem la matricea `A`. Cum operațiile din problemă sunt reversibile, problema inversă nu este cu nimic mai grea sau mai ușoară decât cea pusă în discuție. Într-o tablă de șah există fix `2` tipuri de linii: cele de forma `0101…01` și, respectiv, cele de forma `1010…10`. Mai mult, avem fix `N / 2` linii de fiecare tip. Ce este acum vital să observăm este că operațiile pe linii și coloane nu schimbă foarte mult această configurație. Mai exact, indiferent ce interschimbări am efectua, matricea rezultată va avea `N / 2` linii identice și alte `N / 2` linii identice care sunt fix complementul primelor `N / 2` (adică au `0` unde era `1` și vice-versa). Bineînțeles, în ambele tipuri trebuie să avem exact `N / 2` biți de `0` și `N / 2` biți de `1`, cum interschimbările de orice fel nu schimbă conținutul liniilor, ci doar ordinea elementelor din ele. În mod clar, aceleași observații sunt valabile și pentru coloane.

Date fiind cele spuse, avem acum o condiție necesară pentru ca problema să aibă soluție pentru o matrice `A` dată: matricea `A` trebuie să aibă exact `2` tipuri de linii: `N / 2` de un tip, și `N / 2` de celălalt tip, unde tipurile sunt complementare și conțin exact `N / 2` biți de `1` (automat, și `N / 2` biți de `0`) fiecare. De asemenea, aceeași condiție trebuie să fie îndeplinită și pentru coloane. Ce este posibil surprinzător acum este că aceste condiți sunt și suficiente, adică, cu alte cuvinte, matricea `A` poate fi transformată într-o tablă de șah **dacă și numai dacă** aceste condiții sunt adevărate pentru instanța noastră. Verificarea acestor condiții se poate face în timp `O(N2)` și aduce cu sine 40 de puncte pe problemă (credem noi, aceasta este cea mai dificilă parte a problemei, și este, prin urmare, răsplătită generos ca punctaj).

**3\. Transformarea matricei A în tablă de șah cu număr minim de operații**

Pentru restul problemei, facem presupunerea că matricea `A` se poate transforma în tablă de șah, așa cum este specificat, de altfel, și în enunțul problemei. Cheia rezolvării stă în următoarea observație: atâta timp cât aranjăm ca prima linie a matricei `A` să alterneze (`0101…01` sau `1010…10`) și ca prima coloană a matricei `A` să alterneze, restul matricei va fi, în mod garantat, o tablă de șah (acest lucru rezultă din observația de mai sus legată de tipul liniilor: avem `N / 2` linii de fiecare tip, și tipurile sunt complementare; similar pentru coloane). Mai sus am stabilit că liniile și coloanele sunt independente, deci cele două probleme se pot trata separat. De asemenea, ele se pot reformula mai simplu: dat fiind un șir binar de lungime `N` format din `N / 2` caractere `0` și `N / 2` caractere `1`, transformați-l într-un șir alternant folosind un număr minim de operații de interschimbare a două caractere.

Există doar două șiruri binare alternante de acest tip: `0101…01` și `1010…10`. Fără a restrânge generalitatea, vom încerca să îl obținem pe primul, dar pentru o soluție completă trebuiesc încercate ambele și întoarsă soluția care duce la un număr minim de operații. În șirul `0101…01` observăm că toate caracterele `0` sunt pe poziții pare și toate caracterele `1` sunt pe poziții impare. În șirul nostru pe care dorim să îl aducem la această formă există trei tipuri de caractere:

1. Caractere care sunt la locul lor – adică `0` pe poziții pare și `1` pe poziții impare.
 2. Caractere `0` care sunt pe o poziție impară (deci trebuie obligatoriu să facă parte din cel puțin o interschimbare). Să notăm mulțimea pozițiilor de acest tip din șirul nostru cu `S0`.
 3. Caractere `1` care sunt pe o poziție pară (deci trebuie obligatoriu să facă parte din cel puțin o interschimbare). Să notăm mulțimea pozițiilor de acest tip din șirul nostru cu `S1`.

Reiterând, pozițiile din `S0 U S1` trebuie să facă parte dintr-o interschimbare pentru a le aduce pe o poziție cu paritatea corectă. Observăm că sunt exact atâtea caractere `0` care nu sunt la locul lor câte caractere de `1` nu sunt la locul lor (notăm pentru aceasta că numărul de caractere `0` și caractere `1` este egal), deci `|S0| = |S1|`. Prin urmare, cele de mai sus ne spun că avem nevoie de cel puțin `|S0|` interschimbări pentru a rezolva problema. Mai mult, o soluție cu fix `|S0|` interschimbări se poate construi: interschimbăm pe rând câte o poziție din `S0` cu una din `S1` până când epuizăm ambele mulțimi (fiecare interschimbare practic pune la locul lor două caractere). Așadar, această soluție este și optimă din punctul de vedere al numărului de interschimbări. Bineînțeles, trebuie să aplicăm acest algoritm și pentru coloane, dar acest lucru nu schimbă conceptual rezolvarea. În total, soluția se construiește în timp `O(N)` după citire. Cum este posibil acest lucru dacă complexitatea de citire a matricei este `O(N2)`? Ei bine, orice matrice care se poate transforma în tablă de șah este unic determinată de prima sa linie și prima sa coloană, deci s-ar putea spune că însăși formatul de intrare este inhibitor pentru obținerea unei complexități timp mai bune (dacă ni s-ar fi dat doar prima linie și prima coloană problema se putea rezolva în `O(N)`, lucru menționat aici mai mult ca o curiozitate matematică decât ca o observație necesară pentru rezolvarea problemei). Folosind această soluție obținem restul de 60 de puncte pe problemă.

Solution

Contributor ID

Author

File name	Description	Updated at	Size	Actions
hash.txt	Special file The hash of all the content of a problem. Autogenerated.	10 January 2025 21:26	64 B	View
manifest.json	Special file Metadata for the problem. Autogenerated.	10 January 2025 21:26	2 KB	View
0-polihroniade.in	/ 100	10 January 2025 21:26	76 KB	View
0-polihroniade.ok	/ 100	10 January 2025 21:26	680 B	View
1-polihroniade.in	/ 100	10 January 2025 21:26	868 KB	View
1-polihroniade.ok	/ 100	10 January 2025 21:26	352 B	View
2-polihroniade.in	/ 100	10 January 2025 21:26	981 KB	View
2-polihroniade.ok	/ 100	10 January 2025 21:26	350 B	View
3-polihroniade.in	/ 100	10 January 2025 21:26	41 KB	View
3-polihroniade.ok	/ 100	10 January 2025 21:26	211 B	View
4-polihroniade.in	/ 100	10 January 2025 21:26	99 KB	View
4-polihroniade.ok	/ 100	10 January 2025 21:26	113 B	View
5-polihroniade.in	/ 100	10 January 2025 21:26	197 KB	View
5-polihroniade.ok	/ 100	10 January 2025 21:26	48 B	View
6-polihroniade.in	/ 100	10 January 2025 21:26	392 KB	View
6-polihroniade.ok	/ 100	10 January 2025 21:26	28 B	View
7-polihroniade.in	/ 100	10 January 2025 21:26	783 KB	View
7-polihroniade.ok	/ 100	10 January 2025 21:26	16 B	View
8-polihroniade.in	/ 100	10 January 2025 21:26	1 MB	View
8-polihroniade.ok	/ 100	10 January 2025 21:26	7 B	View
9-polihroniade.in	/ 100	10 January 2025 21:26	41 KB	View
9-polihroniade.ok	/ 100	10 January 2025 21:26	214 B	View
10-polihroniade.in	/ 100	10 January 2025 21:26	99 KB	View
10-polihroniade.ok	/ 100	10 January 2025 21:26	114 B	View
11-polihroniade.in	/ 100	10 January 2025 21:26	197 KB	View
11-polihroniade.ok	/ 100	10 January 2025 21:26	47 B	View
12-polihroniade.in	/ 100	10 January 2025 21:26	392 KB	View
12-polihroniade.ok	/ 100	10 January 2025 21:26	28 B	View
13-polihroniade.in	/ 100	10 January 2025 21:26	783 KB	View
13-polihroniade.ok	/ 100	10 January 2025 21:26	16 B	View
14-polihroniade.in	/ 100	10 January 2025 21:26	1 MB	View
14-polihroniade.ok	/ 100	10 January 2025 21:26	7 B	View
In total: 32 files 8 MB

Problema Polihroniade

Identification properties

Content properties

Technical properties

Delete all files