Admitere la școală Yandex. Intrarea în școala analizei datelor

ÎN În ultima vreme Comunitatea IT ucraineană discută adesea despre problemele educației degradante din Ucraina și Rusia: universitățile nu mai produc programatori cyborg care calculează orice proiect într-o zi și încep cu sârguință să-l implementeze, ci în cel mai bun caz codificatori autodidacți care se află în rândurile din spate. publicul, în loc să asculte prelegeri despre receptorii cu tub vechi, citește cărți despre limbaje de programare. Da, acești oameni pot fi felicitați - ei înșiși încearcă să învețe cumva pentru a-și găsi un loc de muncă în viitor, dar adesea lipsa metodologiei și a unui proces de învățare clar definit nu le permite autodidaților să concureze cu programatorii din „Școala veche”. Sunt și eu unul dintre acei indivizi.

Am folosit în principal banca universității pentru a studia diverse limbaje de programare, am învățat multe, am câștigat experiență lucrând ca programator angajat și în proiectele mele, dar simt că încă mai există o mizerie în capul meu care trebuie să fie adusă urgent într-un fel. de formă structurată. Ca urmare, am început să sistematizez cunoștințele dobândite, să caut opțiuni pentru rezolvarea problemei și mai rapid și mai eficient, să notez și să evidențiez clasa de instrumente care m-ar ajuta în acest sens. Dar nici asta nu mi s-a potrivit. S-a simțit că este necesar să fiu în compania unor oameni care erau cu cap și umeri deasupra mea în cunoaștere, să învețe din experiența lor. Așa că am dat peste un anunț de admitere la Școala de Analiză a Datelor de la Yandex din Ucraina.

De ce am vrut atât de mult să merg la Școala de Analiză a Datelor? Pentru că acum, ca și aerul, am nevoie de practica rezolvării unor probleme complexe, care necesită nu numai cunoașterea unui limbaj de programare, ci și o bună bază de cunoștințe în matematică și teoria probabilităților. Cred că, învățând cum să rezolv astfel de probleme, voi fi mai competitiv pe piață - și aceasta este sarcina mea de bază, forța motrice din spatele dorinței mele de a învăța lucruri noi. Cred că oamenii care au creat un proiect atât de înalt științific au multe de învățat și merită să lupți pentru oportunitatea de a învăța.

Pregătirea

Pentru a aplica pentru admitere a fost necesar să completezi un chestionar detaliat și să rezolvi mai multe probleme de matematică. analiză, teoria probabilității, geometrie analitică. Sarcinile au fost foarte ușoare, dar din moment ce la completarea chestionarului a fost necesar să se indice doar răspunsurile, și nu soluția, pentru siguranță am decis să verific totul de două ori pentru a trece cu siguranță această etapă. Am petrecut câteva ore seara cu asta după muncă și l-am trimis.

O săptămână mai târziu, am primit o scrisoare de la comisie introductivășcoli pe care le-am trecut de prima etapă și am fost invitat la un interviu la biroul Yandex din Kiev. Am fost sfătuit să mă familiarizez cu principalele subiecte pe care vor avea loc interviurile. Un moment plăcut a fost că întrebările erau însoțite și de cărți pe care se putea pregăti (am trecut de analiza matematică la institut acum patru ani și, bineînțeles, am uitat numele cărților).

Am decis să petrec două săptămâni pregătindu-mă pentru interviu și în fiecare zi după muncă mi-am amintit ce uitasem și am învățat ceea ce nu știam înainte. În special, algebră liniară A trebuit să-l învăț de la zero, pentru că ei nu l-au predat la departamentul meu de electronică. Vreau să spun că, dacă ai absolvit deja facultatea și munca ta nu are legătură cu matematică, atunci trebuie să alocați mai mult de două săptămâni pentru pregătire. Este foarte de dorit să aveți o vacanță în acest timp, deoarece trebuie să petreceți mult efort și timp. Accentul nu trebuie pus pe teorie, ci pe soluție sarcini practice, care după o zi de lucru este dificilă. Totuși, teoria trebuie să fie cunoscută „de la scoarță la acoperire”, deoarece sarcinile de la interviu erau adesea nestandardizate.

Ora "H"

