Afişează mesaje
Pagini: [1] 2 3 ... 13
1  Comunitate - feedback, proiecte si distractie / Blog / Răspuns: Solutii la concursul acm 2013 etapa nationala partea a doua : Iunie 01, 2015, 21:47:37
Tu zici ca dacă ai avea nevoie de 3 ți l-ai putea crea. În algoritmul asta nu poți.  Deci ar trebui sa arăți ca nu ai nevoie...
În cazul 7 soluțiile considerate sunt
1 2 3 6 7
1 2 3 5 7
1 2 4 6 7
1 2 4 8 7
2  Comunitate - feedback, proiecte si distractie / Blog / Răspuns: Solutii la concursul acm 2013 etapa nationala partea a doua : Iunie 01, 2015, 12:32:55
Salut!
La problema Power Calculus, de ce ajunge sa expandam doar nodurile care au distanta minima pana la ele egala cu distanta minima pana la ultimul numar generat?

De exemplu:
1 2 3
1 2 4
sunt noduri care se genereaza, dar
1 2 3 4
nu se genereaza, pentru ca are costul trei, iar ultimul numar generat(4) poate fi obtinut cu cost 2.

Adica, nu e posibil sa existe vreun nod de genul 1 2 3 4 din care sa se obtina cu cost minim alt numar? In cazul asta 7 ar fi numarul, dar 7 se obtine de exemplu din 1 2 3 6, care e e un nod generat, deci pentru 7 e ok. Cum demonstram ca e ok pt toate numerele?

Mersi.
3  infoarena - concursuri, probleme, evaluator, articole / Arhiva educationala / Răspuns: 016 Range minimum query : Mai 26, 2015, 11:30:30
Cu solutia in complexitate sqrt(N) se poate lua 70p (in loc de 40p), daca se calculeaza pentru fiecare pozitie i din sir, minimul pe intervalul [i, i + sqrt(n) - 1]. Asta se poate face in O(N), folosind solutia de la problema deque. Apoi pentru a afla raspunsul la un query se merge prin vectorul calculat, prin pozitiile x, x + sqrt(n), ... atata cat e posibil, apoi se parcurg restul(maxim sqrt(N)), element cu element. Are aceeasi complexitate, dar la query se fac 2*sqrt(N) in loc de 3*sqrt(N) operatii, in cel mai rau caz. O solutie se gaseste aici(nu am implementat neaparat frumos).
4  infoarena - concursuri, probleme, evaluator, articole / Algoritmiada 2014 / Răspuns: Algoritmiada 2014 Runda Finala : Septembrie 29, 2014, 10:37:37
Adaugati, va rog, problemele de la finala Algoritmiada si de la Infoarena Cup in arhiva?

Multumesc,
Ciprian.
5  infoarena - concursuri, probleme, evaluator, articole / Infoarena Monthly 2014 / Răspuns: Infoarena Monthly 2014, Runda 5 : Mai 29, 2014, 07:49:35
Am primit azi dimineata la 4 newsletterul infoarena - cica va veni infoarena monthly, runda 5, ieri la 19:00.  Thumb down
6  infoarena - concursuri, probleme, evaluator, articole / Arhiva ACM / Răspuns: 050 Becuriacm : Mai 21, 2014, 14:39:53
Aveti un hint pentru mine? Sau un contraexemplu pentru algoritmul pe care l-am incercat?

Am incercat asa:
1. Punem toate becurile care trebuie stinse in coada Q
2. Luam un bec B din Q(il eliminam din Q)
3. Daca e stins, atunci ne intoarcem la 2, daca e aprins, selectam un intrerupator I care comuta becul B(daca exista I astfel incat I nu a mai fost comutat, alegem un astfel de I - in caz de mai multe optiuni, luam un I oarecare; daca nu exista un I astfel incat sa nu mai fi fost comutat, alegem un I dintre cele care au fost comutate o singura data; daca nu exista I care sa nu fi fost comutat de mai mult de doua ori spunem ca nu este solutie).
4. Schimbam starea tuturor becurilor care sunt comutate de I. Daca aprindem un bec, atunci il adaugam la Q.
5. Daca Q e gol, gata. Daca nu, ne intoarcem la 2.

