10826  Hot or Cold?
Moderator: Board moderators
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...)
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
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
yes..
Yes, I did figure out that it is very similar to #882, but don't know the method of either of them.mf wrote: Yes, it is a DP problem. It's very similar to #882 "The Mailbox Manufacturers Problem."
Sure, but it would be better if you can give some documentations that explains the method from scratch.mf also wrote: You want some hint?
I am asking for too much.. but I feel that this topic is very important and I must learn this.
Thanks.
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.
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.
The problem requires that the last guess you make is the answer.Observer wrote:Wanna know why we need more than N guesses for N=2, 3 or 4...
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.

 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".
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...
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
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
takes too much time..
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 ?
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 ?
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.
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.
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.
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.
yessohel wrote:is A[1][10][1] same as A[1][10][12]..
Ha, so after two years I look at this problem description again and solve it within 20 minutes!
This is the key to the problem. With this in mind one can come up with a very short solution easily.
Cho wrote:Your A[a][c] will always be equal to A[0][ba][ca]. 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
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org