Așa că a sosit ziua interviului. Dimineața am ajuns la biroul Yandex, i-am întâlnit pe examinatori (erau un tânăr drăguț și o fată de la Universitatea de Stat din Moscova) și a început interviul. A constat în sarcini practice. Dupa rezolvarea primei, iti dau pe a doua, apoi pe a treia, si tot asa pana cand examinatorul intelege ca ai trecut, sau nu intelegi ca ai picat. Prima sarcină a fost pe tema programării.

Prima mea sarcină a fost să scriu un program pentru găsirea GCD în orice limbaj de programare. Din moment ce la școală am fost la olimpiade de informatică și matematică, am rezolvat rapid (din memorie) și am trecut la următoarea. A doua sarcină este să găsim derivata lui x la puterea x. O sarcină destul de ușoară dacă cunoașteți proprietățile logaritmului, dar am uitat tocmai această proprietate. Din fericire, examinatorul m-a îndrumat în această direcție, iar problema a fost rezolvată rapid. Vreau să subliniez că la interviu, spre deosebire de chestionar, nu au mai fost verificate răspunsurile, ci trenul de gândire care a condus la răspuns. Un astfel de sistem de admitere a fost folosit în același KPI înainte de introducerea testării unificate și a dat destul rezultate bune. Se poate observa că școala a fost organizată nu pentru Yandex PR, ci pentru ca tinerii promițători să poată face un salt calitativ în dezvoltare.

Nu-mi amintesc exact următoarele sarcini, îmi pot aminti doar subiectele: calculați determinantul unei matrici de mărimea n, unde n este orice număr; verifica daca este spațiu vectorial bază; calculați varianța funcției de distribuție peste funcţie dată probabilitate densitate. În medie, interviul a durat două ore - cineva a renunțat mai devreme, cineva a stat până la ultimul.

"Incearca din nou"

Comisia de examinare a trimis rezultatele prin poștă, indiferent dacă persoana a promovat sau nu. Mi-au trimis o notificare că nu am trecut.

În mod surprinzător, după ce nu am fost acceptat, dorința de a studia la ShAD nu a dispărut, ci doar s-a intensificat. Anul acesta vreau și eu să încerc să merg la școală, dar încerc să mă pregătesc din timp. Pentru început, este necesar să ne amintim din nou întreaga teorie, iar după aceea - să dezasamblați și să dezasamblați sarcinile, deoarece acestea sunt cele mai importante pentru admitere.

Cu acest articol, vreau să încep oficial campania mea de pregătire pentru a mă alătura școlii Yandex. Plănuiesc să împărtășesc gândurile și evoluțiile mele în această direcție cu cititorii DOU: cred că nu sunt singurul care se pregătește să intre în acest an.

Vara este timpul pentru examenele de admitere. În acest moment, selecția la Școala de Analiză a Datelor Yandex este în curs de finalizare - sunt în curs de desfășurare interviuri pentru cei care au promovat deja examenul. Școala de Informatică predă învățarea automată, viziunea computerizată, analiza textului în limbaj natural și alte domenii ale informaticii moderne. Timp de doi ani, studenții studiază discipline care de obicei nu sunt incluse în programele universitare, deși sunt la mare căutare atât în ​​știință, cât și în industrie. Puteți studia nu numai la Moscova - Școala are filiale în Ekaterinburg, Minsk, Kiev, Novosibirsk, Sankt Petersburg. Există, de asemenea extramural, unde puteți studia vizionând prelegeri video și coresponzând cu profesorii Școlii din Moscova prin poștă.

Dar pentru a intra în ShAD, trebuie să parcurgeți cu succes trei etape - completați un formular de cerere pe site, promovați examenul de admitere și veniți la un interviu. În fiecare an, studenții seniori, absolvenții și absolvenții de la Universitatea de Stat din Moscova, Institutul de Fizică și Tehnologie din Moscova, Școala Superioară de Economie, ITMO, Universitatea de Stat din Sankt Petersburg, UrFU, NSU intră în ShAD și nu toți fac față testelor noastre. Anul acesta am primit chestionare de la 3500 de persoane, dintre care 1000 au fost admiși la examen și doar 350 l-au promovat cu succes.

Pentru cei care vor să se încerce singuri și să înțeleagă de ce sunt capabili, am pregătit o analiză a examenului de admitere din acest an. Opțiunea pe care am ales-o pentru tine a fost completată de 56% dintre cei care au rezolvat-o. În acest tabel, puteți vedea câți oameni au fost capabili să rezolve fiecare dintre sarcinile din acesta.