Mi se pare ca daca obtinem solutie, e corecta intotdeauna cu algoritmul asta. Se poate sa dea ca nu exista solutie si sa existe de fapt(eu asta banuiesc)? Sau am gresit la implementare?

Multumesc!
7  Comunitate - feedback, proiecte si distractie / Blog / Răspuns: Why is your bisection search wrong : Mai 19, 2014, 10:56:08
Sorry!

I didn't see that comment when I started writing my comment. Also, there are also other questions in my comment that I would like you to address besides that tomorrow.

Thank you and have a good night.

L.E.: It looks like in python it is called float(as in floating type), but it has the value range of C++'s double: [2.2250738585072014e-308, 1.7976931348623157e+308]. So it might be that in python there's, in fact, only "double".
8  Comunitate - feedback, proiecte si distractie / Blog / Răspuns: Why is your bisection search wrong : Mai 19, 2014, 10:47:12
Hello!

I have a few questions and observations.

First of all, when I first tried to solve this problem, instead of using the simple thing that you did for applying the algorithm to negative numbers, I tried to complicate things by using (-MAX, MAX) range. That was not such a good idea, but it led me to finding that lo + (hi - lo) might overflow too. Namely, if lo is low enough(and negative too) and hi is hi enough, then hi - lo will turn into an large number that could overflow. So hi - lo is good enough, if hi and lo are greater than or equal to 0. In general, always check the range of values that can occur as inputs and check whether the outputs and the intermediate values fit the type.

Second, could you please specify how do we compute that magic constant(120) that you used for the number of iterations? Are there any risks, if that number is too high (besides TLE, smth like roundoff errors)? As an example, my python interpreter shows 999999999999.3113 as a result for cubicRoot(1e36); the exact result would be 1e12. The difference is greater than 0.1

Third, who considered float is a good enough default type for real numbers?

How does this algorithm perform for really small, really large and really close too zero numbers(close to the limits of what the type can hold)?

Thanks!

L.E.: Just noticed the "Tomek" addition to the text. My C++ compiler says that 3.4028235e+038 is the max value for float(numeric_limits<float>::max()).
9  Comunitate - feedback, proiecte si distractie / Feedback infoarena / Răspuns: Bug reports : Septembrie 19, 2013, 23:22:43
Mi-a aparut urm chestie cand am intrat pe infoarena:
http://imgur.com/ns5X7Ye,EpsRfiD
10  infoarena - concursuri, probleme, evaluator, articole / Concursuri / Răspuns: ONI 2013 : Aprilie 12, 2013, 10:40:56
Poftiti parerea mea legata de un evaluator:

La olimpiada, elevii primesc niste probleme si treaba lor e sa gaseasca solutia si sa o implementeze intr-un limbaj de programare acceptat de olimpiada (C/C++/Pascal din cate stiu). Tot ce ar face un evaluator ar fi sa aduca mai mult ajutor pentru a produce o implementare cat mai corecta. Daca e bine sau nu, nu stiu. Dar ganditi-va asa: putem pune pe un slider nivelul de ajutor oferit elevilor la implementare. In partea stanga ar fi ajutor, undeva pe la deloc(poate un editor banal de text - notepad pe windows sau vi pe linux, fara compilator, fara syntax highlighting, fara Intellisense sau alte chestii). In partea dreapta ar fi extrem de mult ajutor(cele mai bune ide-uri pt implementare si generatoare de teste si tot ce va mai puteti imagina). Decizia de a pune un eval sau nu pe calcurile elevilor e pur si simplu o decizie de mutare a sliderului mai inspre dreapta. Bineinteles ca are si avantaje si dezavantaje(cititi mai in posturile precedente?). Ca si orice alt loc de pe slider. Tot ce trebuie decis e cat de mult ne intereseaza ca elevii sa petreaca mult timp pe maruntisuri de implementare vs. pe idei de rezolvare a problemelor.

Ganditi-va la firmele bune din industrie. Stiu ca nu se compara complexitatea proiectelor de acolo cu complexitatea proiectelor de la olimpiada, dar in industrie se incearca ca sa se foloseasca unelete cat mai bune pentru ca developerii sa fie cat mai productivi. Si se inevstesc o tona de bani pentru asta.

