10826 - Hot or Cold?

[mf]

Yes, it is a DP problem. It's very similar to #882 "The Mailbox Manufacturers Problem."
You want some hint?

[Observer]

Hi,

I actually have solved #882 (and find it quite easy), yet I still don't get this question... Can anyone explain how the guessing works with some small N (e.g. N=2, 3 or 4)? Thanks~

(Wanna know why we need more than N guesses for N=2, 3 or 4...)

[sohel]

Yes, it is a DP problem. It's very similar to #882 "The Mailbox Manufacturers Problem."

Yes, I did figure out that it is very similar to #882, but don't know the method of either of them.

You want some hint?

Sure, but it would be better if you can give some documentations that explains the method from scratch.

I am asking for too much.. but I feel that this topic is very important and I must learn this.

Thanks.

[mf]

Well, I don't know any papers about this problem. I can describe the idea of my solution.

Initially we know, that the answer, r, is: 1 <= r <= N.

If N = 1, than obviously, r = 1, and we'll need just one guess.
If N >= 2, we'll need at least two guesses.

The first guess (call it `z') is arbitrary and doesn't give any new information.
Call the second guess `x'.

If we get the response "colder," than |x - r| >= |z - r|.

Solve this inequality for r:
Case 1: x - r >= 0, z - r >= 0, implies: r <= z <= x
Case 2: x - r <= 0, z - r >= 0, implies: x <= r <= z, (x + z)/2 <= r
Case 3: x - r >= 0, z - r <= 0, implies: z <= r <= x, (x + z)/2 >= r
Case 4: x - r <= 0, z - r <= 0, implies: x <= z <= r

Now, from all these cases, you can give more accurate bounds on r.

If x > z:
the lower bound on r remains unchanged (i.e., 1 <= r).
the upper bound (from case #3): r <= floor((x + z)/2).

If x < z:
the lower bound (from case #2): ceil((x + z)/2) <= r.
the upper bound is unchanged (r <= N).

On the other hand, if we get "warmer," than |x - r| <= |z - r|.
Again, solve this inequality and get precise bounds on r.

Now you have two subproblems (for "colder" and for "warmer" cases),
each of which is just like the original problem, except that you have better
bounds on the value of `r', and you don't have to make another "first guess" -- you can use the last one you've made (i.e. the value of `x').

You can solve these subproblems recursively and obtain G1 and G2 -- the number of guesses needed to solve each of them.
So, in the worst case, you'll need max(G1,G2)+1 guesses to find the number.
Than just try every possible value of `x' and choose the minimum necessary number of guesses. That will be the answer.

Memoization and a few other tricks will cut down the running time.

[mf]

Wanna know why we need more than N guesses for N=2, 3 or 4...

The problem requires that the last guess you make is the answer.

In the case N=2, at most 3 guesses are required. One solution is:
The first two guesses are 1, 2.
If you get "colder," the third guess (and the answer) is 1.
If it's "warmer," the answer is 2.

In the case N=3, at most 4 guesses are required.
The first two: 1, 2.
If the response is "colder," the third guess and the answer is 1.
Otherwise make the third guess: 3.
If it's "warmer," the answer is 3.
Otherwise the fourth guess and the answer is 2.

[Abednego]

Note that you don't stop guessing when you know the answer. You stop guessing when you know that your LAST GUESS was correct. This is why in the case n=2 the answer is 3. Here is how it works.

You guess 1 -> no reply.
You guess 2 -> colder.
You now know that the answer is 1, but you have to guess 1 again.
You guess 1 -> hotter.
Now you say that your last guess was correct.
The answer is 3 guesses.

Also to galkovsk:
I know why your program is wrong. I had the same mistake. Sometimes, you need to make a guess that gives you no new information. I mean that sometimes, you need to make a guess when you already know that the answer will be "hotter".

[Observer]

Thank you all!! Now I understand how the guessing process works.

[sohel]

Solved 882 !!
I just optimized A[101][101][11]..
Where A[a][c] is the result for range a to b using c boxes.

But facing problems with 10826 - hot or cold !
I am trying to optimize A[301][301][301];
where A[a][c] is the result for the range a to b using c as the last guess.
It takes a long time for inputs more than 150..

Can this be solved using 2 dimensional sample space ?

[Cho]

Yes.
Your A[a][c] will always be eqaul to A[0][b-a][c-a]. Thus you can reduce one dimension.

[sohel]

Thanks for the idea.

so A[10][20][15] --> meaning in the range 10 - 20 and having 15 as the last guess..

is same as

A[1][11][6].

Sometimes the (c - a) becomes negative.
What do we do then?

is A[1][10][-1] same as A[1][10][12]..

I get all the samples right except for the input 18.
For 18, my code outputs 8, but it should be 7.

Can someone depict why the result of 18 is 7 and not 8.

Thanks.

[mf]

I once was having troubles with this problem because I forgot to take into account previously known bounds.

If you know that the answer is in [a1,b1], and after your next guess the answer will be in [a2,b2], you should take the _intersection_ of these two intervals to be the new bounds on the answer.

is A[1][10][-1] same as A[1][10][12]..

yes

[Observer]

Ha, so after two years I look at this problem description again and solve it within 20 minutes!

Your A[a][c] will always be equal to A[0][b-a][c-a]. Thus you can reduce one dimension.

This is the key to the problem. With this in mind one can come up with a very short solution easily.