Dar mai întâi, aș dori să explic ce verificăm cu examenul și cum abordăm pregătirea lui. În primii ani de existență a SAD, nu a existat examen scris, deoarece încă erau puține aplicații, și era posibil să discutăm personal cu toți cei care au promovat testul online. Dar apoi interviurile au fost mai lungi; unii absolvenți își amintesc că au fost intervievați timp de șase ore, oferind multe sarcini provocatoare. Apoi au fost mai mulți candidați – iar în 2012 a apărut un examen scris.

Curatorii Moscow ShAD sunt implicați în crearea variantei, dintre care unul sunt; cu selecţia sarcinilor sunt asistaţi de colegi din filiale. Numărul sarcinilor din variantă nu s-a schimbat prea mult în acești patru ani: la început au fost șapte, iar anul trecut au fost opt. Fiecare opțiune are probleme de matematică (de la cinci la șapte) și probleme de algoritm (una sau două).

În ceea ce privește matematica, verificăm, desigur, dacă solicitanții stăpânesc principalele secțiuni ale programului: algebră, analiză matematică, combinatorică și teoria probabilităților. Dar ceea ce este important pentru noi nu este cunoștințele care se obțin prin înghesuială și uitate la o săptămână după test sau examen - ca niște formule groaznice de la masă integrale nedefinite sau funcțiile de distribuție ale Studentului; de aceea, le permitem candidaților să ia cu ei orice sursă de hârtie la examenul scris. Mult mai valoroasă este înțelegerea esenței a ceea ce se întâmplă, precum și capacitatea de a aplica fapte și metode standard în situații neobișnuite. De asemenea, încercăm să menținem complexitatea computațională la minimum; chiar și numerele din două cifre trebuie înmulțite rar. Deci, în timpul examenului, nu vei întâlni exerciții de calcul de rutină și plictisitoare, iar multe sarcini vor părea nestandardizate și, poate, chiar olimpiade.

În partea de algoritm, evităm problemele care necesită cunoașterea unor structuri de date specifice (arbori de căutare, tabele hash, etc.) sau algoritmi (algoritmi de sortare rapidă, algoritmi de cea mai scurtă cale de grafică etc.). În plus, nu solicităm solicitanților să scrie o implementare a unui algoritm inventat în niciun limbaj de programare; mai degrabă, dimpotrivă - în toate modurile posibile descurajăm acest lucru. Într-adevăr, la examenul scris, ne interesează cel mai mult nu abilitățile de programare, ci capacitatea de a descrie clar algoritmul și, dacă este necesar, de a convinge cititorul că îndeplinește restricțiile privind timpul de rulare și cantitatea de memorie alocată. Totuși, sunt acceptate și deciziile care conțin cod în orice limbă pe care o putem citi, dar sunt mai greu de verificat și, în plus, trebuie să fie însoțite de o justificare a corectitudinii.

Sarcina 1

Răspuns

Soluţie

Să demonstrăm mai întâi că șirul converge. Dacă un n< 0 , Acea un n+1< 0 , deci este mărginită de sus. Să comparăm un nȘi un n+1:

Sarcina 2

Răspuns

Soluţie

Vom monitoriza poziția centrului cercului. Este clar că ne putem limita considerația la interiorul unui singur dreptunghi. Este ușor de observat că pentru ca cercul să intersecteze exact trei dreptunghiuri, trebuie îndeplinite două condiții: (1) distanțele de la centru până la cele mai apropiate două laturi ale dreptunghiului trebuie să fie mai mici de 4; (2) distanța până la cel mai apropiat vârf al dreptunghiului trebuie să fie mai mare decât 4. Știind acest lucru, putem desena o mulțime de puncte care îndeplinesc aceste condiții.

Prin urmare, probabilitatea dorită este egală cu

Sarcina 3

Răspuns

Cu strategia corectă, Vanya va câștiga.

Soluţie

Matricea rezultată A va avea o valoare proprie de 1 dacă matricea A - E va fi degenerat. Vanya poate realiza acest lucru, de exemplu, în felul următor. După ce Dima a intrat într-un element aij, Vanya intră într-un element nou aik pe aceeași linie astfel încât a ik -δ ik =-(a ij -δ ij), Unde δij este simbolul Kronecker. Apoi suma numerelor din fiecare rând al matricei A-E va fi egal cu zero, adică matricea A - E va fi degenerat.

Sarcina 4

Răspuns

Soluţie

Folosim formula Scăderea precedentă din fiecare rând al matricei, iar apoi pe cea anterioară din fiecare coloană. Matricea rezultată va arăta astfel:

