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

×

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

harshraj22's gravatar image

3★harshraj22
12
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.

link

answered 11 Jan, 11:47

mynk322's gravatar image

4★mynk322
11
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)$

link

answered 11 Jan, 15:12

ay2306's gravatar image

3★ay2306
2029
accept rate: 11%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×342
×100
×15

question asked: 11 Jan, 07:02

question was seen: 115 times

last updated: 11 Jan, 15:12