×

GARGOYLE problem

 0 1 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 1●2 accept rate: 0%

 0 During contest the solution randomly strucked my mind and I got an AC. What I did was first making a vector > 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 4★mynk322 1●1 accept rate: 0% 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)
 0 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 3★ay2306 202●9 accept rate: 11%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×342
×100
×15