Sarcina 5

Soluţie

Acest lucru se poate face într-o singură trecere prin matricea a. De fiecare dată când întâlnim un element de matrice b, îl scriem și numărul său în tablouri speciale. În același timp, menținem segmentul I în aceste matrice, pe care sperăm să găsim toate elementele diferite b. Este clar că dacă următorul element al matricei a coincide cu primul element al segmentului I, atunci în mod clar nu pot fi cel mai scurt un segment care satisface condiția problemei și îi putem muta capătul din stânga. Dacă la pasul următor înțelegem că I conține toate elementele distincte b, atunci eu sunt candidat pentru răspuns; în acest caz, îi deplasăm și capătul din stânga.

Nota Pe) evident din memorie. Nota O(nk) complexitatea poate fi justificată după cum urmează: facem totul într-o singură trecere (deci n) și la fiecare pas trebuie să caute un element în matrice b(deci k). Este clar că algoritmul poate fi îmbunătățit: dacă mai întâi sortăm bși folosiți căutarea binară, obținem O(n log k). Dacă utilizați hashing perfect, atunci puteți obține complexitate O(n+k).

Sarcina 6

Soluţie

Să fim de acord că fiecare echipă pentru turneu primește puncte egale cu numărul de echipe depășite de ea. Mai întâi demonstrăm următoarea lemă simplă:

Lema. Lăsați echipa E să nu depășească echipa K. Apoi K a marcat mai multe puncte decât E.

Dovada. Dacă E nu depășește K, atunci K a învins Echipa E, precum și toate echipele pe care le-a câștigat Echipa E.

Acum să fie X echipa învinsă de echipa E. Dacă E l-a învins pe X, atunci K l-a învins și pe X. Deci K îl învinge pe X. Dacă E a învins echipa F, care l-a învins pe X, atunci rețineți că K a câștigat și F. Deci, K a învins F, care l-a învins pe X, adică K îl învinge pe X. În total, K bate toate echipele care l-au învins pe E, și chiar și pe E pentru a porni, adică cu cel puțin o echipă mai mult decât E Lema este dovedită.

(a) Fie A echipa cu cele mai multe puncte. Să demonstrăm că A este campion. Să spunem că nu, atunci există echipa B pe care A nu a învins-o. După lemă, obținem că B a câștigat mai multe puncte decât A. O contradicție.

(b) Să presupunem că avem doi campioni: A și B. S-au jucat între ei; să câștige, de exemplu, A. Deoarece B este superior tuturor celorlalte echipe (și în special A), atunci B a învins o echipă care a câștigat împotriva lui A.

Să presupunem pentru început că există echipe care au câștigat atât A, cât și B. Atunci se poate demonstra că cea dintre ele (să-i spunem C), care a marcat cele mai multe puncte, va fi al treilea campion. Într-adevăr, fie E echipa care nu a fost învinsă de C. Apoi, în primul rând, E a câștigat atât A cât și B, iar în al doilea rând, E a câștigat mai multe puncte decât C. O contradicție.

Să presupunem acum că nu există echipe care au câștigat atât A cât și B. Luați în considerare setul tuturor astfel de echipe care au câștigat A dar au pierdut B. Rețineți că nu este gol (vezi mai sus). Dintre acestea, luați echipa cu cel mai mare număr de puncte. Apoi, folosind lema, putem stabili că această echipă este a treia campioană.

Sarcina 7

Educaţie

În 2017, intrați în ShAD (Școala de Analiză a Datelor) Yandex.

Buna ziua!

Numele meu este Vladimir, am 26 de ani. Am mai multe studii superioare (inginer metalurgic și economie și management al întreprinderii). Am primit ambele studii la Institutul de Oțel și Aliaje din Moscova. În prezent lucrez ca Project Manager într-una dintre companiile IT autohtone, care este un furnizor de sisteme informatice de management al producției. La locul de muncă, întâmpin constant nevoia de a agrega și transfera date, de a integra diverse sisteme folosind Enterprise Service Bus (ESB). Am auzit de ShAD în urmă cu un an, dar anul precedent a fost foarte aglomerat - predarea tezelor la programele a doua superioare și de master, admiterea la școala superioară. În plus, au existat o mulțime de călătorii de afaceri prelungite, de lucru. Momentan, nu este atât de ocupat, așa că cred că mă voi ocupa în sfârșit de problema pregătirii și admiterii. Pentru data curenta, ma simt putin mai mult decat complet nepregatita;) Tot institutul matan este uitat. În combinatorică și ter.ver am studiat materialul pe cont propriu. În programare, am învățat Python pe cont propriu (cu ajutorul cursurilor pe cursur și stepik). Cred ca trainingul va fi distribuit ca complexitate si incarcare astfel: Matan - 50%, Combinatorics si Ter.Ver. - 30%, Programare - 20%.

