Felicitari tamio pentru initiativa.
Sper ca mai multa lume sa iti urmeze exemplul.
Spor la treaba!

Cand se updateaza rating-urile? 

[Junior Challenge 2017]

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 18
Ziua 2 va avea loc Marti, 5 sept 2017, la ora 14

Organizatori:
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.

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.

foarte frumoasa problema infinitepatternmatching
dar cred ca numele infinitepatternmatchingonbinarynumbersbiggerthanzero era mai accurate

Copii isi retin mere, sau CopilMax si CopilMin se refera la numarul de mere pe care le-au primit si apoi le-au dat mai departe? (cum vrem noi, banuiesc)

[La final de zi, sper ca i-a ajutat pe cei care dau bacul la info joi.Doar pentru ei a fost pusa acum]

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/Kk0h9R
lua 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 

ez katka
ez 5 minute

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)

In fine ..

Cum adica no comment?
Pe langa ca in enunt NU SCRIE CAND SE OPRESTE ALGORITMU
scopul nostru e sa facem ca "pseudo codu" ala sa ia TLE sau sa ia TLE pana gaseste solutia buna?

Acum ca ma gandesc mai bine, cred ca asta se intampla si la mine.
Cred ca el nu mai gaseste muchiile respective si crede ca s-a terminat.
DAR NU S-A TERMINAT >

asa ca presupun ca gaseste si prost diametrul

Cum definiti faptul ca "niciunea din perechile (next, nod_curent) si (nod_curent, next) sa nu mai fi fost aleasa"
Sa nu te fi extins din nod_curent in next sau invers?
in cazul asta, sigur sigur evalul ia next-ul sa aiba indice minim?
Iau 50 de puncte si chiar nu inteleg de ce

Gainile sunt in siguranta? Sigur nu e vreo sansa sa se inece?

Daca balada din input e foarte mare intra citirea in timp sau trebuie sa o parsam?

I thought that a cluster if formed when 2 or more cars are stuck together 
Sorry.

"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"

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

Sirurile de caractere trebuie puse in ordinea din input?

"pentru vecin al lui nod"
ordinea in care vizitam vecinii trebuie sa fie aceeasi ca ordinea in care ni se dau muchiile in problema?

"Se va accepta o eroare de cel mult 10-2."

Dupa ce cele 2 drepte de noi impart planul in 4 bucati, precizia se aplica ca dimensiunea bucatilor sa difere cu maxim 10-2 sau
locul de intersectie al dreptelor cu poligonul sa difere cu 10-2?

Rezultatul sigur incape pe int64?

You have no power here, elf!

Andrei, la problema Marsmusic faci practic pt fiecare melodie suma modurilor in care se suprapun in toate cazurile?
Daca da .. faci pe numere mari si imparti la m!
Si in cazul asta, se poate sa fac fara numere mari (aceeasi rezolvare) doar cu double?

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

Cod:

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.

Cod:

#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 ;
}