015 Permutari II

[•Mishu91]

Încearcă să calculezi după o formulă de genul cmmmc(...cmmmc(cmmmc(v[ 1 ], v[ 2 ]), v[ 3 ])... v[ N ]). Pentru că produsul v[ 1 ] * v[ 2 ] * v[ 3 ] * ... * v[ N ] e posibil să iasă din long long.

[•zeroblitz36]

1   0ms   244kb   Corect!   5
2   0ms   8kb   Corect!   5
3   0ms   16kb   Corect!   5
4   0ms   12kb   Corect!   5
5   8ms   12kb   Corect!   5
6   0ms   12kb   Corect!   5
7   0ms   12kb   Corect!   5
8   0ms   12kb   Corect!   5
9   0ms   8kb   Corect!   5
10   4ms   260kb   Corect!   5
11   0ms   8kb   Corect!   5
12   4ms   8kb   Corect!   5
13   4ms   12kb   Corect!   5
14   0ms   8kb   Corect!   5
15   4ms   16kb   Corect!   5
16   0ms   8kb   Corect!   5
17   0ms   12kb   Corect!   5
18   0ms   12kb   Corect!   5
19   4ms   8kb   Corect!   5
20   0ms   8kb   Corect!   5
Punctaj total   100
Moamah ce noroc, cred ca are complexitate O(log n)

[•Alexandru13]

Cod:

int valid(int k)
{	
	for(int j=1;j<=k;j++)
		if(p[j]!=j)
			return 0;
	return 1;
}
int main()
{
	f>>n;
	for(i=1;i<=n;i++)
		f>>p[i];
	for(;valid(n)==0;nr++)
	{
		for(i=1;i<=n;i++)
			p[i]=p[p[i]];
	}
	g<<nr;
	g.close();
	f.close();
	return 0;
}

ma poate ajuta cineva..
nu imi dau seama cu ce am gresit.

[•SpiderMan]

Nu am vazut sursa trimisa, cat ai luat cu ea. Iti da bine pe exemple ?

[•Alexandru13]

nici nu am trimis sursa. imi intra in bucla... nu imi da nici un rezultat si nu stiu cum sa fac, nu inteleg greseala.

[•ctlin04]

Dati cineva ceva indicii pentru determinarea ciclului fiecarui numar in O ( n ), am citit postul lui Adrian, dar nu-mi dau seama cum pot sa marchez undeva ceva, eu generez toate permutarile pe rind pina cind toate numerele nu s-au repetat cel putin odata, apoi fac cmmmc dintre ciclurile determinate, si astfel iau TLE la testele 1,5 si 10, pls, help

[•Steve]

Edit: Ia un vector binar pana la N pe care il initializezei cu 0. cand ajunge elementul pe pozitia pe care vrei, marchezi in vectorul binar. Daca mai ai nevoie de ajutor PM! O(N)  
Sper ca n-am zis prea mult sry 

[•ctlin04]

Ms mult Stefan, am prins ideea 

[•VisuianMihai]

nu inteleg la al treilea exemplu... care sunt permutarile

[•SpiderMan]

FA ca la mate pe foaie si o sa vezi .

[•gabitzish1]

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.

E bine sa citesti prima data ce s'a mai postat pe un anumit subiect, poate nu mai e nevoie sa intrebi.

[•granny]

Salut tuturor , stiu ca e cam tarziu sa discut despre aceasta problema , dar nu pot intelege dc scot decat 90 puncte si  nu inteleg ce pot sa mai fac.. am observat ciclul pe ex 3 , am facut asa si nu imi da 100.. imi da ca am depasit limita de timp la test 1 si test 10.. am calculat gradele si le-am pus intr-un vector. si am facut cmmmc apoi.. aveti vreun sfat?

[•Trixer]

  va rog vrumos explicati-mi si mie ce vrea enuntul asta de la mine, nu inteleg deloc.
spune la exemplul 1 ca solutia este k=1 iar in enunt spune ca Pk(i) = p(i) pentru ca k=1, deci rezulta p(1)=2; p(2)=3; p(3)=4... nu inteleg nimic

[•DorelBarbu]

Salut! Sunt nou aici. Am incercat si eu sa rezolv aceasta problema. Rezolvarea am gasit-o singur, insa am probleme cu implementarea. Pe sursa mea obtin 30 pct. Am mers pe urmatoarea idee. Am creat un vector vp, in care vp retine o valoare, care arata la cate repetitii apare cifra i pe pozitia i. Dupa care am facut cmmc-ul tuturor valorilor din acest vector. Sunt constient ca implementarea mea, nu este cea mai buna ( si este departe de a o putea numi  macar "buna"), si de aceea va cer ajutorul.

Cod:

