11902 - Dominator

All about problems in Volume 119. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

tanmoy
New poster
Posts: 18
Joined: Wed Jun 25, 2008 2:25 pm

11902 - Dominator

Post by tanmoy » Mon Jan 10, 2011 1:39 pm

Thanks i get it now.....AC
Last edited by tanmoy on Tue Jan 11, 2011 10:32 am, edited 1 time in total.

MRH
Learning poster
Posts: 51
Joined: Mon Aug 11, 2008 9:09 pm

Re: 11902

Post by MRH » Mon Jan 10, 2011 2:27 pm

try this case
1
4
1 1 0 1
1 0 1 1
1 1 1 1
1 1 0 1
acc output
Case 1:
+-------+
|Y|Y|Y|Y|
+-------+
|N|Y|Y|N|
+-------+
|N|N|Y|N|
+-------+
|N|N|N|Y|
+-------+

suneast
New poster
Posts: 49
Joined: Sun Jan 17, 2010 6:25 am
Location: FZU
Contact:

Re: 11902

Post by suneast » Tue Jan 11, 2011 5:33 am

Hi, MRH :wink:

My code have passed your data post above, but I still keep getting WA... and don't know why

My algorithm is quite simple:
delete NODE_U from the graph
if I can't visit NODE_V from 0, then NODE_U is Dominator of NODE_V

and here's my main algorithm code

Code: Select all

deleted... after got ac...
thx for your attention ; ) :wink:
Last edited by suneast on Tue Jan 11, 2011 5:40 am, edited 1 time in total.

suneast
New poster
Posts: 49
Joined: Sun Jan 17, 2010 6:25 am
Location: FZU
Contact:

Re: 11902 - dominator

Post by suneast » Tue Jan 11, 2011 5:39 am

Finally got Ac :wink:

the graph can be disconnected actually :)

happy coding.... :D

Rashad
New poster
Posts: 17
Joined: Tue Dec 22, 2009 4:20 pm

Re: 11902 - dominator

Post by Rashad » Tue Jan 11, 2011 6:46 pm

I am getting WA. :( Can anyone give me some i/o?? Thanks in advance. :)

tanmoy
New poster
Posts: 18
Joined: Wed Jun 25, 2008 2:25 pm

Re: 11902 - dominator

Post by tanmoy » Tue Jan 11, 2011 9:20 pm

Code: Select all

4
5
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1
0 0 0 0 0
1 1 0 0 1
Case 1:
+---------+
|Y|Y|N|N|Y|
+---------+
|N|Y|N|N|N|
+---------+
|N|N|N|N|N|
+---------+
|N|N|N|N|N|
+---------+
|N|Y|N|N|Y|
+---------+
10
1 0 0 0 0 1 0 1 0 1
1 0 0 1 0 0 1 1 0 1
0 0 0 1 1 1 1 0 1 0
0 0 0 1 0 0 0 0 1 0
0 1 1 1 1 1 0 1 1 0
0 0 1 0 1 1 1 1 1 0
0 0 1 1 1 0 1 1 1 0
0 1 1 1 0 0 0 1 0 0
1 1 1 1 1 1 0 1 0 1
1 1 1 1 0 1 1 1 1 1
Case 2:
+-------------------+
|Y|Y|Y|Y|Y|Y|Y|Y|Y|Y|
+-------------------+
|N|Y|N|N|N|N|N|N|N|N|
+-------------------+
|N|N|Y|N|N|N|N|N|N|N|
+-------------------+
|N|N|N|Y|N|N|N|N|N|N|
+-------------------+
|N|N|N|N|Y|N|N|N|N|N|
+-------------------+
|N|N|N|N|N|Y|N|N|N|N|
+-------------------+
|N|N|N|N|N|N|Y|N|N|N|
+-------------------+
|N|N|N|N|N|N|N|Y|N|N|
+-------------------+
|N|N|N|N|N|N|N|N|Y|N|
+-------------------+
|N|N|N|N|N|N|N|N|N|Y|
+-------------------+
10
0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 0 1 0 0 0
1 1 1 1 0 1 0 0 0 1
1 1 1 1 1 0 1 1 1 0
1 1 1 0 1 1 1 1 0 0
1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1
0 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 0 1 1 1
1 0 1 0 1 1 0 1 1 1
Case 3:
+-------------------+
|Y|N|N|N|N|N|N|N|N|N|
+-------------------+
|N|N|N|N|N|N|N|N|N|N|
+-------------------+
|N|N|N|N|N|N|N|N|N|N|
+-------------------+
|N|N|N|N|N|N|N|N|N|N|
+-------------------+
|N|N|N|N|N|N|N|N|N|N|
+-------------------+
|N|N|N|N|N|N|N|N|N|N|
+-------------------+
|N|N|N|N|N|N|N|N|N|N|
+-------------------+
|N|N|N|N|N|N|N|N|N|N|
+-------------------+
|N|N|N|N|N|N|N|N|N|N|
+-------------------+
|N|N|N|N|N|N|N|N|N|N|
+-------------------+
10
1 0 0 0 0 0 0 0 0 1
1 1 1 1 1 0 1 1 0 1
1 1 1 1 0 1 0 0 0 1
1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 0 0
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
Case 4:
+-------------------+
|Y|Y|Y|Y|Y|Y|Y|Y|Y|Y|
+-------------------+
|N|Y|N|N|N|N|N|N|N|N|
+-------------------+
|N|N|Y|N|N|N|N|N|N|N|
+-------------------+
|N|N|N|Y|N|N|N|N|N|N|
+-------------------+
|N|N|N|N|Y|N|N|N|N|N|
+-------------------+
|N|N|N|N|N|Y|N|N|N|N|
+-------------------+
|N|N|N|N|N|N|Y|N|N|N|
+-------------------+
|N|N|N|N|N|N|N|Y|N|N|
+-------------------+
|N|N|N|N|N|N|N|N|Y|N|
+-------------------+
|N|Y|Y|Y|Y|Y|Y|Y|Y|Y|
+-------------------+
try those cases....

