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

×

FIRESC - Editorial

16
2

PROBLEM LINKS

Practice
Contest

DIFFICULTY

SIMPLE

PREREQUISITES

Graph Theory, Union Find, Depth First Search

PROBLEM

An Office has several people on which a relationship of being mutual friends is defined. Two people who are friends will always choose to accompany each other while escaping from fire.

Under these conditions, what are the maximum number of escape routes may be built such that none of them may be empty.

Also, each set of people who escape together, must have a captain assigned. Count the number of ways of assigning captains.

QUICK EXPLANATION

Let us define a graph whose vertices are people. An undirected edge connects two people who are friends.

On this graph, two vertices will be of the same color if they share an edge. This represents that the two people should have to go in the same fire escape route. We wish to maximize the number of colors used.

All the vertices in a connected component in this graph will have to be in the same color.

The above is easy to see because

  • If A and B are friends
  • and B and C are friends
  • Given that A and B should be the same color
  • and B and C should be the same color
  • A, B and C, all three should be the same color

This observation leads us to the following

The maximum number of fire escape routes that may be built is equal to the number of connected components.

The second part of the problem - Finding the ways to assign captains - is equal to the product of the number of vertices in each connected component. This can be derived by simple permutation / combination. (Since we need exactly 1 member from each set, the answer must be the product of the cardinality of the sets).

EXPLANATION

The number of connected components can be found by use of either of the following techniques

Depth First Search

Since this is an undirected graph, the number of times a Depth First Search starts from an unvisited vertex is equal to the number of connected components. We would like to store the graph as an adjacency list due to the large number of vertices (the number of edges are not too many).

Lets look at dfs implementation in pseudo-code. Both the Setter's and Tester's coe use DFS to solve the problem.

for u = 1 to N
    if u is not visited
        connected_components++
        dfs(u)

dfs(u)
    mark_visited(u)
    for all children v, of u
        if v is not visited
            dfs(v)

Union Find

Union Find or Disjoint Set Data structures allow you to merge two sets of items together dynamically and maintain for each item - to which set does it belongs. You can consume a Union Find data structure to join each pair of friends. At the end of this, just count the number of distinct components to get the answer.

for u = 1 to N
    initialize-new-set-with-1-item(u)

for e = 1 to M /* all edges */
    join-sets( e.first, e.second )

Let cc = Array of size N
for u = 1 to N
    cc[ find-set-root(u) ]++

for u = 1 to N
    if cc[u] > 0
        connected_components++

There is one detail missing from the above two approaches. Handling of part 2 of the question. We wish to find the number of items in each connected component and find the product of these numbers.

  • In the dfs approach, maintaining a global "size" and incrementing it can solve the problem
    • or return the counts in the return value of dfs
  • In the disjoint set approach, as demonstrated in the pseudo-code, the array cc stores the number of items in each connected component at the end

SETTER'S SOLUTION

Can be found here.

TESTER'S SOLUTION

Can be found here.

This question is marked "community wiki".

asked 12 Mar '13, 06:04

gamabunta's gravatar image

1★gamabunta
2.4k128183169
accept rate: 14%

I used weighted quick union for this, which can be improved further using path compression. My solution : http://www.codechef.com/viewplaintext/1869801

