Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

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

Revision en1, by 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?

Thanks!

Tags ternary search, binary search

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English foundLoveOfMyLife 2016-01-15 21:32:15 1137 Initial revision (published)