Marele Premiu de la Saratov

saratovului

Cum se rezolvă C și D?
Cred că am mai văzut problema J undeva

  • fmota
  • Acum 3 ani
  • 37

Cum se rezolvă E și H? Amândoi sunt o problemă destul de interesantă.

În primul rând, putem întreba n interogări pentru a găsi toate frunzele copacului. Pentru a verifica dacă un vârf este o frunză, cerem o interogare care conține toate n - 1 alte vârfuri; dacă răspunsul este n - 1, vârful pe care l-am exclus dintr-o interogare este o frunză.

Atunci să ne înrădăcinăm arborele la o frunză. Lăsa L(X) fie setul de frunze din subarborele vârfului X . Deoarece nu există vârfuri cu gradul 2, pentru oricare două vârfuri X și y L(X) ≠ L(y); în plus, X este un strămoș al y dacă nu. Deci, dacă obținem informații despre L(X) pentru fiecare vârf, atunci putem reconstrui copacul.

Pentru rădăcină, L(rădăcină) este ansamblul tuturor frunzelor. Pentru fiecare altă frunză z, L(z) = z>. Deci, trebuie să găsim L(X) numai pentru non-frunze. Pentru a verifica dacă o frunză z se află într-un subarbore de vârf non-frunze y, s-ar putea să ne întrebăm 3 rădăcină y z .

Deci, dacă numărul de frunze este l, trebuie să întrebăm (l - 1)n - l) interogări de găsit L(X) pentru toate vârfurile care nu sunt frunze. Aceasta nu va depăși 2450 și, prin urmare, nu vom solicita mai mult de 2550 de interogări.

Misto! Este o soluție foarte simplă.

Am avut o soluție pentru aceleași interogări, dar a doua parte a folosit o perspectivă diferită.

Deci, pentru fiecare frunză cunoaștem „calea” către rădăcină (numai vârfuri, nu ordinea lor). Acum, intersecția oricăror două astfel de „căi” este, de asemenea, o cale către rădăcină de la un anumit vârf (lca lor). Și fiecare vârf este lca de 2 frunze (din cauza lipsei vârfurilor de 2 grade). Deci, acum avem o listă de "căi" pentru toate vârfurile și trebuie să reconstituim un copac care poate fi realizat de dfs simpli.

Dacă arborele este un bambus, răspunsurile pentru toate interogările din prima parte a algoritmului ar trebui să fie n - 1, nu ar trebui? Dacă nu, vă rugăm să explicați de ce.

E: În DAG fiecare nod poate fi atins de A și ajunge la B, dacă nu

  • A nu are un nivel de licență
  • B nu are o clasă superioară
  • | indegree | > = 1 și | outdegree | > = 1 pentru toate nodurile care nu sunt A, B

Acum ar trebui să selectați două seturi de margini disjuncte EA, EB astfel încât

  • marginile din EA au puncte finale distincte
  • muchiile din EB au puncte de pornire distincte

Acest lucru poate fi găsit prin potrivirea maximă în Oh(pl 0,5)

Uau, curge pentru 1000000 de margini, acesta este un nou record pe care l-am văzut vreodată:)

Apropo, poate fi rezolvat fără flux.

Nu înțeleg de ce este o nouă înregistrare pentru dvs., dar potrivirea bipartită pe vârfurile 10 ^ 6 ar trebui să ruleze în mod evident la timp:)

Ștergerea graficului pentru fiecare TC a fost totuși o durere.

De asemenea, se poate face în O (m) și chiar se poate face cu costul total minim al muchiilor în timp O (m).

Să adăugăm două muchii de la B la A. Acum avem doar o condiție pe grade. Să obținem un grpah bipartit cu 2 copii de vârfuri în partea stângă (corespunzătoare vârfului în EA și vârfului în EB) și muchii în partea dreaptă. Fiecare vârf din partea a doua va avea exact două margini (pentru a începe în EA și în și în EB). Problema este de a găsi potrivirea perfectă (prin partea din stânga) în acest grafic.

Acest lucru se poate face în două moduri. În primul rând, fiecare lanț pe care îl căutăm în metoda Kuhn are un avantaj unic pe fiecare pas. Deci, putem menține doar capătul acestui lanț pentru fiecare vârf în uniune disjunsă.