De ce ați decis să utilizați acest serviciu? Totul este simplu. Cred că mă va ajuta să țin evidența dinamicii și poate să găsesc oameni care să mă ajute sau pe care să mă ajut :)

Criterii de reziliere

Înscrierea în SAD. Nu neapărat pentru un departament cu normă întreagă, dar de preferință pentru un loc cu buget.

Resurse personale

Resursele pentru această sarcină sunt Timpul și Informația. Timpul este strâns, nu. muncă, călătorii de afaceri și pregătire pentru studenți.

Este posibil să aveți nevoie de bani pentru a plăti cursurile sau un tutore. Nu există probleme speciale cu banii.

Green Goal

Vreau să intru în ShAD pentru a obține cunoștințe unice care mă vor ajuta în viitor. Aceste cunoștințe sunt date de oameni absolut unici, cunoștințe cu care, sunt sigur, nu vor fi absolut de prisos în viața mea. În plus, aceasta este o provocare bună pentru a demonstra independența, auto-organizarea și capacitatea de a-ți atinge obiectivele.

Vara este timpul pentru examenele de admitere. În acest moment, selecția la Școala de Analiză a Datelor Yandex este în curs de finalizare - sunt în curs de desfășurare interviuri pentru cei care au promovat deja examenul. Școala de Informatică predă învățarea automată, viziunea computerizată, analiza textului în limbaj natural și alte domenii ale informaticii moderne. Timp de doi ani, studenții studiază discipline care de obicei nu sunt incluse în programele universitare, deși sunt la mare căutare atât în ​​știință, cât și în industrie. Puteți studia nu numai la Moscova - Școala are filiale în Ekaterinburg, Minsk, Kiev, Novosibirsk, Sankt Petersburg. Există, de asemenea, un departament de corespondență, unde puteți studia vizionând prelegeri video și coresponzând cu profesorii Școlii din Moscova prin poștă.

Dar pentru a intra în ShAD, trebuie să parcurgeți cu succes trei etape - completați un formular de cerere pe site, promovați examenul de admitere și veniți la un interviu. În fiecare an, studenții seniori, absolvenții și absolvenții de la Universitatea de Stat din Moscova, Institutul de Fizică și Tehnologie din Moscova, Școala Superioară de Economie, ITMO, Universitatea de Stat din Sankt Petersburg, UrFU, NSU intră în ShAD și nu toți fac față testelor noastre. Anul acesta am primit chestionare de la 3500 de persoane, dintre care 1000 au fost admiși la examen și doar 350 l-au promovat cu succes.

Pentru cei care vor să se încerce singuri și să înțeleagă de ce sunt capabili, am pregătit o analiză a examenului de admitere din acest an. Opțiunea pe care am ales-o pentru tine a fost completată de 56% dintre cei care au rezolvat-o. În acest tabel, puteți vedea câți oameni au fost capabili să rezolve fiecare dintre sarcinile din acesta.

Dar mai întâi, aș dori să explic ce verificăm cu examenul și cum abordăm pregătirea lui. În primii ani de existență a SAD, nu a existat examen scris, deoarece încă erau puține aplicații, și era posibil să discutăm personal cu toți cei care au promovat testul online. Dar apoi interviurile au fost mai lungi; unii absolvenți își amintesc că au fost intervievați timp de șase ore, oferind multe sarcini provocatoare. Apoi au fost mai mulți candidați – iar în 2012 a apărut un examen scris.

Curatorii Moscow ShAD sunt implicați în crearea variantei, dintre care unul sunt; cu selecţia sarcinilor sunt asistaţi de colegi din filiale. Numărul sarcinilor din variantă nu s-a schimbat prea mult în acești patru ani: la început au fost șapte, iar anul trecut au fost opt. Fiecare opțiune are probleme de matematică (de la cinci la șapte) și probleme de algoritm (una sau două).

