You are not logged in. Please login at to post your questions!


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 .

asked 11 Jan, 07:02

harshraj22's gravatar image

accept rate: 0%

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.


answered 11 Jan, 11:47

mynk322's gravatar image

accept rate: 0%

edited 11 Jan, 11:48

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

(11 Jan, 13:09) harshraj223★

What I did was this:

maintain an array pos, where $pos[i] = 1$ if for every $j$ where $arr[i][j] = 'T'$ then $arr[j][i]$ 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)$


answered 11 Jan, 15:12

ay2306's gravatar image

accept rate: 11%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 11 Jan, 07:02

question was seen: 115 times

last updated: 11 Jan, 15:12