Problem sa checkerom - Ciklično pomeranje za K mesta ulevo (Zbirka)

Kod se može naći na sledećem linku: http://cpp.sh/5ogs
Kada je prisutno #include <algorithm> dobija se TLE samo na 9. testu, a kada se izbaci dobija se TLE na testovima 4, 6, 7, 8, 9.

Ne bi bilo loše pokazati ulazne vrednosti sa kojima testirate, a ujedno i izlazne vrednosti koje kompajlirani program ispisuje. Tako da ko god ima problem može da reši problem “pešaka”, bez potrebe da se svaki put otvara tema kada nešto ne valja (bilo da li je u pitanju checker, ili kod programa).

(https://petlja.org/BubbleBee/r/problemi/Zbirka/ciklicko_pomeranje_za_k_mesta_ulevo)
Zdravo,

Ovde nema nikakvih problema sa checkerom. Pretpostavljam da <algorithm> overriduje odredjena default ponasanja i da je zbog toga brze. Ali u svakom slucaju mislim da je TLE ocekivano za ovo resenje. Pogledacu jos malo dublje sta to tacno biblioteka overriduje u ovom kodu pa se izvrsava brze.

Ne razmatramo potpuno otvaranje test primera. Zato sto je debugovanje sastavan deo programiranja i vazno je nauciti kako treba da se radi. Kada dobijas TLE, probaj da generises veliki primer s obzirom da su ti data gornja ogranicenja. Dakle, u ovom slucaju primer sa N = 100k k = 100k i random brojevima. Tvoje resenje ce ovaj primer izvrsavati mozda i nekoliko minuta, zavisi od racunara.

Ako nisi upoznat, pogledaj Složenost algoritama
Kolika je vremenska slozenost tvog koda? Da li je to dovoljno dobro za ovaj zadatak? To su neka od pitanja na koja treba da odgovoris :slight_smile:

Jasno nam je da ako se greska pojavi i u jednom zadatku, svako ko se duze muci sa zadatkom ce pomisliti da i tu postoji greska. Radimo na tome da sto pre detektujemo i uklonimo sve greske. Do tada, Algora je pravo mesto da resite dilemu da li je zadatak ispravan ili ne u najkracem roku.

Hvala na odgovoru!

U pravu si, o tome nisam razmišljao. Neefikasno je ponavljati K puta std::rotate funkciju kada je K veliki broj.
Uzeo sam nove C++ standarde “zdravo za gotovo” :sweat_smile:

Zanima me da li ima na forumu neki post koji objašnjava koja su sve moguća izlazna rešenja zajedno sa njihovim značenjima (WA, TLE, …)?

Rešio sam zadatak. Dodao sam if grananje u slučaju kada je k < n i tu sam refaktorisao for petlju u std::rotate( elements.begin(), elements.begin() + k, elements.end() );
U ostalim slučajevima se koristi for petlja.
Bez grananja dobija se OK na svim testovima sem na prvom, gde se dobija WA, iako su ispunjena vremenska i memorijska ograničenja.

Barem sada znam da nije bitna čitkost koda i da se sledeći put neću uzdati u standard :slight_smile:

Bilo bi dobro kada bi imali mogucnost da vidimo kodove drugih korisnika nakon sto dobijemo OK. Ne znam koliko je to na petlji lako/tesko implementirati ali bi bilo dosta korisno. Postoji li sansa da ubacite tu opciju?

Razmotricemo tu opciju.

Licno mislim da je dobra ideja :slight_smile:

Čini mi se da si izvukao potpuno pogrešan zaključak. Čitljivost koda možda nije presudna u takmičarskom programiranju (jer se jedino ocenjuju test primeri), ali ako kod pišeš nečitko teško da ćeš se sam snaći u većim zadacima, tako da svakako treba uvek da obraćaš pažnju na čitljivost. Takođe, ne znam kako si izvukao zaključak da je ovde u pitanju bilo kakav problem sa standardom. Jedini razlog zašto si dobio TLE je to što si koristio loš algoritam (to je isto kao da x i y sabirao tako što bi u petlji y puta na x dodavao 1) i nema nikakve veze ni sa čitljivošću ni sa jezikom i njegovim standardom. Inače, veoma interesantno za ovaj zadatak je to što imamo njegovih 10 različitih rešenja :slight_smile: Jedno (najlepše) je to koje koristi bibliotečku funkciju std::rotate, međutim, ono je algoritamski najmanje ilustrativno. Ako hoćeš da vežbaš, moj ti je savet da probaš da pronađeš bar još tri različita rešenja ovog zadatka “peške” (pokušaj da zadržiš dobru vremensku složenost, i da izbegneš korišćenje dodatne memorije).

1 Like

Još jedna mala napomena. Za sve zadatke u Zbirci dovoljno je koristiti tipove int, double, string i bool. U drugom tomu koji se priprema bice potreban jos i long long. Izlete u int32_t i uintptr_t nije potrebno praviti.

Jesam, što sam tek shvatio kada mi je @Delta003 odgovorio. Uvideo sam da je greška u mom pristupu algoritmima, sa kojima sam imao relativno malo iskustva i shvatio da moram pročitati “Uvod u algoritme”.

Nisam se dovoljno jasno izrazio po pitanju standarda. Na brzinu sam pročitao par primera i objašnjenje sa http://en.cppreference.com/w/cpp/algorithm/rotate i mislio sam da će samo zameniti mesta dva elementa, a ne pointer do njih.

Što se tiče tipova, znam da se ne moraju koristiti u zbirci, ali su mi ušli u naviku :smiley:

Da ne otvaram novu temu, imam problem sa checkerom na zadatku


Daje RTE, čak i za praznu main()

Hvala! Vec smo upoznati sa ovim problemom!

Nema veze sa ovim zadatkom. Grader daje RTE kad god korisnicki kod ne napravi nikakav izlaz.