#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
int n;
int v[100000],v2[10000],vp[100000];
void citeste()
{
    freopen("perm2.in","r",stdin);
    scanf("%d",&n);
    int i;
    for(i=1; i<=n; i++) scanf("%d",&v[i]);
}
int completeaza(int k,int i)
{
    if(k==1) return v[i];
    else return v[completeaza(k-1,i)];
}
bool verifica(int j)
{
    if(v2[j]!=j) return false;
    return true;
}
int cmmdc(int a, int b)
{
    int c;
    while (b)
    {
        c=a%b;
        a=b;
        b=c;
    }
    return a;
}
int calculeazacmmmc()
{
    int a=1,b=1,m,cmmc,i;
    a=vp[1];
    b=vp[2];
    m=cmmdc(a,b);
    cmmc=a*b/m;
    a=cmmc;

    for(i=3; i<=n; i++)
    {
        b=vp[i];
        m=cmmdc(a,b);
        cmmc=a*b/m;
        a=cmmc;
    }

    return cmmc;
}

int main()
{
    ofstream out("perm2.out");
    citeste();
    int i=0,j,a=1,b=1,nrc;
    j=n+1;
    for(j=1; j<=n; j++)
    {
        while(verifica(j)==false)
        {
            i++;
            v2[j]=completeaza(i,j);
        }
        vp[j]=i;
        i=0;
    }

    out<<calculeazacmmmc();
    return 0;

}

M-ati putea ajuta, va rog? Multumesc anticipat!

[•danalex97]

La tine nu implementarea este problema , ci ideea de rezolvare.  Algoritmul tau lucreaza prea incet pentru ca faci de mai multe ori acelasi lucru. Ia un sir in care cand ajunge elementul pe pozitia pe care vrei il marchezi. Succes ! 

[•DorelBarbu]

Deci, prin secventa asta de cod, nu fac ceea ce ai zis tu?:

Cod:

 for(j=1; j<=n; j++)
    {
        while(verifica(j)==false)
        {
            i++;
            v2[j]=completeaza(i,j);
        }
        vp[j]=i;
        i=0;
    }

Adica, de ce fac de prea multe ori acelasi lucru? Trec prin fiecare pozitie, o data, pentru a plasa acolo elementul corespunzator. La sfarsit calculez cmmc-ul. Scuza-ma, dar cred (sunt aproape sigur), ca nu am inteles prea bine ce ai vrut sa spui. Ai putea, te rog, sa fii putin mai detaliat (nu vreau mura in gura!!!)? Multumesc!

[•TwistedFaith]

Killed by signal 11(SIGSEGV). la toate testele.

[•SebiSebi]

Declara tablourile in afara main-ului. Succes! 

[•TwistedFaith]

Eu am declarat vectorii asa:
int n;  fin>>n;
int v[2][n],k[n/2+3];
pt ca sa mananc cat mai putin spatiu. Daca ar fi sa ii declar in afara main ar trebui sa le dau 20000, respectiv v[2][20000] (1 rand pentru permutare si 1 pentru verificare/marcare) si k[10000] (pt a pune lungimea ciclilor in el).

[•SebiSebi]

Asa ii declari. Compilatorul oricum calculeaza doar cat folosesti. Deci, nu pierzi memorie.

[•DxH5dIMHN]

Câţi? 15! Ce 15? Ce câţi?

perm2.in
21
12 3 16 5 19 8 21 14 18 10 4 17 1 11 2 20 6 13 7 15 9

perm2.out
15

46 de linii de cod -> punctaj total: 100 

[•Daniel_Bot]

+1 pentru ideea lui DITzoneC

[•DorelBarbu]

Ar  putea cineva sa detalieze putin chichita? Cunosc notiunea de ciclu al unei permutari. Am reusit sa obtin 80 de puncte, intelegand ca algoritmul meu era infeicient, si imbunatatindu-l, facand cateva mici retusuri. Dar pic testele 1,5,10,12. Ma poate ajuta cineva?

[•vld7]

Tu in functia in care completezi matricea gasesti pentru fiecare element i un numar c[ i ] astfel incat permutarea la puterea c[ i ] sa aiba elementul i pe pozitia corespunzatoare. Nu e necesar sa verifici la toate pentru ca ciclul unei permutari iti da pentru toate elementele care-l alcatuiesc acel c[ i ]. Daca ai de exemplu ciclul (1, 3, 4) ridicand la putere vei avea 1 -> 3 -> 4 -> 1 deci {1, 3, 4} vor fi pe pozitiile 1, 3 si 4 in p^3, p^6 etc.

[•DorelBarbu]

Iti multumesc frumos pentru ajutor! Am reusit si eu sa iau 100 de puncte. Multumesc din nou! Spor la rezolvat!