Editorial for GARGOYLE - PELT2019

Difficulty: Easy

Problem setter: panik

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.

Author’s Solution: click here

Tester’s Solution: click here

@panik can you please tell me why my code is wrong ? I did exactly same what is mentioned in the editorial, and repeatedly got WA during the contest.

link

Can anyone help me why my submission is getting wrong answer? I am doing same thing as mentioned above. Link

@parth_patel15 You’ve added a link of the submission page. Add the link to the submitted solution.

Updated. My solution is same as yours. Don’t know why it gets WA.

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.

@panik @admin @vijju123 Kindly check, the tester’s solution is even getting a WA

LINK

Hi parth, your solution is wrong because you have set ans=1 but ans can be 0 as well

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

Sorry wrong tester solution file was attached, the file is updated, please have a look

@panik Can you please explain the output for the Sample Case 2 in a litle more detailed way? Still not able to get it.

@panik Let me know once you find the mistake :slight_smile:

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

@panik Did you find the mistake ?

@panik @admin @vijju123 anyone could you please bother to reply?

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?