TopCoder SRM 752 a fost prima rundă a săptămânii trecute (probleme, rezultate, top 5 în stânga, analiză). rng_58 și-a menținut avantajul în cursa pentru cel de-al treilea loc TCO19 și a fost destul de aproape de a-și mări avantajul și mai mult, el fiind la doar 4 puncte în spatele primului loc înainte de faza de provocare, iar pashka se afla în afara primului 10. Cu toate acestea, turistii au găsit 100 a provocat puncte și a câștigat (felicitări!) și pashka a găsit 50 de puncte provocare și a sărit exact pe locul 10, ceea ce înseamnă că atât rng_58, cât și pashka au obținut 4 puncte de turneu pentru această rundă.

săptămână

Codeforces și-a ținut Runda 545 vineri devreme (probleme, rezultate, top 5 în stânga, analiză). Numai apusul soarelui a reușit să rezolve problema F foarte dificilă, astfel încât nici măcar depășirea limitei de memorie din problema C (datorită implementării unei soluții optime asimptotic, dar cu o constantă uriașă atât pentru timp cât și pentru memorie) nu a schimbat rezultatul. Felicitări pentru câștig!

Open Cup 2018-19 Grand Prix al Chinei a încheiat săptămâna (rezultate, top 5 pe stânga, analiză). Toate problemele au fost rezolvabile în această rundă, dar toate au necesitat destul de multă gândire și destul de puțin codificare și, de asemenea, așa cum a formulat zeliboba destul de succint, a avut câteva cazuri de colț oarecum inutile. Team Past Glory a prevalat încă în acele condiții dificile, cu ultima problemă acceptată la 4:59. Foarte bine!

Problema E din această rundă mi-a amintit de postarea mea anterioară în care am încercat să descriu o modalitate de a găsi stări de programare dinamică semi-automat. Problema a decurs astfel: să definim f (X) ca cel mai mic număr negativ care poate fi obținut plasând + sau - înaintea fiecărei cifre în reprezentarea zecimală a X, și calculând suma rezultată. Care este suma tuturor numerelor X între l și r care au f (X) egal cu 0, 1,…, 9, modulo 10 9 +7? l și r au cel mult 100 de cifre și există 10000 de probe de rezolvat în 2 secunde.

Ideea de a utiliza o programare dinamică este la suprafață, dar nu este clar cum se poate obține un număr gestionabil de stări. Vedeți o modalitate de a găsi un spațiu de stare mic algoritmic?

Vă mulțumim pentru lectură și reveniți săptămâna viitoare!