Compact2

[•klamathix]

Aici se pot pune întrebări legate de problema Compact de la Runda Finala a concursului Algoritmiada 2015.

[•vladtt]

Avem voie sa permutam sirul P pana se ajunge la alt sir, si sa cautam in acel sir un subsir supercompact?
Daca Da: sirul poate fi permutat pana se ajunge la 3 4 2 5 1 care este el insusi un supercompact
Daca Nu: in exemplu nu este niciun subsir supercopact (sau cel putin nu vad eu unul... )

[•eudanip]

Nu se permuta sirul. Subsirul din exemplu este "4 5 3". Vom explica in enunt ce inseamna subsir mai exact.

[•nparfene2004]

Va rog foarte mult sa imi dati si mie o idee de rezolvare a problemei compact2. Multumesc.

[•cojocarugabi]

Va rog foarte mult sa imi dati si mie o idee de rezolvare a problemei compact2. Multumesc.

Gindeste la faptul ca daca ai un sir cu elemente de la l lar r atunci poti adauga doar l-1 ori r+1,acum daca ai un x si daca a fost x + 1,x - 1 atunci putem adauga x ori la multimea x - 1 ori la x + 1 deci x adaugam +1 la lungimea multimei ce contine x - 1 si x + 1,daca x - 1 a fost iar x + 1 nu atunci legam x - 1 cu x,analog daca x + 1 a fost iar x - 1 nu iar daca nici x + 1 si nici x - 1 faci multimea doar din x.
Poti folosi dsu pentru multimi.Pentru ajutor poti sa te uiti la sursa mea https://ideone.com/YSAjyS.