015 Permutari II

[•bogdan2412]

Dupa ce problema asta a fost rezolvata de vreo 135 oameni nu crezi ca e cam absurd sa fie exemplele gresite? Mai citeste problema de multe ori pana intelegi ce vrea...

[•dragos_d]

Va rog frumos sa-mi oferiti si mie o indicatie pentru aceasta problema

[•nash]

 ok .. algoritmul de rezolvare e clasic .. cu toate astea mai mult de 85 de punde nu iau ..

[•gabitzish1]

8
1 5 2 3 4 8 6 7                  12

imi explica cineva exemplul de mai sus?

[•DITzoneC]

p¹: 1 5 2 3 4 8 6 7 
p²: 1 4 5 2 3 7 8 6
p³: 1 3 4 5 2 6 7 8
p⁴: 1 2 3 4 5 8 6 7
p⁵: 1 5 2 3 4 7 8 6
p⁶: 1 4 5 2 3 6 7 8
p⁷: 1 3 4 5 2 8 6 7
p⁸: 1 2 3 4 5 7 8 6
p⁹: 1 5 2 3 4 3 6 7 8
p¹⁰: 1 4 5 2 3 8 6 7
p¹¹: 1 3 4 5 2 7 8 6
p¹²: 1 2 3 4 5 6 7 8

Deci raspunsul e 12.

[•Dastas]

Imi dati va rog un indiciu pt teste 1 5 si 10? Iau TLE.. si nu prea stiu cum sa scap de el..

Aflu pentru fiecare numar in cati pasi ajunge pe pozitia finala, avand un while care il intoarce pe p1[p1[p1[...]]]... si apoi fac cmmmc al acestor numere. Si daca scot cmmmc-ul, tot da TLE pe testele alea. Am incercat sa tratez particular cazul 2 3 4 ... n 1 dar tot nu vrea...

Cum as putea face mai eficient? 

[•DITzoneC]

Marcheaza toate numerele prin care treci de-a lungul unui ciclu si pentru alea nu va mai trebui sa calculezi iar.
Complexitatea scade asa de la O(n²) la O(n)

[•Dastas]

Multumesc, mi-a iesit! 

[•mordred]

ok .. algoritmul de rezolvare e clasic .. cu toate astea mai mult de 85 de punde nu iau ..

chiar daca a trecut mult timp, 85 de puncte sunt pentru solutia brute-force ( O(n²) )
am testat eu aici

[•alexandru92]

Ma poate ajuta cineva, pentru problema aceasta eu fac o metoda mai mult babeste:
1)citesc datele de intrare
2) cat timp permutarea curenta nu este egala cu permutarea identica atunci:
           p[ i ]=v[p[ i ]];
           k++;
3) Afisez  k.
p[]= retin permutarea curent  si v[] este permutarea introdusa din fisier.
Cum as putea sa mai optimizez?
Si desi n-are legatura cu subiectul  exista  Numarul lui Stirling de speta 1?

[•Mishu91]

Daca iti scrii toate puterile unei permutari (cred ca gasesti si pe forum toate formele scrise) vei observa ca pe o pozitie anumite elemente se tot repeta. Pentru exemplul trei pe pozitia 2 vor aparea 5, apoi 4, apoi 3 si 2, dupa care se reia de la capat. Tu tre sa determini gradul permutarii care are toate elementele pe pozitiile dorite, iar acest grad este cmmmc-ul repetitiilor tuturor elementelor. In al 3lea exemplu 1 ramane pe prima pozitie in orice permutare, 2,3,4,5 se repeta din 4 in 4, iar 6, 7 si 8 din 3 in 3, deci rezultatul cerut va fi cmmmc(1, 3, 4) = 12. Daca te chinui otzara, poti determina din cat in cat se repeta fiecare element in O(N).
Sper ca am fost de folos, si totodata nu prea explicit  

[•Florian]

Si desi n-are legatura cu subiectul  exista  Numarul lui Stirling de speta 1?

