a faster egg dropping solution?

Revision en1, by hiddentesla, 2016-10-12 12:25:42

http://www.spoj.com/problems/NPC2015E/ it looks like a normal egg dropping problem, but the constraints of the last subtask is really huge. here are some observations i made:

  1. if (k=2) answer is the smallest x where x*(x+1) >= 2*n

  2. if (k=1) answer is n

  3. if(k>= log2(n)) answer is floor(log2(n)) (because we can do binary search)

however, using these three observations, its still not enough to beat the last subtask, because if the input is 10e18 and 5, it would be TLE

is there a faster solution? i tried googling and found a math solution for 2 eggs only

Tags dynamic-programming

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English hiddentesla 2016-10-12 12:25:42 615 Initial revision (published)