10826 - Hot or Cold?

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Yes, it is a DP problem. It's very similar to #882 "The Mailbox Manufacturers Problem."
You want some hint?

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
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...)
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

yes..

mf wrote: 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.
mf also wrote: 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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Observer wrote: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
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
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".
If only I had as much free time as I did in college...

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Thank you all!! Now I understand how the guessing process works.  7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

takes too much time..

Solved 882 !!
I just optimized A..
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;
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
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
Yes.
Your A[a][c] will always be eqaul to A[b-a][c-a]. Thus you can reduce one dimension.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
Thanks for the idea.

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

is same as

A.

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

is A[-1] same as A..

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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.
sohel wrote:is A[-1] same as A..
yes

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Ha, so after two years I look at this problem description again and solve it within 20 minutes! Cho wrote:Your A[a][c] will always be equal to A[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. 7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org