Legat de faptul ca unii elevi buni rateaza cate un rezultat la olimpiada din cauza unor greseli - eu cred ca aceste rateuri pot fi evitate oferindu-le mai multe incercari(care sunt sansele ca un elev bun sa buseasca de multe ori fata de o singura data?). Vrem ca la IOI sa mearga cei mai buni din tara, nu? Atunci trebuie sa le oferim cat mai multe sanse sa se afirme. De aceea, si eu cred ca mai multe zile pt lot sunt bune. Si, intrucat, drumul pana la proba de baraj poate fi blocat de o buseala, trebuie oferita si o alternativa pentru a ajunge la baraj. ONIByNet ar trebui sa fie o alternativa buna.

Legat de lipsa banilor - poate ar trebui cautate mai insistent surse de finantare pt ONI. Bani sunt, la fel si sponsori. Ganditi-va ca avem destule concursuri sponsorizate in tara: FII Competition, Adobe Code Pandas, Algoritmiada, Infoarena Cup, Monthly etc. Sa nu fie bani si pentru ONI?
11  Comunitate - feedback, proiecte si distractie / Feedback infoarena / Răspuns: Bug reports : Aprilie 12, 2013, 10:22:46
Problemele de la runda I de la Adobe Code Pandas nu au fost adaugate inca.
12  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: Be right back. : Aprilie 08, 2013, 21:56:53
Arhiva a revenit, dar lispecs cateva probleme.
13  infoarena - concursuri, probleme, evaluator, articole / Code Pandas / Răspuns: Cercetatori : Aprilie 05, 2013, 12:39:04
Se poate ca in fisierul de intrare sa existe un corp ceresc care are aceeasi pozitie in spatiu la momentul 0 cu corpul ceresc in jurul caruia oriteaza?
14  infoarena - concursuri, probleme, evaluator, articole / Code Pandas / Răspuns: 1381 Gradinarit : Martie 30, 2013, 11:09:50
In caz de egalitate a punctajelor, se va face departajare dupa timp?
Punctajele sunt ca la Monthly(scad o data cu trecerea timpului) sau sunt ca la alte concursuri infoarena(gen algoritmiada)?
15  infoarena - concursuri, probleme, evaluator, articole / Algoritmiada 2013 / Răspuns: Feedback Algoritmiada 2013, Runda 4 : Martie 24, 2013, 17:27:03
Mie mi-a placut problema lumanari. Genul de problema la care e foarte usor sa crezi ca ai solutia corecta - desi esti destul de departe. Am mai vazut pe topcoder ceva greedy-uri despre care ai jura ca sunt corecte, cand de fapt sunt total gresite si necesita de fapt ceva DP sau ceva cuplaje/fluxuri pe grafuri. Asta nu stiu cum se rezolva, dar sigur e ceva tare.
Legat de problema alianta - nu's genul care sa optimizeze back-uri. Asa ca nu prea mi-a placut. Desi ar trebui sa ma uit peste ca apar tot mai multe meet in middle.
La Rama am facut in O(n^3) si am luat 40p cu TLE pe restul. Cica se ia 100 cu O(n^3)   Cry
La radacina2 nu am apucat sa ma uit prea bine.

In total a fost bine si site-ul s-a descurcat acceptabil. Pacat ca anul asta nu vedem la finala!

Distractie la finala celor care s-au calificat si sa luati premii mari!
16  Comunitate - feedback, proiecte si distractie / Blog / Răspuns: Interactive problems shortlist : Martie 23, 2013, 12:55:09
I found my mistake:
Citat
If i1 <= i2 and j1 <= j2 then a[i1][j1] <= a[i2][j2]. Then the submatrix A[1...i][1...j] has the maximum element in A[ i ][j]. So we can binary search (i, j) such that all elements in A[1...i][1...j] are less than x and then binary search x on the i+1 and j + 1 line(column).

Once you find (i, j), x could be in any cell that hasn't got the coordinates less than (i, j).
17  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 1374 Ksecv3 : Martie 20, 2013, 15:55:15
Nu exista teste cu suma subsecventei de lungime > 2^32 si k mic.
18  Comunitate - feedback, proiecte si distractie / Blog / Răspuns: Interactive problems shortlist : Martie 16, 2013, 18:51:46
2. If we start from (1,n) we can only move either left or down => O(n+m)

