Mentionez pentru cine e interesat ca problema se poate reduce la min path cover cu noduri disjuncte intr-un DAG, care poate fi rezolvata cu cuplaj maxim (https://en.wikipedia.org/wiki/Maximum_flow_problem#Minimum_path_cover_in_directed_acyclic_graph).

Reducerea consta in inlocuirea grafului initial cu un graf cu aceleasi noduri, dar muchii orientate x -> y in cazul in care exista un drum de la nodul x la nodul y in graful initial. Pentru a demonstra ca cele 2 probleme sunt echivalente e suficient sa aratam ca orice solutie pe graful initial e o solutie pe graful nou si viceversa.

Daca exista o solutie cu un set de drumuri pe graful initial, poate fi transformat intr-o solutie pe graful nou (fara noduri duplicate) sarind nodurile care au fost vizitate deja (muchiile necesare pt "sarituri" exista din constructie). Pe exemplul problemei:
1 -> 2 -> 3 -> 5 ar ramane tot 1 -> 2 -> 3 -> 5 in graful nou
7 -> 2 -> 4 -> 6, ar deveni:7 -> 4 -> 6 (am sarit nodul 2 fiindca a fost deja vizitat + muchia 7 -> 4 exista din constructie)

Invers, daca exista o acoperire in graful nou, poate fi transformat intr-o solutie pt graful initial inlocuind fiecare muchie x -> y, cu toate nodurile coresp drumului de la x la y.

Extinzand un pic explicatia lui Patrick cu o demonstratie care arata de unde vine solutia respectiva:

In principiu vrem sa determinam in ce conditii o "tragere" intersecteaza o "tinta". Unei tinte oarecare ii corespunde un triplet (x0, y0, y1), iar unei trageri un (x', y', r).
Observam ca punctele de pe traiectoria tragerii sunt de forma (x' + r', y' + r'), 0 <= r' <= r. Pt a avea intersectie, trebuie ca (x' + r', y' + r') sa fie pe dreapta verticala (x0, y0, y1) corespunzatoare tintei, pt un 0 <= r' <= r (exista maxim o intersectie intra o dreapta transversala si una verticala) <=>
exista 0 <= r' <= r, a.i:
1) x0 = x' + r'
2) y0 <= y' + r' <= y1

Observatie 1: singurul r' candidat este r' = x0 - x', care tb sa fie intre 0 si r. Inlocuind in a 2-a conditie avem:
y0 <= y' + r' <= y1 <=> y0 <= y' + x0 - x' <= y1 <=> y0 - x0 <= y' - x' <= y1 - x0

Observatie 2: Avem 2 conditii pt intersectie: una la nivel de x si una la nivel de y dupa cum am vazut mai devreme. Conditia pt y nu depinde deloc de r', si implicit de r. Putem rescrie conditiile de mai devreme ca:
1) x' <= x0 <= x' + r
2) y0 - x0 <= y' - x' <= y1 - x0

De aici ne vine ideea de a ne creea un nou sistem de drepte a.i:
a) "tinta" (x0, y0, y1) -> (x0, y0 - x0, y1 - x0)
b) "tragerea" (x', y', r) -> (x', x' + r, y' - x')

Astfel avem numai drepte orizontale si verticale ; iar o intersectie intre o dreapta verticala si una orizontala respecta conditiile 1) si 2). Aceasta problema este un exemplu clasic de line sweeping prezentat spre ex la https://www.topcoder.com/community/data-science/data-science-tutorials/line-sweep-algorithms/ sub sectiunea "line segment intersections". Se poate folosi intr-adevar un AIB + Smenul lui mars pt a numara numarul de intersectii intre "portiunea activa" si o dreapta verticala.

Nu inteleg de ce pt ex 1 3 1 6 8 7 e solutia buna. De ce 1 3 2 1 6 8 7 nu e o solutie buna? (3 2 1 e o secv descresecatoare de lungime 3)

La problema Rell's Report ar fi mers o limita de timp cu 0.1 - 0.2 mai mare ca sa intre dinamica normala fara memoizare. In rest, felicitari comisiei pentru organizare.

Deci pana la urma pt cv gen 50.000, 50.000, 0.000, raspunsul e 4? (facand abstractie de faptul ca nu sunt teste cu procent de 0).

Are legatura cu faptul ca figureaza ca nu se mai pot trimite solutii la probleme acum?