În ceea ce privește matematica, verificăm, desigur, dacă solicitanții stăpânesc principalele secțiuni ale programului: algebră, calcul, combinatorie și teoria probabilităților. Dar ceea ce este important pentru noi nu sunt cunoștințele care se obțin prin înghesuială și uitate la o săptămână după test sau examen - ca niște formule groaznice din tabelul integralelor nedefinite sau funcția de distribuție a Studentului; de aceea, le permitem candidaților să ia cu ei orice sursă de hârtie la examenul scris. Mult mai valoroasă este înțelegerea esenței a ceea ce se întâmplă, precum și capacitatea de a aplica fapte și metode standard în situații neobișnuite. De asemenea, încercăm să menținem complexitatea computațională la minimum; chiar și numerele din două cifre trebuie înmulțite rar. Deci, în timpul examenului, nu vei întâlni exerciții de calcul de rutină și plictisitoare, iar multe sarcini vor părea nestandardizate și, poate, chiar olimpiade.

În partea de algoritm, evităm problemele care necesită cunoașterea unor structuri de date specifice (arbori de căutare, tabele hash, etc.) sau algoritmi (algoritmi de sortare rapidă, algoritmi de cea mai scurtă cale de grafică etc.). În plus, nu solicităm solicitanților să scrie o implementare a unui algoritm inventat în niciun limbaj de programare; mai degrabă, dimpotrivă - în toate modurile posibile descurajăm acest lucru. Într-adevăr, la examenul scris, ne interesează cel mai mult nu abilitățile de programare, ci capacitatea de a descrie clar algoritmul și, dacă este necesar, de a convinge cititorul că îndeplinește restricțiile privind timpul de rulare și cantitatea de memorie alocată. Totuși, sunt acceptate și deciziile care conțin cod în orice limbă pe care o putem citi, dar sunt mai greu de verificat și, în plus, trebuie să fie însoțite de o justificare a corectitudinii.

Sarcina 1

Răspuns

Soluţie

Să demonstrăm mai întâi că șirul converge. Dacă un n< 0 , Acea un n+1< 0 , deci este mărginită de sus. Să comparăm un nȘi un n+1:

Sarcina 2

Răspuns

Soluţie

Vom monitoriza poziția centrului cercului. Este clar că ne putem limita considerația la interiorul unui singur dreptunghi. Este ușor de observat că pentru ca cercul să intersecteze exact trei dreptunghiuri, trebuie îndeplinite două condiții: (1) distanțele de la centru până la cele mai apropiate două laturi ale dreptunghiului trebuie să fie mai mici de 4; (2) distanța până la cel mai apropiat vârf al dreptunghiului trebuie să fie mai mare decât 4. Știind acest lucru, putem desena o mulțime de puncte care îndeplinesc aceste condiții.

Prin urmare, probabilitatea dorită este egală cu

Sarcina 3

Răspuns

Cu strategia corectă, Vanya va câștiga.

Soluţie

Matricea rezultată A va avea o valoare proprie de 1 dacă matricea A - E va fi degenerat. Vanya poate realiza acest lucru, de exemplu, în felul următor. După ce Dima a intrat într-un element aij, Vanya intră într-un element nou aik pe aceeași linie astfel încât a ik -δ ik =-(a ij -δ ij), Unde δij este simbolul Kronecker. Apoi suma numerelor din fiecare rând al matricei A-E va fi egal cu zero, adică matricea A - E va fi degenerat.

Sarcina 4

Răspuns

Soluţie

Folosim formula Scăderea precedentă din fiecare rând al matricei, iar apoi pe cea anterioară din fiecare coloană. Matricea rezultată va arăta astfel:

Sarcina 5

Soluţie

Acest lucru se poate face într-o singură trecere prin matricea a. De fiecare dată când întâlnim un element de matrice b, îl scriem și numărul său în tablouri speciale. În același timp, menținem segmentul I în aceste matrice, pe care sperăm să găsim toate elementele diferite b. Este clar că dacă următorul element al matricei a coincide cu primul element al segmentului I, atunci în mod clar nu pot fi cel mai scurt un segment care satisface condiția problemei și îi putem muta capătul din stânga. Dacă la pasul următor înțelegem că I conține toate elementele distincte b, atunci eu sunt candidat pentru răspuns; în acest caz, îi deplasăm și capătul din stânga.