If i1 <= i2 and j1 <= j2 then a[i1][j1] <= a[i2][j2]. Then the submatrix A[1...i][1...j] has the maximum element in A[ i ][j]. So we can binary search (i, j) such that all elements in A[1...i][1...j] are less than x and then binary search x on the i+1 and j + 1 line(column). That would be O(log n + log m).

L.E.: For the first binary search we can use middle =  ((left i + right i) / 2, (left j + right j) / 2)
19  infoarena - concursuri, probleme, evaluator, articole / .com 2012 / Răspuns: Aby : Martie 10, 2013, 16:03:34
Se cere caracterizarea personajelor?
20  Comunitate - feedback, proiecte si distractie / Off topic / Răspuns: OJI 2013: Cum sa ne asiguram ca ne calificam la nationala? : Martie 04, 2013, 08:47:53
Citat
Stai chill ca nimeni nu te judeca cu nimic.
Esti foarte comic  Rolling on the Floor Laughing

Am trecut de varsta la care sa imi pese de ce zic niste copii despre mine pe un forum.

Pur si simplu nu vad nicio legatura(sa nu mai zic de logica) intre ce discutati aici si subiectul topicului.
21  Comunitate - feedback, proiecte si distractie / Off topic / Răspuns: OJI 2013: Cum sa ne asiguram ca ne calificam la nationala? : Martie 03, 2013, 21:10:54
Stiu ca topicul asta e in off topic, dar voi ati luat-o razna rau de tot. Invatati putin autocontrol. Pana una alta sigur se gaseste vreun admin de forum sa inchida topicul asta. Il rog eu frumos!
22  infoarena - concursuri, probleme, evaluator, articole / Informatica / Răspuns: Something Weird : Februarie 15, 2013, 14:52:59
M-am grabit putin, dar eu iau doar 45p cu sursa ta: http://infoarena.ro/job_detail/879489?action=view-source
23  Comunitate - feedback, proiecte si distractie / Off topic / Răspuns: OJI 2013: Cum sa ne asiguram ca ne calificam la nationala? : Februarie 14, 2013, 22:03:22
Eu vroiam sa fie un post cu sfaturi pentru toata lumea - nu doar pt cei din Cluj. Poate ne impartasiti din "secretele" voastre?
24  Comunitate - feedback, proiecte si distractie / Off topic / OJI 2013: Cum sa ne asiguram ca ne calificam la nationala? : Februarie 13, 2013, 18:11:54
Sa presupunem ca sunt un elev in clasa a 10-a, destul de inteligent, care detine cunostintele teoretice necesare pentru a rezolva cu succes o problema de OJI de clasa a 10-a. De asemenea am rezolvat in jur de 100 de probleme de pe infoarena, o parte din ele fiind probleme de la OJI din anii trecuti. Totusi nu ma simt foarte comfortabil atunci cand ma apuc de o problema noua data la OJI la a 10-a in anii trecuti. Ce trebuie sa fac ca sa obtin maxim de puncte la OJI 2013 si sa ma calific la nationala? Cum imi optimizez pregatirea pentru scurtul timp ramas(2 saptamani jumate) pana la OJI?
25  infoarena - concursuri, probleme, evaluator, articole / Informatica / Evaluator Tucu Galatan: De ce nu se ruleaza executabilul? : Februarie 10, 2013, 14:20:05
Stie cineva de ce nu imi merge evaluatorul de aici: http://cnlr.ro/~tucu/ ?
Am Windows 7 si am instalat intai kitul de OJI linkat acolo, apoi evalul.
Dupa care l-am pornit si am creat o problema noua, am adaugat teste, surse...
Am compilat => un executabil.
La rulare imi da 0 puncte, dar fara niciun feedback pe teste.
Am incercat sa acord permisiuni de administrator, sa scot read-only de pe foldere - dar tot degeaba. Sugestii cineva?



L.E>: Nu stiu ce am facut exact - dar acuma merge. Am dat si un restart la calculator intre timp.
Pagini: [1] 2 3 ... 13
Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines