753 - A Plug for UNIX

[titid_gede]

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

regards,
titid

[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.

[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-

[little joey]

1

[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

[ab]

Hi,

Looks like a simple bipartite matching problem, but I always get a WA reply 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]

Argh! My algorithm is OK, but I've forgotten to initialize some variable in my program and that's why I was getting WA It took me two weeks to find that stupid mistake!!!

[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

[sohel]

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.

[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?

[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.

[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.

[Abednego]

This input is invalid. There is at most 1 of each type of socket. I checked this with an assert().

[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

[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.