Page 1 of 2

753 plug for Unix

Posted: Thu Dec 11, 2003 5:46 pm
by titid_gede
hi,
can you tell me how to get 1 in sample input / output?
thanks before.

regards,
titid

Posted: Thu Jan 22, 2004 12:08 pm
by little joey

Code: Select all

[laptop|B> -- >B|X> -- >X|A> -- >A]
[pager |B> -------------------- >B]
[phone |C> -------------------- >C]
[comb  |X> -- >X|D> ----------- >D]
Which leaves the clock unplugged, so the answer is 1. But there are other optimal combinations.

Posted: Sat Jan 24, 2004 6:51 am
by titid_gede
thanks for your explanation.
another ask, what is the output for

Code: Select all

1

1
A
1
titid  B
1
A B
is the output 0 or 1?

thanks before.
-titid-

Posted: Sat Jan 24, 2004 10:17 am
by little joey
1 :)

Posted: Mon Jan 26, 2004 6:48 am
by titid_gede
thanks little joey. at first some statements confused me as i always got WA. but i found a little bug in my code. now i got AC. thank you very much :)

753 - A Plug for UNIX

Posted: Thu Mar 18, 2004 1:37 am
by ab
Hi,

Looks like a simple bipartite matching problem, but I always get a WA reply :cry: What I'm doing is:
- plugs and receptacles (verticies) together with adapters (edges) form a graph, so first I do a bsf of this graph for each device (of course, if two devices have got the same plug type I do only one bfs) and so I get for each device a list of receptacles it can be plugged in (directly or through a chain of adapters);
- devices together with lists of receptacles they can be plugged in form a bipartite graph, so I use Ford-Fulkerson method to find the max flow;
- number of devices minus max flow is the result.

I've tried different tests, but all of them passed. Can anyone suggest some interesting tests?

And another question. Is the following input vaild?

Code: Select all

2
A
B
3
laptop A
laptop B
phone A
0
So laptop has got two plugs. Are we garanted that each device appears only once in the list?

Thanks,

ab

Posted: Sun Mar 21, 2004 12:01 am
by ab
Argh! My algorithm is OK, but I've forgotten to initialize some variable in my program and that's why I was getting WA :lol: It took me two weeks to find that stupid mistake!!! :(

not specified

Posted: Sat Aug 21, 2004 2:35 pm
by Mahmud776
Sample input:
4

4
c
c
c
c
4
lap1 a
lap2 b
lap3 a
lap4 x
4
x c
b x
a b
y x

5
d
c
d
c
c
5
lap1 a
lap2 a
lap3 b
lap4 b
lap5 b
5
x c
b x
a b
y x
x d

3
p
q
r
3
lap1 p
lap2 p
lap3 p
2
p q
p r

3
c
c
c
3
lap1 a
lap2 b
lap3 b
3
a c
b a
a b

Sample Output:
0

0

0

0

Posted: Sat Aug 21, 2004 2:39 pm
by sohel
Mahmud wrote: Sample input:
4

4
c
c
c
c
4
lap1 a
lap2 b
lap3 a
lap4 x
4
x c
b x
a b
y x

5
d
c
d
c
c
5
lap1 a
lap2 a
lap3 b
lap4 b
lap5 b
5
x c
b x
a b
y x
x d

3
p
q
r
3
lap1 p
lap2 p
lap3 p
2
p q
p r

3
c
c
c
3
lap1 a
lap2 b
lap3 b
3
a c
b a
a b

Sample Output:
0

0

0

0
Ahhh... Are you getting WA or are you giving free sample i/o to those who are getting WA. :roll:

753 - A plug for UNIX

Posted: Tue Feb 22, 2005 1:09 am
by greco
I can't find out what's wrong... Let's say we have a total of nrrec plugs or receptacles. While reading the input data I always check if the plug has been read before. If not, I increase nrrec and add it. For each of the m devices I have ptr - the number of the plug / receptacle of the i'th device.

Then I build a matrix mat[j] (i, j = 1..nrrec), mat[j] = 1 means that that the device i can be plugged in the j receptacle. First, mat[j] = 1 if i = j, or 0 otherwise. Then, considering the k pair of adapters, if x and y are a pair of numbers, mat[x][y] = 1.
Using this information I do nrrec df searches to find out the final mat[j].

After that there's a bipartite graph with 0 - the source, 1..m - the devices, m+1..m+n - the receptacles, and n+m+1 - the destination. The capacity of (s, x) is 1 for x = 1..m, the capacity of (x, d) is 1 for x = m+1.. n+m. The capacity of (x, y) is 1 if mat[ptr][j] = 1 (we can plug the i'th device in the j'th receptacle).

The answer is m - the maximum flow in this graph. Can anybody tell where my mistake is? :-?

Posted: Tue Feb 22, 2005 3:31 pm
by shamim
Your Algorithm looks basically correct as it is indeed a MAX flow problem.

But here is how I considered it.

suppose there is one source, some adapters , some device, and one sink.
The capacity from source to adapters is infinite( if the shop has supply ), the capacity of adapters to adapters is also infinite, and the capacity of adapters to device is one and capactiy of device to sink is also one.

Well, I know my explanation is vague, but try to make something out of it.

Posted: Wed Feb 23, 2005 12:18 am
by greco
My solution seems easier.. I have only n+m+2 vertices, and the i'th device is connected to the j'th plug with a 1-capacity edge only if we can connect the two, using any kind of adapter.

This should be right too... but it keeps wa-ing. :(

Posted: Sun May 01, 2005 12:47 am
by Abednego
This input is invalid. There is at most 1 of each type of socket. I checked this with an assert().

753 - A plug for UNIX

Posted: Thu May 05, 2005 11:37 am
by frk_styc
I use the highest-label preflow-push algorithm for max flow. To find the node with the "highest-label" I use a heap (push_heap & pop_push from STL with a Less functor for key comparison). My submissions all end up with a runtime error (SIGSEGV). After checking many times I still can't find the code segment which may have caused that. Here is my code:

Code: Select all

Deleted by a lazy admin

Posted: Thu May 05, 2005 2:27 pm
by mf
There can be more than 300 plug names in the input - each of the 100 adapters may introduce up to two new plug names. Increase your MAX constant to something like a 500.

Also, your program does not print a blank line between test cases.