crip121
New poster
Posts: 29
Joined: Tue Jul 08, 2008 9:04 pm

Re: 11902 - dominator

Post by crip121 » Tue Jan 11, 2011 11:29 pm

@tanmoy, i think all of the graph in your i/o is not DAG. but strangly, in problem statement, 2nd graph contains a self loop. although i treated given graph as a DAG and got AC.

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 11902 - dominator

Post by Shafaet_du » Thu Jan 13, 2011 2:50 pm

The Graph can be disconnected. Thats the trap that caused wa for many teams during contest.

Mehadi
New poster
Posts: 18
Joined: Sun Jan 24, 2010 11:17 am

Re: 11902 - dominator

Post by Mehadi » Sun Jan 23, 2011 7:50 am

WA
My code passed all input given in this thread.But still WA.Can anyone plz help me.It also works for disconnected graph

Code: Select all

Removed after Acc
Last edited by Mehadi on Sun Aug 07, 2011 8:51 am, edited 1 time in total.

pfiesteria
New poster
Posts: 9
Joined: Mon Aug 13, 2007 7:45 am

Re: 11902 - dominator

Post by pfiesteria » Sun Jan 30, 2011 1:55 pm

Thanks to Mehadi, your WA code active me write AC code.
But I still don't know what bugs in your WA code.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11902 - dominator

Post by brianfry713 » Mon Mar 04, 2013 10:58 pm

Input:

Code: Select all

1
12
1 1 1 0 0 1 1 1 1 0 0 0
0 0 1 0 1 0 0 1 1 1 0 1
0 0 1 1 0 1 1 0 0 1 0 0
0 1 1 0 1 0 0 0 0 1 0 1
1 0 0 1 1 0 0 0 0 1 1 1
1 1 1 1 0 1 0 0 0 1 0 0
1 1 0 1 0 0 0 0 1 1 1 0
1 1 0 0 0 0 1 1 1 0 1 1
1 1 1 1 0 0 1 0 1 1 1 1
0 0 1 1 1 0 1 0 1 0 0 0
0 1 1 1 1 0 0 0 1 1 0 0
1 1 0 0 1 1 0 1 1 1 0 0
AC output:

Code: Select all

Case 1:
+-----------------------+
|Y|Y|Y|Y|Y|Y|Y|Y|Y|Y|Y|Y|
+-----------------------+
|N|Y|N|N|N|N|N|N|N|N|N|N|
+-----------------------+
|N|N|Y|N|N|N|N|N|N|N|N|N|
+-----------------------+
|N|N|N|Y|N|N|N|N|N|N|N|N|
+-----------------------+
|N|N|N|N|Y|N|N|N|N|N|N|N|
+-----------------------+
|N|N|N|N|N|Y|N|N|N|N|N|N|
+-----------------------+
|N|N|N|N|N|N|Y|N|N|N|N|N|
+-----------------------+
|N|N|N|N|N|N|N|Y|N|N|N|N|
+-----------------------+
|N|N|N|N|N|N|N|N|Y|N|N|N|
+-----------------------+
|N|N|N|N|N|N|N|N|N|Y|N|N|
+-----------------------+
|N|N|N|N|N|N|N|N|N|N|Y|N|
+-----------------------+
|N|N|N|N|N|N|N|N|N|N|N|Y|
+-----------------------+
Check input and AC output for thousands of problems on uDebug!

raj
Learning poster
Posts: 78
Joined: Fri Feb 15, 2013 5:39 pm

Time limit exceed: 11902 - dominator

Post by raj » Sat Oct 19, 2013 9:23 pm

Code: Select all

Accepted
Last edited by raj on Sun Jun 22, 2014 11:20 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11902 - dominator

Post by brianfry713 » Mon Oct 21, 2013 9:50 pm

I solved it running DFS N + 1 times, you're running DFS N * N - 1 times.
Check input and AC output for thousands of problems on uDebug!

raj
Learning poster
Posts: 78
Joined: Fri Feb 15, 2013 5:39 pm

Question: 11902 - dominator

Post by raj » Mon Jun 09, 2014 7:33 pm

I have a question here
if the 0th node is the start node then if the graph is disconnected then is it will be all the connected components of the graph 1st random node is the start node?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11902 - dominator

Post by brianfry713 » Thu Jun 12, 2014 9:32 pm

I can't understand your question.
In graph theory, a node X dominates a node Y if every path from the predefined start node to Y must go through X. If Y is not reachable from the start node then node Y does not have any dominator. By definition, every node reachable from the start node dominates itself. In this problem, you will be given a directed graph and you have to find the dominators of every node where the 0th node is the start node.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 119 (11900-11999)”