Cealaltă modalitate, care pare a fi mai frumoasă pentru mine, este gândirea la vârful de gradul 2 ca la o margine între vecinii săi. Se poate arăta că potrivirea este aceeași cu acoperirea acestui grafic prin set de margini, în care nici o componentă nu are mai multe margini decât vârfuri (adică un copac sau un ciclu cu copaci pe el). O astfel de acoperire poate fi realizată de ceva de genul algoritmului Kruskal. Și doi să fim sinceri, produce exact același cod, prima metodă.

Și dacă sortăm marginile prin creșterea costurilor în oricare dintre aceste metode, aceasta ne va conduce la o soluție de cost minim.

Știe cineva soluția intenționată la B? Cum ar trebui să faceți calculele rapid după ce ați ajuns la o formulă pentru răspuns?

Deși nu am AC, am ceva în Python care ar putea trece într-un limbaj mai rapid cu GMP-gcd încorporat, cu unele optimizări constante.

Fie „avgbad” costul mediu al unui articol nerezonabil și „avgreason” costul mediu al unui articol rezonabil. Să fie „rele” numărul de obiecte nerezonabile. Atunci răspunsul este

Binomii pot fi calculați destul de repede prin cernerea peste primele, probabil că acest lucru ar putea fi accelerat mai mult prin calcularea produsului în mod divizat și cucerit. Principalul blocaj a fost reducerea fracției. Buitin python gcd este să încetinească, am găsit un lehmer-gcd mai rapid aici, dar este încă să încetinească.

Încărcarea GMP în c ++ nu funcționează din păcate pe Yandex (cel puțin metoda care funcționează pe spoj nu funcționează pe yandex), așa că nu am putut încerca GMP-gcd. Voi mai încerca câteva lucruri până mâine.

Editare: Am obținut o anumită accelerare în pow_binomal calculând produsul într-un mod mai inteligent, acum TLE 36 (anterior TLE 34).

Bine, am primit AC în 1,5 secunde, cu câteva optimizări.

  • Formula care implică doar doi coeficienți binomiali diferiți și unele numere mai mici. (Vezi postarea mea de mai sus.)
  • Calcularea binomilor prin numărarea numărului de apariții ale fiecărui prim.
  • Calcularea produsului rezultat al puterilor prime prin împărțirea binară.
  • (nou) Anulați primele care apar în ambele binomii devreme.
  • Utilizați lehmer gcd.
  • Utilizați pypy4, nu python2.7.

Cum se rezolvă problema F? Cum folosim constrângerea ?

Cred că trebuie să folosim trucul de aici, dacă alegem un indice aleatoriu și cu probabilitate (care prin starea noastră este cel puțin așa că vom verifica aproximativ 10 cazuri pentru a fi siguri) va apărea în secvența finală. Apoi găsim cel mai mare divizor al său astfel încât să existe cel puțin n - k numere care împart acest număr.

UPD. Despre ultima parte, să presupunem că am ales numărul N, are cel mult divizori. Să presupunem că divizorii săi sunt 1 = d 1 2 K = N iar numerele prime le împart p 1 2 t (1 ≤ t ≤ 15). Vom calcula o matrice cnt cu cnt eu fiind numărul de valori din secvența noastră care se împart d eu . În problema menționată mai sus ni se permite să facem următorul lucru:

Primul set cnt eu să fie egal cu numărul de valori astfel încât mcd între el și N să fie egal cu eu .

În al doilea rând, iterați doar pentru fiecare eu din K până la 1 și pentru fiecare j din eu + 1 la K dacă avem asta d j ≡ 0 (mod d eu) apoi creștem cnt j de cnt eu .

Acum trebuie să-l optimizăm pentru că Oh(K 2) este prea mult, de aceea am introdus succesiunea primelor. Practic pentru fiecare prim p eu și pentru fiecare j creștem cu cnt j poziția în matrice cnt corespunzătoare divizorilor (1 ≤ r, d j ≡ 0 (mod p eu r )). Acest lucru se poate face din nou în timp liniar. Deci complexitatea devine care în practică este mult mai mică.

Dacă găsiți ceva în neregulă, vă rog să-mi spuneți. Sper ca nu am ratat nicio solutie usoara:) .