Chef and Remissness Problem Code: REMISS

general
1

In this problem, How Maximum number would be the minimum number of entrances into the hotel? please explain me.
problem link:
REMISS Problem - CodeChef

Thanks in Advance.

2

I don’t know if you have read the editorial. That should be enough to see why this is the case. Still, I will write a (hopefully) easier to understand reason.

Since at least one guard is awake at all times, any time chef enters the hotel, it is noticed by some guard.

If the first guard reports that chef entered A times, then chef must have entered at least A times. There could be other times when the first guard was asleep, and chef entered.

Similarly, If the second guard reports that chef entered B times, then chef must have entered at least B times. There could be other times when the second guard was asleep, and chef entered.

So the minimum possible number of entrances is >= A and it is also >= B. The smallest number that satisfies these 2 is max(A,B). Can there be a situation when chef made exactly max(A,B) entrances? Answer is yes, if one guard notices all his entrances and the other was asleep for some ( possibly none ) of them.

1 Like
3

Thank you very much. I read the editorial but i thought like min(A,B) times the chef can enter into room.

I took 19 and 17 for example,
So the minimum possible number of entrances is >= A and it is also >= B. --> for example guard A(19) was asleep and guard B(17) notices all entrances then what would be the answer?? is it same 19 only? – I read in editorial like both guards never fall asleep at a time.
The smallest number that satisfies these 2 is 19 only as >=A and >=B… but please clarify me the above doubt.

Thank you very much once again.

4

It is just some normal reasoning. What I am saying here is that all values \{0,1,2 \ldots A-1\} cannot be the answer and all values \{0,1,2 \ldots B-1\} cannot be the answer.

Let’s assume A\ge B. Then, A is the smallest value that hasn’t been excluded.

If we can find a situation where chef entered exactly A times, then A is the minimum number of times chef entered. Otherwise, the minimum number of times chef entered has to be greater than A.

But, we can find a situation where A is the number of times chef entered. This happens when the first guard is awake for all of the times chef entered, and the second guard was asleep for A-B of them. (All of this is assuming A\ge B)

1 Like
5

Thanks a lot saini for your explanations and i got your answer as min possible is the max of A,B. but my doubt is

if A was asleep and B guard counts all the entrances of chef then what will be the answer?

for my doubt, i took the exam as guard A slept all the time(24 hours) then it must be 0 count and then we have to take Guard B count and which is higher. so we are taking higher value of A,B.

and other case as you mentioned, one of the guard might slept A-B or B-A of the entrances.

I got it now. thank you very much saini for your patience to clear my doubt.