Poti pleca de la reprezentarea unui arbore de intervale. Un nod dintr-un arbore de intervale caracterizeaza un interval, (st, dr) sa zicem. Acum sa presupunem ca iti mentii urmatoarele informatii pt fiecare astfel de nod:
1) o lista cu valorile din intervalul (st, dr) in ordine crescatoare. Aceasta lista se poate obtine prin interclasarea listelor fiilor acelui nod. Avand in vedere ca fiecare valoare apare in log N noduri, complexitatea dpdv al memoriei cat si al timpului este N log N la pasul asta.
2) conceptual vei mentine o alta lista de lungime nr de noduri, unde pe pozitia i, ai 1 daca valoarea i(in ordinea sortata de mai sus) e online, 0 altfel. Avand in vedere tipurile de operatii pe care vrei sa le executi, defapt iti vei mentine un aib de lungime tot nr de noduri care este construit pe baza listei de care spuneam. Pt stocarea acestor aib-uri este necesara de asemenea, tot N log N memorie.
Cu aceste informatii, poti sa aplici acum operatiile date in felul urmator:
Operatie de tip 1: Vei trece prin cele log N noduri din arborele de intervale care contin nodul p din enunt si le vei actualiza aib-ul asociat. Deci log ^ 2 N / operatie de acest tip
Operatie de tip 2: Vei descompune intervalul (p, q) in log N noduri. Acum cauti binar rezultatul printre cele N valori posibile(presupunand ca mai ai o lista cu valorile initiale sortate in ordine crescatoare). Pt o anumita valoare, verificarea se poate face folosind structura de aib, in log (lungime nod) pt fiecare nod. Complexitatea teoretica e in cazul asta log ^ 3 N, dar se comporta destul de bine.
Bafta!

Si o solutie dinamica brute, in care incerci sa potrivesti fiecare cuvant la fiecare pozitie intra

Problemele au fost destul de interesante. Din pacate testele lasa mult de dorit...

Pe exemplu, daca la t = 90, corpul 2 se afla in (1, 2), corpul 3 care orbiteaza in jurul lui nu ar trb sa se afle la (1, 3) ?

Cand se spune ca un corp graviteaza in jurul altuia, se intelege ca distanta intre cele 2 corpuri ramane constanta la orice moment de timp?

Mi se pare cam mica limita de timp la mergesort. Solutia mea(corecta), desi are O(N) complexitatea, ia TLE-uri pe aproape jumate de teste.

Daca capul de citire e pe (i,2) (elementul 2 din perechea i) si vrei sa citesti (j,1),j>i urmatorul caracter, costul deplasarii este j-i sau 2*(j-i)-1?

3 sfaturi care mi-ar fi fost utile daca le-as fi aplicat:
1) Cititi cu atentie problemele a.i. cerinta sa fie clara. Puneti intrebari daca sunteti nesiguri
2) Cel mai important e sa salvati problemele unde/cum trebuie. Degeaba munciti la probleme,daca le salvati prost. O greseala aparent nesemnificativa cum ar fi confundarea unui "o" cu un "0", dupa cum am experimentat si eu, va conduce cu siguranta la un punctaj rotund de 0 puncte.
3) Verificati tot timpul memoria folosita. Chiar daca memoria disponibila pare arhisuficienta, este de preferat sa verificati. Eu am reusit sa busesc memoria la o problema de la oni anul trecut la care erau 128 mb disponibili.
Succes!  

La final stiva trebuie sa fie goala?

Deci N e par?

Numarul de mutari trebuie sa fie acelasi(cei doi jucatori muta de nr egal de ori)?

Salut.Cand are cineva timp,ar trebui modificata limita de timp la problema asta. Cand a fost data la olimpiada timpul era de 3s/test,iar 0.05 pare cam putin in comparatie, chiar daca compilatorul de pe infoarena se misca mult mai bine. Mersi!  

Cred ca este o problema in evaluator: http://infoarena.ro/job_detail/677733 .Rog pe cineva cand are timp, sa se uite si sa rezolve aceasta chestiune. Mersi

Salut. Cred ca ar trebui sa schimbati niste teste pentru a delimita solutia corecta de alte solutii mai putin bune  . Eu spre ex am reusit sa obtin 100 puncte cu o sol incompleta: http://infoarena.ro/job_detail/667842 .

Sunt foarte curios care-i solutia optima.

Cred ca este o problema in evaluatorul de la aceasta problema: http://infoarena.ro/job_detail/653225 . Cand are cineva timp, il rog sa se uite ce nu merge. Mersi.

Rezultatele echipei Vianu:

Matematica:
Stefan Gramatovici(juniori) argint
Petru Constantinescu(seniori) argint

Fizica:
Cristian Zaharia(juniori) bronz
Alexandru Botu(seniori) bronz
Andra Ionescu(seniori) argint

Chimie:
Cristian Zagar(juniori) argint
Laura Manea(seniori) argint

S-au luat cate 2 medalii din fiecare tip

Gandeste-te ca daca ai un nr impar de termeni consecutivi ei pot fi scrisi: x-k,...,x-1,x,x+1,...,x+k.Suma lor o sa fie (2k+1)x.Deci poti cauta x printre divizorii lui n. Asemanator si daca ai nr par de termeni: x-(2k-1)/2,...,x-1/2,x+1/2,...x+(2k-1)/2.Suma lor este 2k*x.

Ca un fapt divers,am observat ca testele la aceasta problema sunt destul de slabe. Am luat 100 puncte cu o sursa care are complexitate O(N^2) pe cel mai rau caz: http://infoarena.ro/job_detail/508238. Poate ar trebui sa fie schimbat unul sau mai multe teste pentru a departaja astfel de abordari de abordarea corecta.In cazul in care vreun admin considera ca ar trebui schimbat ceva pot propune cateva teste.