Conţinutul numărului revistei |
Articolul precedent |
Articolul urmator |
1004 32 |
Ultima descărcare din IBN: 2024-05-12 08:59 |
Căutarea după subiecte similare conform CZU |
004.02 (22) |
Știința și tehnologia calculatoarelor. Calculatoare. Procesarea datelor (4225) |
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ă |
||||||
|
DataCite XML Export
<?xml version='1.0' encoding='utf-8'?> <resource xmlns:xsi='http://www.w3.org/2001/XMLSchema-instance' xmlns='http://datacite.org/schema/kernel-3' xsi:schemaLocation='http://datacite.org/schema/kernel-3 http://schema.datacite.org/meta/kernel-3/metadata.xsd'> <identifier identifierType='DOI'>10.36120/2587-3636.v18i4.104-108</identifier> <creators> <creator> <creatorName>Cercelescu, .</creatorName> <affiliation>Liceul Internațional de Informatică, Bucuresti, România</affiliation> </creator> </creators> <titles> <title xml:lang='en'>The trick from Aliens in competitive programming</title> </titles> <publisher>Instrumentul Bibliometric National</publisher> <publicationYear>2019</publicationYear> <relatedIdentifier relatedIdentifierType='ISSN' relationType='IsPartOf'>1857-0623</relatedIdentifier> <subjects> <subject>dynamic programming</subject> <subject>parameter search</subject> <subject>competitive programming</subject> <subject>programare dinamică</subject> <subject>căutare de parametri</subject> <subject>programare competitivă</subject> <subject schemeURI='http://udcdata.info/' subjectScheme='UDC'>004.02</subject> </subjects> <dates> <date dateType='Issued'>2019-11-27</date> </dates> <resourceType resourceTypeGeneral='Text'>Journal article</resourceType> <descriptions> <description xml:lang='en' descriptionType='Abstract'><p>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(N<sup>2</sup>) 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”.</p></description> <description xml:lang='ro' descriptionType='Abstract'><p>Scopul acestui articol reprezintă ilustrarea unei tehnici de optimizare a DP foarte utilă, introdusă în comunitatea de programare competitivă odată cu problema Aliens la Olimpiada Internațională de Informatică din 2016. Tehnica este utilizată pentru a reduce dimensiunile în anumite configurații DP, prin exploatarea caracterului convex al unor funcții de cost. Vom introduce această tehnică începând cu o problemă DP mai simplă, vom arăta optimizarea de la O(N<sup>2</sup>) la O(Nlog VAL) , apoi vom dezvălui soluția completă a problemei originale. Aparent, denumirea oficială a acestei tehnici de optimizare este „căutare de parametri”, iar comunitatea chineză o numește „căutare binară wqs”.</p></description> </descriptions> <formats> <format>application/pdf</format> </formats> </resource>