Da, Numarul lui Stirling de speta I reprezinta numarul de permutari ale elementelor {1,2,...,n} ce contin exact m cicluri. ( Secventa ( c1,c2, ... , ck ) se numeste ciclu in permutarea p, daca p(c1)=c2, p(c2)=c3, ... ,p(ck) = c1. )

[•alexandru92]

@Andrei Misarca multumesc pentru explicatie, am citit comentarile de aici dar nu intleelgeam , din ce obtii cmmmc
@Marcu Florian: exista si o relatie de recurenta

[•Florian]

s(n,m) - nr lui stirling de speta I.

* s(n,m) = 0, pt n<m
* s(n,m) = s(n-1,m-1) + n*s(n-1,m).

Explicatia: Elementul n poate forma singur cel de-al m-lea ciclu, sau poate fi inserat in cele m cicluri deja existente (in n moduri). Sper sa nu fi gresit. 

[•alexandru92]

conditia   n<m  este necesara dar nu suficienta, daca ai n=4,m=2 o sa dea o bucla la infinit. Am gasit
aici , un articol interesant

[•Florian]

Nu va intra in ciclu, pentru ca nu face decat sa numere niste permutari. Nu le si genereaza. 

[•alexandru92]

Am scris o functie recursiva si condtia de oprire am pus-o n<m, cnd returneazsa 0:

Cod:

int s(int n,int m)
  {
   if(n<m) return 0;
   return s(n-1,m-1)+n*s(n-1,m);
  }

dac dai n=4; m=2; mereu  n>m,  pentru ca scazi mereu 1

[•andrici_cezar]

La testul 2 permutarile sunt:
p1: 3 4 1 2
p2: 4 1 2 3
p3: 1 2 3 4
p4: 2 3 4 1
Astea sunt?
Si daca da la testul 3 unde e 8 dc este 12 dc nu sunt la fel?

[•gabitzish1]

La testul 2, permutarile sunt:
p¹: 2 3 4 1
p²: 3 4 1 2
p³: 4 1 2 3
p⁴: 1 2 3 4

Pentru testul 3 s-a mai explicat de ce raspunsul e 12:

p¹: 1 5 2 3 4 8 6 7 
p²: 1 4 5 2 3 7 8 6
p³: 1 3 4 5 2 6 7 8
p⁴: 1 2 3 4 5 8 6 7
p⁵: 1 5 2 3 4 7 8 6
p⁶: 1 4 5 2 3 6 7 8
p⁷: 1 3 4 5 2 8 6 7
p⁸: 1 2 3 4 5 7 8 6
p⁹: 1 5 2 3 4 3 6 7 8
p¹⁰: 1 4 5 2 3 8 6 7
p¹¹: 1 3 4 5 2 7 8 6
p¹²: 1 2 3 4 5 6 7 8

Deci raspunsul e 12.

[•andrici_cezar]

asta am mai vazut pe acest forum dar p si k ce inseamna mai exact?
sau mai bine zimi cum ai facut prima permutare ca poate inteleg asa:D

[•Mishu91]

p reprezinta permutarea, iar k puterea ei

P^k(i) =
    * P(i), atunci cand k=1
    * P(P^k-1(i)), pentru k > 1

Pt testul 2 de exemplu p²(1) = p(p(1)) = p(2) = 3

[•andrici_cezar]

aha ms

[•lsorin_94]

poate sa imi spuna cnva ce ins bijectiva:?

[•gabitzish1]

http://airinei.omad.ro/catmate/2FUNCTIA%20PUTERE%20CU%20EXPONENT%20NATURAL.pdf

De ce nu cauti pe google? Ai gasi mai multe informatii. 

[•Alexa_ioana_14]

Am retinut intr-un vect v nr de poz dupa care se repta elementul i, si daca perioada a mai fost gasita o ignor.Am calculat cmmmc dupa formula: cmmmc=v[1]*...*v[ultimul element]/cmmdc si iau pe majoritatea testelor wa. Am incercat si cu numere mari. Are cineva idee unde busesc sursa? 

Ps:Multumesc anticipat!