Topcoder SRM 798 DIV 2 — Problem 500

Md Shadekur Rahman
4 min readJan 24, 2021

Full problem description is here:

Problem description:

[(copied description here so you don’t have to switch tab). Following description, my solution approach to this problem is presented.]

Three logicians walk into a bar. The bartender asks them: “Do all of you want a beer?”

The first logician answers “I don’t know.”

The second logician answers “I don’t know.”

The third logician answers “Yes.”

The bartender brings them three beers.

If you don’t understand what’s going on, here’s an explanation of the joke:

In the joke, all three logicians clearly do want a beer, but they are also logicians. The first two logicians have to give the logically correct answer “I don’t know”, because the question asked whether everyone wants a beer and these logicians are not sure yet whether that’s true. Only the third logician, after hearing the first two logicians, correctly deduces that everyone really wants a beer.

This problem is a generalized version of the above joke.

There are N perfectly logical logicians. Each logician either wants a beer or doesn’t want a beer. Each logician only knows their own preference, they have no idea whether their friends want a beer.

The bartender asks them the same question as above: “Do all of you want a beer?” The logicians answer, one after another. Each logician considers their own preference and everything they heard before when formulating their statement. Each statement is one of “Yes”, “No”, and “I don’t know”.

You are given the statements made by the logicians: a String responses with N characters. The character ‘+’ represents the answer “Yes”, ‘-’ represents “No”, and ‘?’ represents “I don’t know”.

First, determine whether responses represents a valid set of responses that could have been given by N logicians with some preferences. If it is not valid, return -1.

If responses represents a valid set of responses, imagine that you are the bartender. After hearing all the responses, you can make the conclusion that at least A and at most B of the logicians want a beer. Find and return the value of A.