908 - Re-connecting Computer Sites

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

Moderator: Board moderators

calicratis19
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Location: SUST,SYLHET,BANGLADESH.
Contact:

908 - Re-connecting Computer Sites

Post by calicratis19 » Tue Aug 11, 2009 10:49 pm

i m surprised abt the problem. it is said that it will give n-1<=m<=n*n-1/2 ,here m is the number of edges and n is the numbner of node which can be 1 <= n <= 1000000. so clearly m edges cant be stored in an array. but surprisingly there is no input where m>n.a two dimensional array of array[1000020][3] is enough to store edges and cost.
:o :o :o
Heal The World

Jehad Uddin
Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

Re: 908-Re-connecting Computer Sites

Post by Jehad Uddin » Sun Oct 04, 2009 4:16 pm

In uva there are problems(such as 200,11042,935,(789,479 no test case :))) of poor test cases , and this problem is also that type, the problem descripton is wrong also,

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

Re: 908-Re-connecting Computer Sites

Post by Shafaet_du » Sun Nov 28, 2010 10:25 pm

Whats wrong with problem description? just add the costs of first N-1 inputs,and thats the first output. find MST of last K+M inputs,thats the 2nd output.

SyFyKid
New poster
Posts: 26
Joined: Tue May 08, 2012 9:47 am

Re: 908-Re-connecting Computer Sites

Post by SyFyKid » Sun Jun 10, 2012 5:22 pm

Nothing wrong, but we should remember that second line (aka MST of K+M edges) should be min(cost_before, cost_after).
Shafaet_du wrote:Whats wrong with problem description? just add the costs of first N-1 inputs,and thats the first output. find MST of last K+M inputs,thats the 2nd output.

VitezVojko
New poster
Posts: 7
Joined: Sun Apr 15, 2012 4:45 pm

Re: 908-Re-connecting Computer Sites

Post by VitezVojko » Sun Nov 04, 2012 2:55 pm

Code: Select all

AC, Blank lines were the problem :S
I simply don't know, what am i doing wrong here, can someone please help me, or give me tricky I/O?

c1337
New poster
Posts: 3
Joined: Wed Oct 23, 2013 8:03 pm

Re: 908-Re-connecting Computer Sites

Post by c1337 » Wed Oct 23, 2013 8:07 pm

Can this question be done without using a priority queue and just using a disjoint-set data structure ?

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

Re: 908-Re-connecting Computer Sites

Post by brianfry713 » Wed Oct 23, 2013 8:55 pm

Check input and AC output for thousands of problems on uDebug!

c1337
New poster
Posts: 3
Joined: Wed Oct 23, 2013 8:03 pm

Re: 908-Re-connecting Computer Sites

Post by c1337 » Thu Oct 24, 2013 8:33 am

When I add a edge to already formed MST it creates exactly 1 cycle. Traversing that cycle I need to find the maximum weight edge and delete it. But that means I need to implement a union-find-delete instead of just union-find. Is that correct or am I missing something ?

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

Re: 908-Re-connecting Computer Sites

Post by brianfry713 » Thu Oct 24, 2013 8:55 pm

In Kruskal's algorithm, you only add edges that don't create a cycle.
Check input and AC output for thousands of problems on uDebug!

c1337
New poster
Posts: 3
Joined: Wed Oct 23, 2013 8:03 pm

Re: 908-Re-connecting Computer Sites

Post by c1337 » Fri Oct 25, 2013 12:19 am

What I meant was can this question be done by using the previously given MST and modifying it according to the new edges given to us ?That we don't use the information about all the edges

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

Re: 908-Re-connecting Computer Sites

Post by brianfry713 » Fri Oct 25, 2013 8:02 pm

Here's how I solved it:

On this part of the input: "The set T of previously chosen high-speed lines, consisting of N-1 lines, each describing a high-speed line, and containing the numbers of the two computer sites the line connects and the monthly cost of using this line. All costs are integers." ignore the graph, just sum the costs and print that on the first line of the testcase.

Next run Kruskal's algorithm from scratch on the graph containing the M + K edges, these two parts of the input combined: "K lines, each describing a new high-speed line, and containing the numbers of the two computer sites the line connects and the monthly cost of using this line. All costs are integers." and "M lines, each describing one of the originally available high-speed lines, and containing the numbers of the two computer sites the line connects and the monthly cost of using this line. All costs are integers." Report the result on the second line of the testcase.
Check input and AC output for thousands of problems on uDebug!

chanderg_12
New poster
Posts: 5
Joined: Fri Nov 15, 2013 2:06 pm

Re: 908-Re-connecting Computer Sites

Post by chanderg_12 » Fri Nov 15, 2013 2:11 pm

Can't we add the new edges to the old MST by removing cycles as they appear?Will this greedy approach work?

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

Re: 908-Re-connecting Computer Sites

Post by brianfry713 » Fri Nov 15, 2013 9:31 pm

I don't know, it depends on your implementation I guess. I would use an already existing simple greedy algorithm rather than trying to invent a new one. The old MST is essentially useless once you add new previously unconsidered edges. I think it would be much slower if you could get it to work at all.
Check input and AC output for thousands of problems on uDebug!

chanderg_12
New poster
Posts: 5
Joined: Fri Nov 15, 2013 2:06 pm

Re: 908-Re-connecting Computer Sites

Post by chanderg_12 » Wed Nov 20, 2013 6:15 pm

No. I mean something like Kruskal's algorithm except that we start with the given old MST and the new edges alone as the edge set to be sorted and then.....

Oh. Every time an edge threatens a cycle creation, we would again have to check the entire cycle to find out the bottleneck. But as we are already doing a traversal (to find if it is a cycle), will it be too much of an overload?

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

Re: 908-Re-connecting Computer Sites

Post by brianfry713 » Wed Nov 20, 2013 10:13 pm

I don't know. Try to over complicate it if you want.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 9 (900-999)”