Connection Status:
Competition Arena > ConundrumReloaded

ConundrumReloaded

SRM 625 · 2013-12-22 · by vexorian

SRM 625 · 2013-12-22 · by vexorian · Simple Search, Iteration, Simulation
Class Name: ConundrumReloaded
Return Type: int
Method Name: minimumLiars
Arg Types: (string)
Problem Statement

Problem Statement

Once upon a time, N people sat around a circle. They were numbered 0 through N-1 in counter-clockwise order. Each person was either a honest person or a liar. A honest person always tells the truth, a liar always lies. You asked some of them (possibly all or none) whether the person sitting to the right of them is a liar. You are given their answers in a String answers with N characters. For each i, character i of answers is one of the following:
  • 'L' if person i said that person (i+1) is a liar,
  • 'H' if person i said that person (i+1) is a honest person,
  • '?' if you didn't ask person i.
(Above, (i+1) is considered modulo N. That is, person N-1 is talking about person 0.)

You are given the String answers. If there is at least one possible combination of honest people and liars that is consistent with answers, return the smallest possible number of liars. Else return -1.

Constraints

  • answers will contain between 2 and 50 characters, inclusive.
  • Each character in answers will be 'L', 'H' or '?'.
Examples
0)
"LLH"
Returns: 1

According to the input: Person 0 says that person 1 is a liar. Person 1 says that person 2 is a liar. Person 2 says that person 0 is a honest person. Clearly, they cannot all be honest, so there is at least one liar. It is possible that person 1 is liar and the other two are honest. Hence, the smallest possible number of liars is one. (Note that it is also possible that person 1 is honest and the other two are liars.)

1)
"?????"
Returns: 0

Nobody told us anything. It is possible that everybody is honest.

2)
"LHLH?"
Returns: 2

If person #1 and person #2 are liars, then the answers would be "LHLHH". This is consistent with the answers we received.

3)
"??LLLLLL??"
Returns: 3
4)
"LLL"
Returns: -1

Each of the 8 possible combinations of (liar / honest person) will lead to a contradiction.

7)
"?HL"
Returns: 1

A case in which changing "?" to "H" is not a good result.

Submissions are judged against all 296 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ConundrumReloaded with a public method int minimumLiars(string answers) · 296 test cases · 2 s / 256 MB per case

Submitting as anonymous