Solution for Cute Quiz #1
I posted "Cute Quiz #1" 4 weeks ago. For the first 2 weeks nobody submitted a solution, but then I found the Chrome pillow in the box with my children's stuffed toys.
Soon after I advertised the pillow, five people submitted working solutions. Two said they would like the pillow to go to someone else, so I had to pick a winner out of three. I did choose by throwing a real 🎲.
And the winner is Victor Stoian. Congrats!
Let's talk about the solution now. Fetching each page would work only if the site has few pages. For 1000 pages each loading in 1 second, this would take ~16 minutes of not so interesting work involving clicking the next button in the browser. Fetching the pages could be automated using a script, however the site owner might get unhappy and block the script if this generates a lot of work for the servers behind the site.
Furthermore, if the site has billions of pages, fetching every page becomes intractable. We could question the utility of so many pages, but let's just say that such a site exists, just to make the problem more challenging.
One thing we can immediately take advantage of is the estimation on the first page. We can compute a page based on that estimation and try to fetch it. If it exists and has fewer than N results, we found the last page by just fetching two pages. Lucky!
If it has N results (it's a "full page"), we can take the estimation on that page and repeat.
However, if the page does not exist, we have to try smaller pages until we find one that exists. This can be achieved using a binary search.
I was particularly impressed by the elegant solution, analysis and Python code submitted by Andrei Olariu. Great job!
Here is my solution, trying to combine binary search with being greedy when a full page is found. As the comments suggest, I am not sure this is the best we can do, but it's the best I could think of so far :)
Definitions
results(i) = number of results on the i-th page; 0 if the page does not exist
estimation(i) = estimated number of pages based on the estimation available on the i-th page; we assume estimation(i) >= i for any non-empty page
report_answer(a) = reports that the number of total results is a and terminates the program
Pseudo-code
l = 1, r = max(1, estimation(1)), p = r
ans = 0, min_inexistent_page = infinity
while (l <= r) {
nr = results(p)
if (nr == 0) {
min_inexistent_page = p
r = p - 1
p = l + (r - l) / 2
} else if (nr == N) {
ans = p*N
l = p + 1
e = min(min_inexistent_page - 1, estimation(p))
// Make sure we make at least one more iteration,
// since we are not sure yet if l-th page exists or not
r = max(l, e)
// We also ask for r-th page and not the middle, which might work better
// as the estimations get better. However, this was not analyzed in detail
// and there might be cases when it will perform worse.
p = r
} else {
// p must be the last page since it has between [1, N-1] results.
report_answer(nr + (p-1)*N)
}
}
// This covers the case when the last page is full.
report_anser(ans)
I hope you liked this quiz! Let me know if you want to see more like this via comments or reactions on social media sites.
