278 Swap

[ditzone]

Aici puteţi discuta despre problema Swap.

[•Coty]

Nu e mult O(N^N)  Se poate O(N log N)   cu arbori de intervale.

[•bogdan2412]

Sau mai simplu de implementat cu AIBuri

[•rmikeweb]

Da NlogN e solutia.Eu am facut cu un arbore de intervale si o lista dublu inlantuita si am luat doar 50p

[•peanutz]

Hmm, grafuri... inca nu m-am prea apucat de asa ceva... Cred ca e cazul.. merci

[•bogdan2412]

Da NlogN e solutia.Eu am facut cu un arbore de intervale si o lista dublu inlantuita si am luat doar 50p

Tu ai luat Wrong Answer, nu TLE... nu ai luat 50 pct pt ca nu e buna complexitatea... ai tu o greseala in program... 

[•pocaitu]

  Am luat 40 de pct cu AIB-uri . Restul TLE . Are ceva daca inainte de program am scris asta pt a simplifica problema ??
  .
 

strcpy(s3,s1);
 strcpy(s1,"2");
 strcat(s1,s3);
 strcpy(s3,s2);
 strcpy(s2,"2");
 strcat(s2,s3);
 

[•fireatmyself]

nu cred ca are ceva, dar, pt orice eventualitate, scoate acele 6 linii si trimite sursa modificata chiar daca nu da raspunsul corect. in cazul in care si atunci iei TLE inseamna ca ai un bug in algoritm (iti cicleaza pe undeva sau nu ai facut n log n)

[•pocaitu]

    Am restructurat algoritmul . Nu sunt liniile alea problema . 
  Postez aici codul daca vrea cineva sa ma ajute . Dupa aceea il sterg daca ceva

Cod:

int main()
{ifstream f("swap.in");
 f>>s1>>s2;
 n=strlen(s1);
 ofstream g("swap.out");
 strcpy(s3,s1); strcpy(s1,"2"); strcat(s1,s3); strcpy(s3,s2); strcpy(s2,"2"); strcat(s2,s3);
 for(i=1;i<=n;++i)
   {poz=strchr(s1,s2[i])-s1;
     s1[poz]='1';
     k[poz]=i;
     }
 ...
 return 0;}

[•fireatmyself]

Cod:

....
 for(i=1;i<=n;++i)
   {poz=strchr(s1,s2[i])-s1;
     s1[poz]='1';
     k[poz]=i;
     }
....

aici e problema... bucata asta e cam O(n^2). incearca sa faci altfel renumerotarea pozitiilor 

[•pocaitu]

O cautare binara ar fi mai folositoare ? 

[•fireatmyself]

errr... pai retine intr-o matrice cu 26 de coloane (sa o numim A) pt fiecare litera de la 'a' la 'z' pozitiile pe care acestea se gasesc in s1. apoi, cand ai trecut la al doilea sir si esti la pozitia i, trebuie sa retii cate litere de s2[ i ] ai mai intalnit in sirul s2 (fie acest nr X) pana la acea pozitie si numerotezi litera respectiva cu A[ s2[ i ]-'a' ][X] (a X-a aparitie a lui s2[ i ] in sirul s1). sper sa intelegi ceva din balbele mele

Last edit: ti-am scos eu partea importanta din cod... sa nu te panichezi

[•Coty]

In concurs am luat 100 la prob. asta, cand am retrimis am luat 6 TLE ... ati modificat limita? ... sau sunt eu cam batut in cap si am uitat sursa la scoala? 

[ditzone]

Limita de timp e aceeasi ca in timpul concursului...

[•MarcvsHdr]

Eu am facut O(NlogN) si am luat 100, dar ma intrebam... SIGUR nu se poate O(N)? Era problema aia... camion sau cum se numea... de la campion, in care se intampla ceva asemanator, doar ca lua operatiile in ordine inversa. 

[•APOCALYPTO]

 

Cod:

int main()
{ifstream f("swap.in");
 f>>s1>>s2;
 n=strlen(s1);
 

Salut!
 Imi aratati si mie va rog cum ati facut citirea. Vrea sa invat mai multe metode ca sa-mi fie mai usor cand codez.

Multumesc anticipat!

[•mathboy]

Uite aici citirea mea :

Cod:

        freopen ("swap.in", "r", stdin);
	freopen ("swap.out", "w", stdout);
	scanf ("%s%s\n", a, b);
	n = strlen (a); m = strlen (b);

[•danalex97]

Eu am facut O(NlogN) si am luat 100, dar ma intrebam... SIGUR nu se poate O(N)? Era problema aia... camion sau cum se numea... de la campion, in care se intampla ceva asemanator, doar ca lua operatiile in ordine inversa. 

Sigur nu se poate. Metoda O(N lg N) are la baza metoda greedy.

[•bciobanu]

Buna ziua, am o sursa in O(nlogn) care ia 80p cu TLE pe 2 teste. Nu imi pot explica de ce o sursa in care calculez rezultatul, dar nu il afisez, are timpul de executie mult mai mic decat cea in care afisez rezultatul.

LE: Imi imaginez ca toata secventa de calcul a rezultatului a fost optimizata de compilator (pentru ca nu il mai foloseam dupa), dar intrebarea ramane deschisa: ce trebuie sa modific pentru a se incadra in timp?

LLE: Am luat 100 cu mergesort modificat, se descurca mult mai bine decat AIB-urile pentru aceasta problema.

[•blasterz]

LLE: Am luat 100 cu mergesort modificat, se descurca mult mai bine decat AIB-urile pentru aceasta problema.

Nu cred ca "se descurca mult mai bine". Eu am 100 cu 12ms cu AIB... Poate faci tu ceva aiurea sau iti intra in bucla infinita

[•Cristian1997]

Daca ai spus ca ai luat 100p cu AIB si timp de 12ms, ai putea te rog sa-mi spui ce sa mai optimizez la codul meu, ca nu reusesc sa iau testul 8.

http://www.infoarena.ro/job_detail/1496861

Multumesc.