Conţinutul numărului revistei |
Articolul precedent |
Articolul urmator |
964 31 |
Ultima descărcare din IBN: 2024-04-17 09:59 |
Căutarea după subiecte similare conform CZU |
004.02 (22) |
Știința și tehnologia calculatoarelor. Calculatoare. Procesarea datelor (4156) |
SM ISO690:2012 CERCELESCU, Şerban. The trick from Aliens in competitive programming. In: Acta et commentationes (Ştiinţe ale Educaţiei), 2019, nr. 4(18), pp. 104-108. ISSN 1857-0623. DOI: https://doi.org/10.36120/2587-3636.v18i4.104-108 |
EXPORT metadate: Google Scholar Crossref CERIF DataCite Dublin Core |
Acta et commentationes (Ştiinţe ale Educaţiei) | ||||||
Numărul 4(18) / 2019 / ISSN 1857-0623 /ISSNe 2587-3636 | ||||||
|
||||||
DOI:https://doi.org/10.36120/2587-3636.v18i4.104-108 | ||||||
CZU: 004.02 | ||||||
Pag. 104-108 | ||||||
|
||||||
Descarcă PDF | ||||||
Rezumat | ||||||
The scope of this article is presenting a very useful DP optimization technique, introduced in the competitive programming community with the problem Aliens at IOI 2016. The technique is used to reduce dimensions in particular DP configurations, by exploiting the convex nature of some cost functions. We will introduce the technique by starting with a simpler DP problem, show the optimization from O(N2) to O(Nlog VAL) then reveal the full solution of the original problem. Apparently, the official name of this optimization technique is “parameter search” and the Chinese community calls it “wqs binary search”. |
||||||
Cuvinte-cheie dynamic programming, parameter search, competitive programming, programare dinamică, căutare de parametri, programare competitivă |
||||||
|