Si ce nu stii ? In ce mediu lucrezi ?

Am inteles chestia asta si faptul ca complexitatea dorita era de N², chiar daca nu s-a gasit una mai buna ca N³, dar am intrebat pentru ca eram curios daca o s-o refaca, sau .... nu.
[LE] Merci George, mi-ai luat-o inainte.

Pana la urma, cu 2stacks ce faceti ?

Mai bine iti folosesti timpul rezolvand (doar) probleme grele. Asa progresezi cel mai mult.

Am inteles, eu doar intrebam  .

Acum ca va fi XOR 2013, pot sa adaug pb. de la XOR 2012 ? Merita ?

Am banuit ca el a intrebat asta pt. a rula o sursa, eu i-am spus ca poate sa faca asta fara sa se complice cu proiect. De ce trebuie de fiecare data cineva sa se bage, fara macar sa stie de ce am zis eu anumite chestii. Daca era deplasat, zicea Ieronim ceva in legatura cu asta.

Poti sa compilezi si sa rulezi programe fara sa faci proiecte, CodeBlocks iti permite asta.

Problema camera, dupa care este inspirata, construieste, la fel ca asta, un asa-zis "poligon" care contine toate pct. solutie. Eu initial bag in vectorul solutie tot planul, si pe parcurs il tot diminuez, luand intersectia cu mediana a 2 puncte fixate i, j, de partea lui i, cu i < j. Dar, vazand alte surse, chiar si a unui prieten de-al meu care lua 90 cu KBS 11 pe testul 1, adica cel fara solutie, am sters din sursa tot algoritmul, ramanand doar cu initializarile, si cu afisarile. Acea sursa lua in continuare 90 puncte (uita-te la sursele mele de pe cont_de_Teste de 90, resp. de 100, fara ultimele ca alea-s corecte), si o sa vezi ce rezultate aiurea dau, chiar si pentru exemplu). Sper ca ai inteles ce-am vrut sa zic, finalul este ca acest "vector" este NULL, si in acest caz imi afiseaza 2 numere mari (infinituri si -infinituri), care cu siguranta nu ar trebui sa constituie solutia buna.
[LE] Despre aceasta sursa vorbeam, cea din care am sters aproape tot algoritmul, si care ia 90 puncte (fara testul 1).

FF. Slabe testele la problema. Luam 100 chiar daca nu avem niciun punct pe poligonul solutie.

Dupa cum zicea steve, rezultatul este dat de max * 2, unde max este elementul maxim din vector. Daca afisai pozmax pozmax max * 2, atunci luai 90 cu un incorect, si ca sa iei 100, trebuie sa iei cea mai lunga secventa care cuprinde elemente maxime, pentru ca-ti cere solutia cu i-ul minim si j-ul maxim. Pentru exemplul :

Cod:

2 2 2 1

Rezultatul o sa fie 1 3 4, nu 1 1 4, cum ai fi facut altfel, pentru ca 1 3 are j-ul mai mare ca si 1 1. Sper ca ti-a fost de folos .

E ok limita de timp la aceasta problema ? Se poate uita cineva cu o sursa de 100 ?
[LE] Am rezolvat, am optimizat-o de o luat-o ameteala, am scos 12 ms pe testul ala naspa  .

Ce tot are site-ul, cand ti-e lumea mai draga el nu mai merge deloc.

Am rezolvat, acuma iau 50 pct. cu TLE.
[LE] Gata, merci fain.

Nu inteleg intrebarea. Adica eu construiesc lista vector <int> G[MAX_M], unde MAX_M = numarul minim maxim, care este 5000 in acest caz, si apoi fac dijkstra pe acest graf. Dar se pare ca lista asta devine cam "voluminoasa" la un moment dat, si nu stiu ce sa fac.

Iau 20 cu MLE, cum pot optimiza memoria, eu construiesc graful exact ca in solutie, dar sunt relativ cam multe muchii.

Numerele mari nu ar fi ok in arhiva ? Si asa se folosesc din ce in ce mai des.
BTW daca nu poate Petru pun eu in arhiva aria unui poligon.

Eroare de compilare in evaluator, sa refaca un admin evaluatorul.

E ok, as putea adauga si cele de clasa a 9-a, daca un admin este prin apropiere ....

E prea stransa limita, 0.2 ar fi ok. Am retrimis sursa si altele de 100, si nu iau 100, doar 80.

Am inteles, daca fac unordered_set, fara tr1/ in fata, desi includ namespace-ul tr1, imi apare aceeasi eroare de la C++11, ca mai sus. Si in legatura cu array-urile, daca am program asa :

Cod:

1 <= N <= 10000
1 <= M <= 10000
int ch[MAX_N][MAX_M];
// sau asa
vector < vector <int> > (N + 1, vector <int> (M + 1));

Ramane la fel viteza, pentru ca eu il declar acum ca fiind cu un numar fix de elemente. Si inca ceva, din cate am inteles, push_back-ul redimensioneaza vectorul, facand-ul de dimensiunea puterilor lui 2. Se poate, daca am sa zicem un numar de elemente (nu stiu cate), si fac push_back, la final (sau nu stiu) sa fac ca acest vector sa fie fix, adica daca am citit 1000 elemente si el este de 1024 (putere a lui 2), sa fie de fix 1000, ca din cate am inteles resize nu elibereaza memoria, doar redimensioneaza vectorul.

Si inca 2 intrebari care ma framanta si cu asta am terminat : unordered_map este inlocuitorul lui hash_map (resp. _set), si daca da merge la olimpiada cu <tr1/un...> ? Si daca am un array mai mare, si vreau sa-l fac dinamic, la olimpiada sa nu-mi scada daca pun ch[MAX_N], in caz ca MAX_N este foarte mare, sau alte cazuri, se poate folosi vector <> declarat dinamic, pastrand viteza ?

Am vazut pe cplusplus.com noul C standard din 2011, dar care nu este pus pe compilatoare, e doar versiunea de test sau ceva gen. Are noi librarii, si noi functii, spre ex. <array> din STL. Daca includ acest header, compilerul imi spune asa :

Cod:

#ifndef _CXX0X_WARNING_H
#define _CXX0X_WARNING_H 1

#ifndef __GXX_EXPERIMENTAL_CXX0X__
#error This file requires compiler and library support for the \
ISO C++ 2011 standard. This support is currently experimental, and must be \
enabled with the -std=c++11 or -std=gnu++11 compiler options.
#endif

#endif

As fi curios cum pot sa fac sa activez acele "compiler options" si daca se poate pe infoarena.

As vrea sa postati aici oricine, chiar si adminii, daca ati gasit ceva probleme frumoase care nu sunt bagate in arhiva, si pe care le putem pune, cu acordul adminilor. Le pot pune eu, doar sa stiu daca sunt astfel de probleme.

Se blocheaza uneori evaluatorul, trebuie sa astepti pana se deblocheaza.

Aceasta problema a fost data la FII Competition 2011, problema safeu, Runda a 3-a (parca). Are si solutie oficiala, si de asemenea o solutie scoasa de colegul meu, Spatarel Dan, in complexitate mult mai mica .
[LE] Uite aici solutia.