GARGOYLE problem



Can Any one help me with my solution for
GARGOYLE problem
My Solution Accepted Solutions
essentially , I did the same thing that others have done , i.e. counting number of truths of true speaking people and equating it to their frequency , still getting wa. Any help will be appreciated .


During contest the solution randomly strucked my mind and I got an AC.
What I did was first making a vector<pair<int, string> > and counting the frequencies of every unique statement and storing in it as {frequency, statement}.
then sorting it according to frequency and then iterating from backwards.
Then for each statement i find the number of ‘T’ in it and compare it to it’s corresponding frequency.If it matches,I am printing the frequency.And if none ate true, print 0.


What I did was this:

maintain an array pos, where pos* = 1 if for every j where arr*[j] = 'T' then arr[j]* should be ‘T’ as well.

then in for every person, we check that if j that he is declaring true must be possible, in other words, must not contradict himself.

And count maximum truth speaking people this way.

Code for Reference: Link

Time Complexity: O(n^2)


Man , That’s what I did !! But My solution is getting WA. Moreover , its pathetic to see solutions having O(n³) getting accepted !!!