infoarena

Aici se pot pune întrebări legate de problema Move de la Runda 3 a concursului Algoritmiada 2013.

Timpul alocat întrebărilor este de 1 ora dupa inceperea concursului. Întrebările vor fi formulate astfel încât să se poată răspunde cu DA sau NU. În caz contrar sau în cazul în care întrebarea își găsește răspuns în enunțul problemei, răspunsul va fi FARA COMENTARII.

Cum adica "Pentru ca o operatie move(a, b) sa fie considerata valida, trebuie ca a != b"?Inseamna ca nu pot sa il mut pe 2 imediat dupa pozitia 2,adica pe 3?

Numerele sunt intre 1 si N?

NO COMMENT. E foarte clar.


Din moment ce se da o PERMUTARE tu ce crezi?

operatiile de tip MOVE sunt incluse in limbajul c si c++ in <cmath>/<cmath.h> ?

edit: nu mai am nevoie de un raspuns

Cum se facea problema asta?

Problema e foarte asemanatoare cu asta: http://codeforces.com/contest/270/problem/D, diferenta fiind ca aici trebuie sa afisezi si operatiile propriuzise.
Pentru ca numarul de operatii sa fie minim, incerci sa alegi un subsir cat mai lung a.i. elementele din el sa poata ramane la pozitiile lor si sa nu trebuiasca mutate (adica sa fie deja in ordine crescatoare), ceea ce coincide cu gasirea celui mai lung subsir crescator. Astfel ca numarul minim de mutari este egal cu N - L, unde L = lungimea celui mai lung subsir crescator.
Pentru a determina operatiile, se introduc intr-un vector toate valorile care nu fac parte din subsirul crescator maximal (adica valori care trebuiesc mutate de la pozitiile lor), si se parcurg in ordine crescatoare (ar trebui sa functioneze si o parcurgere in ordinea in care apar). Pentru fiecare valoare VAL, ea trebuie mutata la dreapta valorii VAL-1, astfel ca fiecare operatie este de forma "VAL VAL-1". Complexitatea finala O(N log N). Sper ca ti-am fost de ajutor!

Multumesc pentru ajutor!Am luat 100.Totusi nu mergea sa afisezi operatiile in ce ordine vrei.Trebuiau afisate neaparat in ordine crescatoare:D

Da, trebuie afisate in ordinea crescatoare a valorii lor, deoarece mutarea elementului VAL in dreapta elementului VAL-1 implica automat ca elementul VAL-1 sa fie amplasat corect, si asta nu-i neaparat adevarat daca nu tii cont de ordine...