Овде ћемо посматрати задатак који су такмичари решавали на интернационалној олимпијади из информатике 2017. године у мало измењеном облику због једноставности анализе решења.
Задатак у неизмењеном облику се може пронаћи овде.
Задатак
Посматрајмо следећу игру:
Нека је N (1 <= N <= 100 000) кутија, које су згодно обележене са лева на десно бројевима од 1 до N, поређано у низ, и нека се у свакој кутији налази по тачно један поклон. Постоји k типова поклона, и за сваки тип се зна која му је вредност (поклон типа 1 је највреднији, поклон типа 2 је мало мање вредан, …, поклон типа k је најмање вредан). На почетку су све кутије затворене, те не можемо да видимо који се поклон налази у којој кутији, али знамо следеће:
- Највреднији поклон (поклон типа 1) се налази у тачно једној кутији,
- Уколико означимо са b[t] број поклона типа t онда знамо да за свако r (2 <= r <= n) важи (b[1] + b[2] … b[r-1])^2 < b[r], тј. квадрат броја свих поклона који су типа мањег од r је мањи од броја поклона типа r,
- У свакој кутији, када је отворена, се поред поклона могу видети и два броја (означимо их са l[i] и r[i] за кутију i). Први од та два броја (l[i]) представља број свих кутија које се налазе лево од кутије i и садрже поклон вредности веће од поклона у кутији i. Слично, други број (d[i]) представља број свих кутија које се налазе десно од кутије i и садрже поклон вредности веће од поклона у кутији i.
Једино што можемо да радимо у овој игри јесте да отварамо кутије једну по једну у било ком редоследу све док не нађемо кутију са највреднијим поклоном. Наш задатак је да нађемо кутију са највреднијим поклоном, а да при томе не отворимо више од 10 000 кутија.
Приметимо да не знамо број k, тј. не знамо колико типова поклона постоји. Исто тако, гледајући само у поклон не знамо да одредимо којег је он типа.
Решење
Да смо отворили кутију са највреднијим поклоном ћемо приметити по томе што су оба броја која се налазе у тој кутији поред поклона једнака 0 због тога што не постоји ниједна кутија ни лево ни десно од те кутије која садржи вреднији поклон.
Уколико бисмо отварали насумично једну по једну кутију онда бисмо у најгорем случају отворили свих N кутија, те у случају када је N > 10 000 не бисмо успели да задовољимо услов да смемо отворити највише 10 000 кутија.
Посматрајмо случај када постоји тачно само 2 типа поклона. У том случају бисмо имали ситуацију да једна кутија садржи поклон типа 1, а преосталих N-1 кутија садржи поклон типа 2. Уколико отворимо кутију која се налази са леве стране кутије која садржи највреднији поклон, у отвореној кутији ћемо видети да је l=0 и r=1. Слично, када отворимо кутија која се налази са десне стране кутије која садржи највреднији поклон, у отвореној кутији ћемо затећи бројеве l=1 и r=0. Ово можемо искористити, те користећи бинарну претрагу пронаћи кутију са највреднијим поклоном. Овим поступком ћемо у најгорем случају отворити ⌈log2(N)⌉<17 кутија.
Сада ћемо решити општи случај. Приметимо други услов у тексту игре, ”квадрат броја свих поклона који су типа мањег од r је мањи од броја поклона типа r”. Уколико користећи ово покушамо да направимо низ са што више типова поклона добићемо да је максималан број различитих типова поклона 5 (један пример таквог низа би био (b[1], b[2], b[3], b[4], b[5])=(1,2,10,170,N-1-2-10-170)).
Важније, закључак који можемо да донесемо јесте да постоји мање од sqrt(N) кутија које садрже поклоне типова од 1 до k-1, где sqrt(N) означава корен из броја N. Ово можемо да закључимо на следећи начин:
- Означимо са x укупан број кутија које садрже поклоне типова од 1 до k-1
- Из претходног следи да је број кутија које садрже поклоне типа k већи од x^2
- Укупан број кутија можемо представити са x+(x^2+y) = N где су x и y природни бројеви
- Из овога можемо закључити x = sqrt(x^2) < sqrt(x + (x^2 + y)) = sqrt(N)
Приметимо да је sqrt(N) < 317, што значи да када бисмо знали где су кутије које садрже поклоне типова од 1 до k-1 могли бисмо да отворимо сваку од тих кутија и видимо где се налази највреднији поклон. Ово нам и јесте идеја решења, покушаћемо паметно да нађемо и отворимо све кутије које не садрже поклон типа k.
Прво ћемо покушати да сазнамо колико тачно постоји кутија које нису типа k. Како знамо да тих кутија има мање од sqrt(N) можемо закључити да уколико отворимо било којих ⌈sqrt(N)⌉ различитих кутија барем једна од њих мора садржати поклон најмање вредности. Ово значи да уколико отворимо на пример првих ⌈sqrt(N)⌉ кутија и узмемо максимум l[i]+r[i], сазнаћемо колико има кутија које не садрже највреднији поклон. Означимо тај број са brVrednijihKutija.
Сада када знамо колико таквих кутија постоји, можемо бинарном претрагом тражити једну по једну (на пример са лева на десно) и отварати сваку од њих. Бинарну претрагу ћемо радити на следећи начин.
Претпоставимо да смо да смо до сада пронашли првих t кутија са лева које нису типа k и нека смо последњу пронашли на позицији pos. Из овога знамо да се преосталих brVrednijihKutija-t таквих кутија налазе на позицијама од pos+1 до N.
Означимо са levo=pos+1 и desno=N. Сада када знамо интервал у ком тражимо следећу кутију можемо да започнемо бинарну претрагу. Израчунамо средину интервала, на почетку је то sred=(levo+desno) / 2, и отворимо ту кутију. Када отворимо ту кутију постоје два случаја:
- У кутији се налази поклон који није типа k, (l[sred]+r[sred]<brVrednijihKutija)
- У кутији се налази поклон типа k, (l[sred]+r[sred]=brVrednijihKutija)
Решимо прво први случај. Уколико се у кутији налази поклон који није типа k онда знамо да нашу претрагу можемо наставити на интервалу [levo, sred], пошто на том интервалу сигурно постоји барем једна таква кутија.
Сада ћемо решити други случај. Приметимо да када год отворимо кутију у којој се налази поклон типа k сума l[i]+r[i] ће увек бити иста. Једино што ће се мењати јесте појединачно ти бројеви, како повећавамо i тако ће се l[i] повећавати, док ће се r[i] смањивати. Сада када у овом случају отворимо кутију sred и она је типа k, ми на основу броја l[sred] можемо да закључимо на коју страну бинарна претрага треба да буде настављена. Уколико је l[sred]=t (t је број кутија које нису типа k и које смо до сада пронашли) то значи да се у свим кутијама од позиције pos+1 до позиције sred налази поклон типа k па нашу претрагу треба да наставимо на интервалу [sred+1,desno]. На сличан начин можемо да закључимо да уколико је l[sred]>t нашу претрагу треба да наставимо на интервалу [levo,sred-1].
Овим поступком ћемо проначи и отворити све кутије са поклонима типова од 1 до k-1, те ћемо сазнати где се налази кутија са највреднијим поклоном.
Остало је да израчунамо колико ћемо кутија отворити у најгорем случају. На почетку ћемо отворити ⌈sqrt(N)⌉ кутија, те ћемо након тога урадити бинарну претрагу највише sqrt(N) пута пошто највише толико кутија садржи поклон типа од 1 до k-1. Како бинарна претрага у најгорем случају отвара ⌈log(N)⌉ кутија, ми ћемо у најгорем случају отворити sqrt(⌈N⌉)+sqrt(N)*⌈log(N)⌉<5 700 кутија.