Codeforces исполнилось 10 лет! Мы рады анонсировать краудфандинг-кампанию. Поздравьте нас по ссылке ×

How to find the Shape of a discrete function defined from N -> R

Правка en1, от foundLoveOfMyLife, 2016-01-15 21:32:15

Hello, The latest Round had a problem named Skills( Link ) .

My approach was to assume the function to be dependent on Minimum Number( Note Frequency of A_MAX is also dependent on Minimum Number as The M left after achieving minimum number will be used to make maximum frequency of A_MAX) :

C_F * Minimum No + C_M * Frequency of A_MAX

Now ,
I assumed this function to be just judging the function at the two extreme points i.e. Minimum No. is what it is now or is A_MAX . And I had kind of feeling that it will have only one maxima like

Then I thought of applying ternary search on integers which can be done using Binary search as mentioned in this blog Blog .

And Got a WA : 15382925

So probably the function might have more than one maxima's.

Is there someway to determine the shape and number of maxima's of a discrete function?


Теги ternary search, binary search


  Rev. Язык Кто Когда Δ Комментарий
en1 Английский foundLoveOfMyLife 2016-01-15 21:32:15 1137 Initial revision (published)