(13 Mar '13, 09:38) xonix_monty2★

http://www.codechef.com/viewsolution/1939836 getting wrong ans..really pissed off :( please find the error...thanx in advance...

(15 Mar '13, 21:27) notaloser2★

I m getting SIGSEGV but i dont know why i am getting this... intializing like this mark=vector<int>(n,0) i am getting correct answer.. but when i try to do vector<int> mart(n,0) i am getting SIGSEGV.. what is wrong with this...plz answer me.. http://www.codechef.com/viewsolution/4372844

(24 Jul '14, 14:47) vishnu018233★

1234next »

Please help . Getting Wrong answers for even test case!!! link to my code -> http://ideone.com/lU40Sl

link

answered 19 May '13, 18:53

al3x1784's gravatar image

2★al3x1784
041416
accept rate: 0%

i have used same approach as gven in editorial but it is giving me wrong answer.anyone explain me....where i am wrong first in C is C SOLUTION http://www.codechef.com/viewsolution/1910690 and second is in JAVA is JAVA SOLUTION http://www.codechef.com/viewsolution/1907414

link

answered 13 Mar '13, 20:23

tarnado111's gravatar image

2★tarnado111
012
accept rate: 0%

They both have the same mistake. You do not handle possible overflow in this statement

total = ((total % N)*(count % N) % N;

As you can see, because N is 1000000007, the result of the product might exceed the range of 32-bit integers. You must cast total as long long in C to solve the issue. Cast total to long in JAVA to get AC.

(15 Mar '13, 19:23) gamabunta1★

Yes right... after changing the logic to total = ((total % N)*(count % N) % N;.. my code also worded.. huh.. http://www.codechef.com/viewsolution/1927944

(16 Mar '13, 00:54) ashishcheema3★

such a nice problem, thank you codechef.

link

answered 25 Sep '17, 23:39

kishynivas_13's gravatar image

2★kishynivas_13
123
accept rate: 0%

If you're having a problem with StackOverflow on Java, use BFS instead of DFS. I had a problem with DFS and my switch over fixed it.

link

answered 12 Mar '13, 08:32

kullalok's gravatar image

2★kullalok
1.5k112236
accept rate: 14%

Once i did the set-union of all given edges, i did a find-set (with path-compression) on all vertices. Now, the number of distinct set representatives gives the number of connected components. We can also get the cardinality of each set from this information. http://www.codechef.com/viewsolution/1871116

link

answered 12 Mar '13, 12:36

tijoforyou's gravatar image

2★tijoforyou
4.2k52364
accept rate: 15%

Used exactly same solution in my submission as of union find , still got wrong answer

Can anyone tell where is the mistake?? Link to solution

http://www.codechef.com/viewsolution/1905165

link

answered 12 Mar '13, 13:26

sahil90's gravatar image

2★sahil90
1
accept rate: 0%

1

Replace c[p[i]]++ by c[find(i)]++
p[i] is not always the actual root of the disjoint set containing i.
Namely, after link operation.

(12 Mar '13, 16:30) anton_lunyov ♦6★

@ anton : Thanks a lot..

(13 Mar '13, 14:31) sahil902★

@gamabunta @tijoforyou Are you sure implementing with DFS would pass all test cases without TLE. Initially I did it with DFS but was getting TLE. Then I did it with disjoint sets. Yet again I got a TLE with a simple implementation of union. But when I changed my implementation to Union by Rank, I got an AC with a runtime of 1.02 sec. http://www.codechef.com/viewsolution/1894308

link

answered 12 Mar '13, 13:35

rahulp0491's gravatar image

3★rahulp0491
1
accept rate: 0%

Running DFS is getting TLE. Why? Check my submissions: http://www.codechef.com/viewplaintext/1881613

link

answered 12 Mar '13, 15:16

bugkiller's gravatar image

3★bugkiller
8.6k194898
accept rate: 9%

You have loop for(int j=i; j<n; j++) after each call to dfs. In the case of no edges in the graph you will have O(N^2) solution. Obviously it should get TLE :)

(12 Mar '13, 16:18) anton_lunyov ♦6★

@anton_lunyov >> So, if I consider the case of graph consisting of no edges separately, will it run within TL?

(12 Mar '13, 16:29) bugkiller3★

No. The graph could have many components, say 90000, and you still will get TLE. Also why you are creating the array visited at each dfs run? This is the worst thing to do. It should be created only once and filled by false before global dfs loop

(12 Mar '13, 16:48) anton_lunyov ♦6★

and that is why my code was 270M :(

(12 Mar '13, 17:04) bugkiller3★

@anton_lunyov >> can you give some large test files, like you did for CHEFHACK?

(12 Mar '13, 17:06) bugkiller3★
showing 5 of 6 show all

Need help finding bug in my solution http://www.codechef.com/viewplaintext/1933093. Was getting WA :(

link

answered 12 Mar '13, 18:04

amit5148's gravatar image

1★amit5148
122
accept rate: 0%

Use ret = ((long long)ret * c) % 1000000007;

(12 Mar '13, 21:31) anton_lunyov ♦6★

I got accepted using BFS using queues....but the same code I tried to implement it with DFS using stacks it gave TLE...whereas the recursive version of DFS got AC.could you tell me the reason for the TLE...was my code going into infinite loop or just didn't achieve the desired time limit.

TLE CODE: http://www.codechef.com/viewplaintext/1901407

AC CODE: http://www.codechef.com/viewplaintext/1889867

Thanks in advance.

link

answered 12 Mar '13, 18:47

rahul_nexus's gravatar image

2★rahul_nexus
7741923
accept rate: 13%

edited 12 Mar '13, 18:50

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:

×14,850
×1,034
×664
×104
×22

question asked: 12 Mar '13, 06:04

question was seen: 12,179 times

last updated: 03 Feb, 21:56