Afişează mesaje
|
Pagini: [1] 2 3 ... 6
|
3
|
infoarena - concursuri, probleme, evaluator, articole / Concursuri / Junior Challenge 2017
|
: Septembrie 01, 2017, 18:10:39
|
Salut. va invit sa participati la Junior Challenge 2017! Am luat legatura cu organizatorii EJOI si ne-au pus in contact cu tarile participante. Speram sa fie cat mai multi participanti juniori internationali. Concursul este dedicat tutoror, nu numai juniorilor. Formatul concursului: Concursul va avea 4 probleme (dintre care una mai usoara) pe o durata de 4 ore. Probleme vor avea 2-4 subtaskuri, de punctaje variabile, cele usoare fiind accesibile tuturor. Concursul va avea full-feedback, cu teste grupate in interiorul unui subtask. Ziua 1 va avea loc Duminica, 3 sept 2017, la ora 18Ziua 2 va avea loc Marti, 5 sept 2017, la ora 14Organizatori: bciobanu (Bogdan Ciobanu) Andrei1998 (Constantinescu Andrei Costin) tamionv (Tamio Vesa Nakajima) george_stelian(George Chichirim) geniucos (Oncescu Costin) impreuna cu Alexa Tudose, Bogdan Sitaru, , Radu Muntean, Serban Cercelescu, Stefan Constantin si Teo Moroianu.
|
|
|
4
|
infoarena - concursuri, probleme, evaluator, articole / Algoritmiada 2016 / Răspuns: Marvel
|
: Iunie 19, 2016, 12:20:51
|
Nu cred ca sunt singurul care a inteles problema in felul urmator. "Pentru cate noduri X exista o sortare "topologica" in care un nod poate sa fie pe pozitia x daca exista cel putin un nod pe pozitiile 1 .. (x - 1) care sa aiba muchie catre el si labelurile nodurilor sa formeze subsirul din input."
Trebuia scris mai mic ca trebuie sa fie lant.
|
|
|
7
|
infoarena - concursuri, probleme, evaluator, articole / Algoritmiada 2015 / Răspuns: Feedback Runda 3
|
: Iunie 27, 2015, 21:19:17
|
Legat de problema Arb4 e posibil sa faci O(MlogM) sortare + O(NlogN) RMQ + O(Mlog*N + M) solutia propriu-zisa. Nu stiu cat de Mlog*N e, pentru ca tot ce faci e compresia drumurilor, nimic mai mult, pentru simplitate. Dar e acceptabil Codul meu, cu RMQ cu stramosi + parsare -> http://ideone.com/Kk0h9Rlua 690 fara parsare, poate pierdeam ceva si am spus sa nu risc. Am bagat tot in concurs, inafara de parsare. Nu e un capat de lume. Problemele au fost super ok. Site-ul la fel Problema metrou3 sincer mi s-a parut cam jegoasa. Ideea din spate nu e super grea. Pentru fiecare statie vezi doar in momentul cand is trenurile in gara cum o sa se duca oamenii, mai faci acolo ceva inmultiri si sume partiale + cautari binare. Ideea e intuitiva, dar implementarea mi se pare ca poate sa cauzeze super multe probleme aiurea. La final de zi, sper ca i-a ajutat pe cei care dau bacul la info joi. Doar pentru ei a fost pusa acum
|
|
|
9
|
infoarena - concursuri, probleme, evaluator, articole / Algoritmiada 2015 / Răspuns: Diametru
|
: Iunie 27, 2015, 11:01:47
|
Daca nu mai ai perechi clar ai rezolvat tot. Sa spunem ca ai varful 1, si ai luat perechile (1, 2) (1, 3) (1, 4) .. w/e asta inseamna ca te-ai extins cu BF-ul din toate nodurile posibile, deci ai aflat raspunsul Daca ai implementa TU problema, ai optimiza sa nu te extinzi daca next a fost vizitat, nu perechea (nod, next)
|
|
|
17
|
Comunitate - feedback, proiecte si distractie / Blog / Răspuns: Probability puzzle: Cars
|
: Noiembrie 14, 2014, 07:59:36
|
"This is pretty much equivalent to the question of how many times you update the minimum so far when going through a random permutation, going from the first car to the last: each time you find a new minimum, that will be a separate cluster."
That was my first ideea too but it's not corect. If you want to create a cluster, the new minimum should be at a distanve of at leaste 1 For example N .. 1 N updates but 0 clusters.
In this case the answer would've been 2sqrt Because it's the expected value of "increasing sebsequene"
|
|
|
18
|
infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 521 Banuti
|
: Noiembrie 11, 2014, 14:09:15
|
ceva nu e chiar ok la problema asta #1 nu cred ca merge in O(N * N). cel putin mie nu mi-a mers. daca am bagat dijkstra care merge teoretic in O(N * N * logN)
stiu ca teoretic e foarte greu sa iasa O(NNlogN) dar cred totusi ca ar trebui sa mearga mai bine NN pt ca graful e complet.
#2 exista cazuri in care rezultatul e pe int64 nu exista aceasta restrictie si e foarte usor sa gasesti un test care sa iasa de int 32 de biti 2 4999 10^7
|
|
|
25
|
Comunitate - feedback, proiecte si distractie / Blog / Răspuns: Binary Search Shortlist
|
: Mai 17, 2014, 14:09:51
|
First i need to say that #8 is my favourite problem So here it is ... let's asume that the arrays are indexed from 1 to n, m O(logK) First we need to make a quick observation. The first k elements in the union form a compact section in the 2 arrays. That means that one array contains at least [k/2] elements. let x = k/2 We compare A[x] with B[x]. If A[x] < B[x] implies the fact that the first x elements from A are in the first k in the union. if A[x] was not in the first K elements in the union .. then B[x] was .. and B[x] is bigger than A[x], so it's false.
In the first step we move A[1] to A[x + 1] and continue the program with the A[x + 1] and B[1] as the .front() of the arrays and with k -= x
And .. here it's a C++ code for this. #include <cassert> #include <ctime> #include <cstdlib>
#include <algorithm> #include <fstream> #include <iostream> #include <vector> using namespace std;
void read_vector(vector<int> &a, ifstream &in); void read(vector<int> &a, vector<int> &b, int &k);
int solve(vector<int> &a, vector<int> &b, int k) { int stA = 0, stB = 0; while (k != 1 and stA < int(a.size()) and stB < int(b.size())) { int indA = min(k / 2, int(a.size()) - stA); int indB = min(k / 2, int(b.size()) - stB);
if (a[stA + indA - 1] <= b[stB + indB - 1]) { stA += indA; k -= indA; } else { stB += indB; k -= indB; } }
if (stA == int(a.size())) return b[stB + k - 1]; if (stB == int(b.size())) return a[stA + k - 1];
assert(k == 1); return min(a[stA], b[stB]); }
int main() { vector<int> a, b; int k; read(a, b, k); cerr << solve(a, b, k); return 0; }
void read_vector(vector<int> &a, ifstream &in) { int n; in >> n; a.reserve(n); while (n--) { int x; in >> x; a.push_back(x); } return ; }
void read(vector<int> &a, vector<int> &b, int &k) { ifstream in("data.txt"); read_vector(a, in); read_vector(b, in); in >> k; in.close(); return ; }
|
|
|
|