I don’t think it’s equivalent. The duck can move freely inside the circle, while the fox can only stay on the circumference. Anyway, try to solve the 2 and 3 case.
Imagine a rating system for movies where Bob the reviewer watches a movie and declares “this is in the top three movies I will see this year”. Then he watches another movie and says “this is in the top two movies I will see this year”. Then he watches another movie and says “this is in the top two movies I will see this year”. Then he watches another movie and says “this is in the top three movies I will see this year”. But with this last statement his credibility is gone, because he’s claimed that four movies will be in the top three or better. Thus we will say that the “longest credible prefix” of the list [3,2,2,3] is [3,2,2].
The puzzle is to write an algorithm that accepts a list of integers and returns the length of its longest credible prefix, whose asymptotic complexity is as good as possible. (I have found an answer that’s extremely fast, but no proof that it’s fastest.)
I can do time O(n^2), where n is the length of the list. Perhaps the “extremely fast” algorithm you have is O(n log n)? Surely O(n) must be impossible.
Just to check we are formalizing in the same way, do you agree that O(n) is a lower bound? Because the list [1,2,...,n] has longest credible prefix of length n, but if we reduce any of the first n-1 elements by 1 then the length of the longest credible prefix is reduced. So we at least have to spend O(n) time looking at the first n-1 elements.
“this is in the top three movies I will see this year”
He can’t say that. He doesn’t even know how many movies he is going to see.
If he knows, that he is going to watch another N movies this year, he can only say “this is in the top N+1 movies I will see this year”. If that was the best movie so far.
The problem statement should be taken on face value, not argued with. But if you’re interested in the motivation, I was trying to design a review system that wouldn’t suffer from score inflation and payola (“every decent movie is 4 stars out of 5”). The problem you see is in fact the whole point. If you don’t feel confident enough that a movie will be in your top 3, say that it will be in your top 10. Your lack of confidence is an important signal of your true beliefs about the movie and viewers deserve to know it :-)
I don’t think it’s equivalent. The duck can move freely inside the circle, while the fox can only stay on the circumference. Anyway, try to solve the 2 and 3 case.
I didn’t say it’s equivalent, just another puzzle. Took years before the solution came, decades ago.
But I don’t see much sense into digging for old solved or unsolved problems.
Invent one!
Here’s one I invented recently.
Imagine a rating system for movies where Bob the reviewer watches a movie and declares “this is in the top three movies I will see this year”. Then he watches another movie and says “this is in the top two movies I will see this year”. Then he watches another movie and says “this is in the top two movies I will see this year”. Then he watches another movie and says “this is in the top three movies I will see this year”. But with this last statement his credibility is gone, because he’s claimed that four movies will be in the top three or better. Thus we will say that the “longest credible prefix” of the list [3,2,2,3] is [3,2,2].
The puzzle is to write an algorithm that accepts a list of integers and returns the length of its longest credible prefix, whose asymptotic complexity is as good as possible. (I have found an answer that’s extremely fast, but no proof that it’s fastest.)
I can do time O(n^2), where n is the length of the list. Perhaps the “extremely fast” algorithm you have is O(n log n)? Surely O(n) must be impossible.
O(n log n) would be nice, but you can do even better :-)
Just to check we are formalizing in the same way, do you agree that O(n) is a lower bound? Because the list [1,2,...,n] has longest credible prefix of length n, but if we reduce any of the first n-1 elements by 1 then the length of the longest credible prefix is reduced. So we at least have to spend O(n) time looking at the first n-1 elements.
Yes, O(n) is a lower bound.
He can’t say that. He doesn’t even know how many movies he is going to see.
If he knows, that he is going to watch another N movies this year, he can only say “this is in the top N+1 movies I will see this year”. If that was the best movie so far.
The problem statement should be taken on face value, not argued with. But if you’re interested in the motivation, I was trying to design a review system that wouldn’t suffer from score inflation and payola (“every decent movie is 4 stars out of 5”). The problem you see is in fact the whole point. If you don’t feel confident enough that a movie will be in your top 3, say that it will be in your top 10. Your lack of confidence is an important signal of your true beliefs about the movie and viewers deserve to know it :-)
I’ll pass. Maybe somebody else will solve this problem of yours. Too vague for me.