Prerequisites: Implementations, usage of maps/dictionary(if in python).
Explanation:
I this question for statements to not contradict, all the statement arrays of the selected people should be similar. We can do this by taking the count of each distinct array with the help of maps and then Iterating all of them and finding the maximum count with the correct Statements.
Note: A statement array will only be considered correct if the count of True in it is equal to the count of that type of substring. This could be seen in sample Test case 2. Although the count of T T T was 2, the final answer was 1 because according to them all of them were true speaking by according to the 3rd person, he only considered himself to be a true speaking person.
Time complexity: O(nlog(n)) → log(n) factor occurs due to usage of maps.
Similar thing happened in Sept 2018 Lunchtime as well where the solution got WA during the contest but got AC in practice section. At that time as well, there was no reply from the admin or the author and the contest was kept as rated.
Hi arjit, I am looking into your solution although its giving the correct ans on codechef compiler on the TC on which your solution is showing wrong, i am looking into it. @vijju123 can you please have a look
see the first 2 people consider everyone to be a truth speaking person, but the 3rd person doesn’t think so, so we cannot cosider to T T T statement to be correct. No if we pick the F F T statement then according to him only the 3rd person is correct and this does not contradict with any statement as only 1 person is in set and the count of T in statement is 1 also, so ans is 1
I do not understand how is the time complexity of the suggested solution nlogn. I think that the time complexity of the solution is (n^2)logn. Can you please explain?
