pswap

Pswap

== include(page="template/taskheader" task_id="pswap") ==

Poveste şi cerinţă...

Eşti în anul 2121 şi vrei să configurezi o reţea de Neuralink. Ai la dispoziţie $N$ servere, ale căror IP-uri sunt reprezentate de permutări de lungime $M$ (ale numerelor $0, 1 ... M-1$). Vrei ca reţeaua ta să fie cât de mare, dar în acelaşi timp, te temi de potenţiale probleme de securitate: dacă un hacker află unul dintre IP-uri, îi va fi uşor să găsească un IP similar. Prin urmare, dintre cele $N$ servere pe care le ai la dispoziţie, vrei să alegi cât de multe servere pentru reţeaua ta astfel încât să nu existe două servere cu IP-uri similare. Două IP-uri sunt similare, dacă unul dintre ele poate fi obţinut din celălalt print exact o operaţie _swap_ (o interschimbare a oricăror două elemente). De exemplu, IP-urile $(0, 1, 2)$ şi $(1, 0, 2)$ sunt similare, dar $(0, 1, 2)$ şi $(1, 2, 0)$ nu.

h2. Date de intrare

h2. Protocol de interacţiune

Fişierul de intrare $pswap.in$ ...

Concurentul trebuie să implementeze o funcţie:

h2. Date de ieşire

== code(c) |
(C)   int solve(int N, int M, int** p);
==

În fişierul de ieşire $pswap.out$ ...

== code(cpp) |
(C++) int solve(int N, int M, std::vector< std::vector<int> > p);
==
 
Parametrii $N$ şi $M$ au semnificaţia din enunţ. $p$ reprezintă o matrice cu $N$ linii şi $M$ coloane, linia $i$ reprezentând cel de-al $i$-lea IP (o permutare de lungime $M$). Funcţia va întoarce numărul maxim de IP-uri nesimilare.
 
*Din cauza limitărilor impuse de Infoarena şi pentru a reproduce condiţiile din concurs, recomandăm să foloseşti template-urile de {'aici':problema/pswap?pswap.zip}.*

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 2500$
* $1 ≤ M ≤ 5000$
* Oricare ar fi $0 &le; i < n, p[i]$ este o permutare a numerelor de la $0$ la $M - 1$
* Oricare ar fi $0 &le; i, j < n, p[i]$ si $p[j]$ sunt distincte
 
h2. Subtask 1 (11 puncte)
 
* $N, M &le; 20$
 
h2. Subtask 2 (30 de puncte)
 
* Cel mult 20 de permutări din cele $N$ sunt similare cu oricare alta dintre cele $N$
* $N &le; 1000$
 
h2. Subtask 3 (36 de puncte)
 
* $N &le; 300$
 
h2. Subtask 4 (14 puncte)
 
* $N &le; 1000$
 
h2. Subtask 5 (9 puncte)
 
* Fără restricţii suplimentare.

h2. Exemplu
table(example). |_. pswap.in |_. pswap.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

| 3 3
0 1 2
2 1 0
1 0 2
| 2 |
| 5 5
0 1 2 3 4
1 0 2 3 4
0 1 2 4 3
0 4 2 3 1
4 1 2 3 0
| 4 |
| 6 3
0 1 2
0 2 1
1 0 2
1 2 0
2 1 0
2 0 1
| 3
|

h3. Explicaţie

...

Pentru primul exemplu, alegem serverele cu IP-urile $(2, 1, 0)$ şi $(1, 0, 2)$. Nu putem alege serverul $(0, 1, 2)$, deoarece IP-ul său este similar cu ale celorlalte 2.
 
Pentru cel de-al doilea exemplu, putem alege toate IP-urile în afară de primul.
 
Pentru cel de-al treilea exemplu, putem selecta IP-urile $(0, 1, 2)$, $(1, 2, 0)$, $(2, 0, 1)$.

== include(page="template/taskfooter" task_id="pswap") ==