753 - A Plug for UNIX

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

Moderator: Board moderators

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

753 plug for Unix

Post by titid_gede » Thu Dec 11, 2003 5:46 pm

hi,
can you tell me how to get 1 in sample input / output?
thanks before.

regards,
titid
Kalo mau kaya, buat apa sekolah?

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

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

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.

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede » Sat Jan 24, 2004 6:51 am

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-
Kalo mau kaya, buat apa sekolah?

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sat Jan 24, 2004 10:17 am

1 :)

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede » Mon Jan 26, 2004 6:48 am

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 :)
Kalo mau kaya, buat apa sekolah?

ab
New poster
Posts: 2
Joined: Thu Mar 18, 2004 12:59 am
Location: Grenoble, France
Contact:

753 - A Plug for UNIX

Post by ab » Thu Mar 18, 2004 1:37 am

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

ab
New poster
Posts: 2
Joined: Thu Mar 18, 2004 12:59 am
Location: Grenoble, France
Contact:

Post by ab » Sun Mar 21, 2004 12:01 am

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!!! :(

Mahmud776
New poster
Posts: 22
Joined: Mon Dec 22, 2003 9:29 am
Location: Canada

not specified

Post by Mahmud776 » Sat Aug 21, 2004 2:35 pm

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

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Sat Aug 21, 2004 2:39 pm

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:

greco
New poster
Posts: 6
Joined: Sat Jul 31, 2004 6:04 pm
Contact:

753 - A plug for UNIX

Post by greco » Tue Feb 22, 2005 1:09 am

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? :-?
Attitude is no substitute for competence.

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Tue Feb 22, 2005 3:31 pm

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.

greco
New poster
Posts: 6
Joined: Sat Jul 31, 2004 6:04 pm
Contact:

Post by greco » Wed Feb 23, 2005 12:18 am

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. :(
Attitude is no substitute for competence.

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Sun May 01, 2005 12:47 am

This input is invalid. There is at most 1 of each type of socket. I checked this with an assert().
If only I had as much free time as I did in college...

frk_styc
New poster
Posts: 10
Joined: Sun Apr 17, 2005 5:00 pm

753 - A plug for UNIX

Post by frk_styc » Thu May 05, 2005 11:37 am

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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Thu May 05, 2005 2:27 pm

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.

Post Reply

Return to “Volume 7 (700-799)”