infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: ditzone din Octombrie 15, 2006, 21:25:52

Titlul: 278 Swap
Scris de: ditzone din Octombrie 15, 2006, 21:25:52

Aici puteÅ£i discuta despre problema Swap (http://infoarena.ro/problema/swap).

Titlul: Raspuns: 278 Swap
Scris de: Sima Mihai Cotizo -vechi din Octombrie 17, 2006, 08:45:28

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

Titlul: Raspuns: 278 Swap
Scris de: Bogdan-Cristian Tataroiu din Octombrie 17, 2006, 10:37:06

Sau mai simplu de implementat cu AIBuri

Titlul: Raspuns: 278 Swap
Scris de: Rimovecz Ioan Mihai din Octombrie 17, 2006, 12:41:47

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

Titlul: Raspuns: 278 Swap
Scris de: Andrei Homorodean din Octombrie 17, 2006, 14:23:50

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

Titlul: Raspuns: 278 Swap
Scris de: Bogdan-Cristian Tataroiu din Octombrie 17, 2006, 17:41:14

Citat din mesajul lui: rmikeweb din Octombrie 17, 2006, 12:41:47

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... ???

Titlul: Raspuns: 278 Swap
Scris de: David si Goliat din Octombrie 24, 2006, 21:17:27

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

Citat

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

Titlul: Raspuns: 278 Swap
Scris de: Bogdan-Alexandru Stoica din Octombrie 24, 2006, 21:33:00

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)

Titlul: Raspuns: 278 Swap
Scris de: David si Goliat din Octombrie 24, 2006, 21:50:19

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;}

Titlul: Raspuns: 278 Swap
Scris de: Bogdan-Alexandru Stoica din Octombrie 24, 2006, 22:16:50

Citat din mesajul lui: C.Ovidiu din Octombrie 24, 2006, 21:50:19

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 :D

Titlul: Raspuns: 278 Swap
Scris de: David si Goliat din Octombrie 24, 2006, 22:19:26

O cautare binara ar fi mai folositoare ? ???

Titlul: Raspuns: 278 Swap
Scris de: Bogdan-Alexandru Stoica din Octombrie 24, 2006, 22:27:45

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 :P

Titlul: Raspuns: 278 Swap
Scris de: Sima Mihai Cotizo -vechi din Octombrie 29, 2006, 14:59:15

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? :aha:

Titlul: Raspuns: 278 Swap
Scris de: ditzone din Octombrie 29, 2006, 21:08:29

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

Titlul: RÄƒspuns: 278 Swap
Scris de: Mihai Leonte din August 31, 2007, 10:44:46

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. :-k

Titlul: RÄƒspuns: Raspuns: 278 Swap
Scris de: Dragos din Iunie 07, 2010, 14:19:40

Citat din mesajul lui: David si Goliat din Octombrie 24, 2006, 21:50:19

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!

Titlul: RÄƒspuns: 278 Swap
Scris de: Dragos-Alin Rotaru din Iunie 07, 2010, 19:48:18

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);

Titlul: RÄƒspuns: 278 Swap
Scris de: Dan H Alexandru din Iulie 30, 2012, 12:23:37

Citat din mesajul lui: Adrian Scoica din August 31, 2007, 10:44:46

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

Titlul: RÄƒspuns: 278 Swap
Scris de: Bogdan Ciobanu din Octombrie 05, 2015, 10:57:46

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 (http://www.infoarena.ro/job_detail/1496609), are timpul de executie mult mai mic decat cea in care afisez rezultatul (http://www.infoarena.ro/job_detail/1496610).

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.

Titlul: RÄƒspuns: 278 Swap
Scris de: Mircea Dima din Octombrie 05, 2015, 12:44:21

Citat din mesajul lui: Bogdan Ciobanu din Octombrie 05, 2015, 10:57:46

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

Titlul: RÄƒspuns: 278 Swap
Scris de: Vintur Cristian din Octombrie 05, 2015, 17:04:50

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 (http://www.infoarena.ro/job_detail/1496861)

Multumesc.