 Afişează mesaje
|
|
Pagini: [1] 2 3 ... 6
|
|
3
|
infoarena - concursuri, probleme, evaluator, articole / Informatica / Răspuns: Pseudocod bac
|
: Iulie 07, 2014, 15:28:35
|
Pentru corectori, structura pentru ... executa este de același tip cu cât timp ... executa?
Daca inlocuiesti (d<-2; cat timp d<=n executa {B; d<-d+1}) cu (pentru d de la 2 la n executa B) ar trebui sa primesti toate punctele. Mai mult la o alta problema se definea termenul de interval factorial astfel ... Intervalul [0,5] este interval factorial al lui 2! Corect. Definitia e intr-adevar ciudata. Si dacă credeți ca lucrurile ar trebui lăsate asa? Care lucruri? Au corectat altfel decat spui tu mai sus? |
|
|
|
|
5
|
Comunitate - feedback, proiecte si distractie / Blog / Răspuns: Why is your bisection search wrong
|
: Mai 20, 2014, 02:07:49
|
You made me implement this :p I did it quickly, so very likely I have bugs. Python3: from math import frexp
def cube(y):
return y * y * y
def cr_subunit(x):
assert (0 <= x and x <= 1)
delta = 1
y = 0
while cube(y) != cube(y + delta):
delta /= 2
if cube(y + delta) < x:
y += delta
return y
cr_two = 1.2599210498948731647672106072782283505702
def cr_powtwo_nn(e):
if e == 0:
return 1
x = cr_powtwo_nn(e // 2)
x = x * x
if e % 2 == 1:
x *= cr_two
return x
def cr_powtwo(e):
if e >= 0:
return cr_powtwo_nn(e)
else:
return 1/cr_powtwo_nn(-e)
def cr_pos(x):
m, e = frexp(x)
return cr_subunit(m) * cr_powtwo(e)
def cr(x):
if x > 0:
return cr_pos(x)
else:
return -cr_pos(-x)
|
|
|
|
|
7
|
Comunitate - feedback, proiecte si distractie / Blog / Răspuns: Binary Search Shortlist
|
: Mai 16, 2014, 13:51:48
|
One more: 11. Find some minimal subset A of S that has a monotone property p. The property p is given as a function. It is expensive to call this function, so you want to minimize the number of calls in the worst case. (p monotone = if p holds for a set, it also holds for all supersets; A minimal = A has property p, but no proper subset of A does) The following solution is too slow because it makes |S| calls even if A is tiny: find(S, p)
A, B := emptyset, S
while B not empty
pick some element x of B
B := B - {x}
if not p(A union B):
A := A union {x}
return A
|
|
|
|
|
9
|
Comunitate - feedback, proiecte si distractie / Off topic / Răspuns: Cu ce sa incep ?
|
: Octombrie 02, 2013, 12:56:01
|
Cel mai important e sa incepi, sa lucrezi in mod regulat si sa faci lucruri care iti plac, ca sa ramai motivat. In locul tau eu as incerca sa rezolv doua feluri de probleme, cam una pe zi. - probleme care ilustreaza un algoritm standard. Pentru asta arhiva educationala de pe infoarena e buna. Incearca intai sa rezolvi problema singur. Daca in 30-60min nu iti vine nicio idee, atunci cauta intr-un manual. Unul destul de bun este Algorithms de Dasgupta, Papadimitriou si Vazirani. Notele de curs ale lui Jeff Erickson sunt si ele bune. Daca ai cautat vreo ora prin carti si tot nu te-ai prins, uita-te la solutiile altora. Daca nu e clar de ce functioneaza, intreaba pe forum.
- probleme date in anii trecuti la olimpiada. Cea mai buna metoda sa inveti sa faci probleme de la olimpiada e sa faci probleme de la olimpiada.
 Glumesc. Oarecum. Si aici merge cam aceeasi metoda, doar ca de obicei cautatul in carti e mai putin eficient.
Participarea la olimpiade (si premiile) sunt doar una din informatiile folosite de universitati pentru a decide pe cine admit. Trebuie sa ai note bune in general, unele departamente cer examene scrise, sau poate chiar interviuri. Uita-te pe site-urile universitatilor care te-ar interesa ca sa-ti faci o idee mai clara asupra criteriilor folosite. |
|
|
|
|
10
|
Comunitate - feedback, proiecte si distractie / Blog / Răspuns: Numbers everyone should know
|
: Martie 27, 2013, 13:36:15
|
I remember only one thing: a desktop computer nowadays does about 2^27 operations in one second. The other numbres are very easy to derive. When I estimate quickly the runtime f(n), I tend to work with (lg f(n)), and check if it goes over 27. For your Dijkstra example, I'd say there are <=2^25<=2^(2^5) nodes and <=2^26 edges, so the runtime should be <=2^(26+5), which is over the budget. Of course, this is a back-of-the-envelope calculation that you routinely do in a few seconds, not a precise estimate. Edit: Previous version had nodes/edges in the Dijkstra example swapped. |
|
|
|
|
12
|
Comunitate - feedback, proiecte si distractie / Blog / Răspuns: Prison synchronization
|
: Iulie 16, 2012, 23:05:06
|
I remember solving this problem during a pub crawl in Budapest in 2008. While somewhat drunk and with many hints it took me ~1h to solve the first part. Then Michal, who was posing the problem, said "what about if you don't know the inital state of the switch" and I immediately answered "ah, they just do it twice". IIRC, he looked at me a bit puzzled and said, "that's weird, it took me more time to solve the second half than the first." |
|
|
|
|
13
|
infoarena - concursuri, probleme, evaluator, articole / Articole / Răspuns: Standard Template Library (STL)
|
: Iunie 27, 2012, 19:18:33
|
Exact un vector cu trei valori vreau. Mai nou exista tuple. De exemplu #include <cstdio>
#include <vector>
#include <tuple>
using namespace std;
int main() {
vector<tuple<int, int, char> > v;
v.push_back(make_tuple(1,2,'a'));
printf("%d %d %c\n", get<0>(v[0]), get<1>(v[0]), get<2>(v[0]));
} se compileaza cu "g++ -std=c++0x a.cpp", cel putin cu versiunea >=4.4.3. |
|
|
|
|
16
|
Comunitate - feedback, proiecte si distractie / Blog / Răspuns: Merită să faci o facultate?
|
: Aprilie 18, 2012, 19:08:35
|
|
Stiu si la Google oameni care au doar liceul si stiu si ca te incurajeaza sa te lasi de scoala (PhD cel putin) ca sa te angajeze. Dar asta nu schimba faptul ca procentul de angajati care nu au facultatea e foarte mic. Si asta nu este numai fiindca oamenii nu pleaca de la facultate din inertie. Intrebarea e ce procent din studentii de la facultate sunt asa de buni cat sa-i incurajeze Facebook sa se lase si sa vina la ei? Experienta ta personala nu este una tipica.
Edit: Nu vreau sa sugerez nici un raspuns pentru toata lumea. Pur si simplu am sugerat o alta intrebare, legata de cea din titlu, la care mi se pare ca merita ca fiecare sa se gandeasca.
|
|
|
|
|
17
|
Comunitate - feedback, proiecte si distractie / Blog / Răspuns: Merită să faci o facultate?
|
: Aprilie 18, 2012, 10:02:07
|
|
Dar liceul a meritat facut? Uita-te la colegii de generala care nu l-au facut.
Dar scoala generala a meritat facuta? Uita-te la oamenii mai putin norocosi nascuti in alte tari.
Merita facultatea facuta? Ia sa vedem: Cam ce procent din angajatii Google, Facebook, etc. au doar liceul?
Problema nu este daca merita facuta facultatea. Problema este de ce merita facuta facultatea, in ciuda faptului ca de multe ori pare sa fie plictisitoare, sa nu foloseasca ultimele tehnologii, multi studenti spun ca nu e utila si asa mai departe. Asta este intrebarea la care ar trebui sa va ganditi.
|
|
|
|
|
23
|
Comunitate - feedback, proiecte si distractie / Blog / Răspuns: Doua fire, patru variabile
|
: Martie 26, 2012, 13:19:03
|
|
Bravo, ati gasit trei explicatii posibile! O sa reformulez un pic ce ati spus pentru ca am niste lucruri de adaugat.
Intrebarea e un pic ciudata. De obicei vezi intrebari cu forma "ce face programul P" si modelul de executie este implicit, de exemplu definitia limbajului C. Aici insa intrebarea este "gasiti un model de executie in care programul X face cutare lucru". Din cauza asta nu exista un raspuns corect: poti inventa o gramada de modele de executie. Dar binenteles ca unele sunt mai bune ca altele. Ar trebui sa fie cat mai simple si cat mai apropiate de ce fac calculatoarele adevarate. Toata faza la intrebarea asta e sa descrii modelul de executie si sa argumentezi de ce are sens, nu sa spui pas cu pas ce se intampla intr-un model de executie care ramane implicit.
Pana nu demult modelul de memorie prevalent era consistenta secventiala (sequential consistency). Modelul acesta spune ca fiecare executie e echivalenta cu executia unui program secvential obtinut prin intercalarea instructiunilor. Binenteles ca e important ce anume constituie o instructiune. Sa zicem deocamdata ca fiecare linie din ce am scris e o instructiune. Atunci sunt 6 intercalari posibile.
1) Y:=1; a:=X; X:=1; b:=Y { a=0 /\ b=1 }
2) Y:=1; X:=1; a:=X; b:=Y { a=1 /\ b=1 }
3) Y:=1; X:=1; b:=Y; a:=X { a=1 /\ b=1 }
4) X:=1; Y:=1; a:=X; b:=Y { a=1 /\ b=1 }
5) X:=1; Y:=1; b:=Y; a:=X { a=1 /\ b=1 }
6) X:=1; b:=Y; Y:=1; a:=X { a=1 /\ b=0 }
In nici unul dintre cazuri nu e posibil ca a=b=0 la sfarsit.
Prima explicatie este ca granularitatea pentru instructiuni este mai mica: Fiecare linie din ce am scris este de fapt o citire urmata de o scriere. In practica insa problema se observa chiar daca a si b sunt registrii, caz in care granularitatea chiar e de o instructiune pe linie.
Alta explicatie este ca modelul de executie nu asigura consistenta secventiala. Motivul pe scurt e performanta, dar e bine sa vedem mai exact.
Executie speculativa. Aproape toate procesoarele au un pic de paralelism intern. De exemplu au o bucata de circuit care face adunari si una care face inmultiri. Daca instructiunea curenta e o adunare si peste cinci instructiuni vine o inmultire atunci n-o sa stea ci o sa faca si inmultirea acum, cu niste check-uri ca asta e OK (sa nu existe dependente de date). In cazul nostru, daca esti primul dintre procesoare atunci vezi instructiunile (Y:=1; a:=X) si nu le vezi pe cele executate de celalalt procesor/core. Din ce vezi, nu ai absolut nici un motiv sa crezi ca s-ar schimba ceva daca le executi in alta ordine, asa ca n-o sa ai nici o jena sa faci a:=X inainte de Y:=1. Compilatorul poate si el sa reordoneze instructiuni, dar problema apare chiar daca scriem direct in asamblor.
Cache. In fine, alta explicatie este ca fiecare procesor lucreaza cu cache-ul lui local, care nu se sincronizeaza decat din cand in cand cu memoria globala, fiindca operatia de sincronizare este lenta. (Inca o data, nu e necesar sa luam in considerare optimizari de compilator pentru a observa acest efect; hardware-ul deja are problema asta.)
Cam toate modelele de memorie ofera garantia ca memoria e coerenta: fiecare locatie de memorie are o istorie liniara. Dar nu prea mai garanteaza mult in afara de asta.
De obicei exista instructiuni speciale pentru a-i spune procesorului ca nu vrei sa reordoneze instructiuni (isync pe PowerPC) sau ca vrei sa-si syncronizeze cache-ul cu memoria globala (sync pe PowerPC, se mai numeste si bariera de memorie). Mai exista si alte instructiuni care garanteaza ca lucreaza direct cu memoria globala fara sa foloseasca cache (de exemplu compare&swap).
O problema care e studiata destul de activ este urmatoarea: Dat fiind un program si un model de memorie, ce bariere trebuie introduse pentru ca programul sa se comporte ca si cand modelul de memorie ar fi consistenta secventiala? De exemplu, unde trebuie pus sync/isync in programul de mai sus ca sa se comporte ca in modelul consistent secvential?
|
|
|
|
|
25
|
Comunitate - feedback, proiecte si distractie / Blog / Răspuns: Cum sa scrii programe la concursuri si nu numai
|
: Martie 23, 2012, 22:30:41
|
|
Am scris un comentariu super, da' la mancat serveru'. Acum cititi un surogat amarat.
Gandeste-te bine la solutie inainte sa scrii cod. Inchipuie-ti ca-i explici altcuiva solutia, de ce e corecta si suficient de eficienta. Nu-i nevoie sa vorbesti tare, dar e nevoie sa folosesti hartie pentru lucrurile care se formuleaza greu in cuvinte.
Cunoaste bine particularitatile limbajului de programare. Tine toate warningurile activate, -Wall -W in gcc, -Xlint:all in java.
Scrie cod incremental. Daca ai erori de compilare, atunci ai scris prea mult de la ultima compilare. Daca programul face altceva decat ai prezis, atunci l-ai rulat prea rar.
La antrenamente fa mai multe solutii pentru o problema. Floyd zice asa: Dupa ce gasesti o solutie la o problema grea, cauta un proces care te-ar fi facut sa gasesti solutia repede. O metoda buna este sa rezolvi problema de multe ori si sa simplifici solutia.
|
|
|
|
|