Nota Pe) evident din memorie. Nota O(nk) complexitatea poate fi justificată după cum urmează: facem totul într-o singură trecere (deci n) și la fiecare pas trebuie să caute un element în matrice b(deci k). Este clar că algoritmul poate fi îmbunătățit: dacă mai întâi sortăm bși folosiți căutarea binară, obținem O(n log k). Dacă utilizați hashing perfect, atunci puteți obține complexitate O(n+k).

Sarcina 6

Soluţie

Să fim de acord că fiecare echipă pentru turneu primește puncte egale cu numărul de echipe depășite de ea. Mai întâi demonstrăm următoarea lemă simplă:

Lema. Lăsați echipa E să nu depășească echipa K. Apoi K a marcat mai multe puncte decât E.

Dovada. Dacă E nu depășește K, atunci K a învins Echipa E, precum și toate echipele pe care le-a câștigat Echipa E.

Acum să fie X echipa învinsă de echipa E. Dacă E l-a învins pe X, atunci K l-a învins și pe X. Deci K îl învinge pe X. Dacă E a învins echipa F, care l-a învins pe X, atunci rețineți că K a câștigat și F. Deci, K a învins F, care l-a învins pe X, adică K îl învinge pe X. În total, K bate toate echipele care l-au învins pe E, și chiar și pe E pentru a porni, adică cu cel puțin o echipă mai mult decât E Lema este dovedită.

(a) Fie A echipa cu cele mai multe puncte. Să demonstrăm că A este campion. Să spunem că nu, atunci există echipa B pe care A nu a învins-o. După lemă, obținem că B a câștigat mai multe puncte decât A. O contradicție.

(b) Să presupunem că avem doi campioni: A și B. S-au jucat între ei; să câștige, de exemplu, A. Deoarece B este superior tuturor celorlalte echipe (și în special A), atunci B a învins o echipă care a câștigat împotriva lui A.

Să presupunem pentru început că există echipe care au câștigat atât A, cât și B. Atunci se poate demonstra că cea dintre ele (să-i spunem C), care a marcat cele mai multe puncte, va fi al treilea campion. Într-adevăr, fie E echipa care nu a fost învinsă de C. Apoi, în primul rând, E a câștigat atât A cât și B, iar în al doilea rând, E a câștigat mai multe puncte decât C. O contradicție.

Să presupunem acum că nu există echipe care au câștigat atât A cât și B. Luați în considerare setul tuturor astfel de echipe care au câștigat A dar au pierdut B. Rețineți că nu este gol (vezi mai sus). Dintre acestea, luați echipa cu cel mai mare număr de puncte. Apoi, folosind lema, putem stabili că această echipă este a treia campioană.

Sarcina 7

Yandex deschide o nouă înscriere la Școala de Analiză a Datelor. Acestea sunt cursuri serale gratuite de doi ani pentru cei care doresc să obțină o educație în domeniul prelucrării și analizei datelor și al extragerii de informații de pe Internet. Școala necesită o bună pregătire matematică și este destinată în primul rând studenților și tinerilor absolvenți ai specialităților de inginerie și matematică.

Cum se procedează

Trebuie să completați un formular pe site-ul școlii până pe 15 mai. După aceea, veți primi un e-mail cu un link către un test online de matematică și programare de bază. Toți cei care au absolvit cu succes proba vor fi invitați de școală la un examen scris, care va avea loc la sfârșitul lunii mai – începutul lunii iunie. Cele mai bune rezultate ale examenului vor trebui să treacă printr-un interviu, în urma căruia se va lua o decizie finală.

Program de antrenament

Pe site-ul școlii, puteți studia sarcinile de examen din anii trecuți și puteți afla pentru ce ar trebui să vă pregătiți. Puteți face cunoștință cu profesorii școlii și puteți afla despre noua direcție „Big Data” la Ziua porților deschise a ShAD. Va avea loc 19 aprilieîn biroul Yandex din Moscova, pentru a participa trebuie să vă înregistrați.

Cursurile la SHAD au loc seara în zilele lucrătoare. Puteți studia la școală personal sau în absență, conform prelegerilor video. În timpul pregătirii sau după absolvire, studenții pot face un stagiu la Yandex.

Școala de Analiză a Datelor există din 2007 și a absolvit peste 300 de specialiști, mulți dintre care sunt implicați în știință, lucrează pentru Yandex și alte companii IT mari din Rusia și din străinătate. Filiale ale ShAD există în Sankt Petersburg (în cadrul Centrului de Informatică), Novosibirsk, Ekaterinburg, Minsk și Kiev.