Search found 18 matches

by Mg9H
Sun Sep 24, 2006 11:22 pm
Forum: Algorithms
Topic: I NEED HELP WITH DYNAMIC PROGAMMING
Replies: 2
Views: 1869

Re: I NEED HELP WITH DYNAMIC PROGAMMING

Hi :) This link has 3 questions of dynamic programming I dont know how to solve the first question (Interleaving) http://www.cs.berkeley.edu/~jordan/courses/170-fall05/homeworks/hw9.pdf If someone knows please help me! what should be the recurrence, base conditions and why? Thanx... DP array D [N][...
by Mg9H
Mon Sep 18, 2006 4:18 pm
Forum: Algorithms
Topic: VERY CHALLENGING QUESTION OF NETWORK FLOW
Replies: 6
Views: 4510

can you please define the network flow? what will be the perfect matching? Think of your matrix as a adjacency matrix for a bipartite graph with N vertices in each set, i.e. M [j] = the capacity of an edge from X to Y [j] (i, j = 1, 2, .., N). Now, add 2 more vertices S & T to this graph, add N edg...
by Mg9H
Mon Sep 18, 2006 1:26 pm
Forum: Algorithms
Topic: VERY CHALLENGING QUESTION OF NETWORK FLOW
Replies: 6
Views: 4510

Re: The question

If that is the definition of REARRABLEABLE, I believe a matrix NxN is rearrangeable iff it has a perfect matching (which can be determined in O(N^3)). I'll write the question as it is in the 'Algorithm Design' book: (Chapter 7: Network flow page 428 question 22) Let M be an nxn matrix with each entr...
by Mg9H
Mon Sep 18, 2006 5:59 am
Forum: Algorithms
Topic: VERY CHALLENGING QUESTION OF NETWORK FLOW
Replies: 6
Views: 4510

Re: VERY CHALLENGING QUESTION OF NETWORK FLOW

Hi all here is a a good link: http://www.cs.uiuc.edu/class/sp06/cs473g/exbook.pdf I have no idea how to solve question 3.1.11 (page 33 in the pdf file) the one with the matrice of 0-1... If somebody knows what network flow should be constructed please help me P.S: 3.1.12 (Unique cut) I have no idea...
by Mg9H
Tue Aug 08, 2006 4:44 am
Forum: Volume 110 (11000-11099)
Topic: 11061 - Playing War
Replies: 41
Views: 10490

Well, but in each attack both of them may use up to 3 armies, therefore on each side up to 3 armies may die in one attack. actually there are exactly bno = min (Attack, Defense) (<= 3) battles can happen in 1 attack, and exactly that many armies (in total, counting from both side) will die. i think...
by Mg9H
Mon Aug 07, 2006 2:43 pm
Forum: Volume 110 (11000-11099)
Topic: 11060 - Beverages
Replies: 96
Views: 31970

There is no relation between a and b, so a must be drunk before b, because it appears earlier in the list; There is a relation between a and c that dictates that c should be drunk before a; There is no relation between b and c, so b must be drunk before c, because it appears earlier in the list. Th...
by Mg9H
Mon Aug 07, 2006 1:06 pm
Forum: Volume 110 (11000-11099)
Topic: 11061 - Playing War
Replies: 41
Views: 10490

on each level they roll the dice attakers hava the probabillity of 15/36 to kill one defender ( becauese there is 15 pair of numbers between 1 and 6 that the first one is greater than the second one ) and defender has the probabilty of 21/36 to kill one attacker Well, but in each attack both of the...
by Mg9H
Mon Aug 07, 2006 12:59 pm
Forum: Volume 110 (11000-11099)
Topic: 11060 - Beverages
Replies: 96
Views: 31970

I assumed there were no cycles - because they didn't say what to do in the case of one. I am still not sure what I did wrong with my solution, it was supposed to be a simple topological sort, right? What is output for this: 3 a b c 1 c a I get: Code: Case #1: Dilbert should drink beverages in this ...
by Mg9H
Sun Aug 06, 2006 1:12 am
Forum: Volume 110 (11000-11099)
Topic: 11063 - B2-Sequence
Replies: 73
Views: 39579

Re: 11063 B2-Sequence

Ok, what is the trick in this one? I solved B by switching from Java to C and realizing that my WAs were actually RTEs (books with negative costs..sigh). I was about to try to do that with this problem, too, but just ran out of patience. Ok, I eventually realized that "pairwise" included sum of an ...
by Mg9H
Sun Aug 06, 2006 1:10 am
Forum: Volume 110 (11000-11099)
Topic: 11060 - Beverages
Replies: 96
Views: 31970

I assumed there were no cycles - because they didn't say what to do in the case of one. I am still not sure what I did wrong with my solution, it was supposed to be a simple topological sort, right? What is output for this: 3 a b c 1 c a Yes, it's just a simple topological sort, but be careful when...
by Mg9H
Sun Aug 06, 2006 12:59 am
Forum: Volume 110 (11000-11099)
Topic: 11060 - Beverages
Replies: 96
Views: 31970

Re: 11060: Beverages

Martin Macko wrote:Well... the beverages relation is transitive, but is it asymmetric? If it is not, what is the correct answer for the following?

Code: Select all

5
a
b
c
d
e
5
a b
b c
c d
d b
c e
I believe the input will not form any "circles" because of the background information about alcohol content of the beverages.
by Mg9H
Thu Nov 24, 2005 1:38 pm
Forum: Volume 5 (500-599)
Topic: 558 - Wormholes
Replies: 30
Views: 14672

It's a little late for replying this but your algorithm works correctly because the first loop is a Ford-Bellman loop, which works perfectly in graph with negative edges but no negative cycle. Since Ford-Bellman algorithm broke when graphs have negative cycle (by "broke", i mean the minimum distance...
by Mg9H
Mon Nov 21, 2005 8:08 am
Forum: C++
Topic: what c++ compiler is used ?
Replies: 2
Views: 1899

Re: what c++ compiler is used ?

Check your email, a copy of the respond and some detail information (in this case, which functions cause the compiler to generate CE) will be sent to your registered email. I've had a 'compile error' when submitting a solution in C++, I'm quite surprised because I've been testing the code with sever...
by Mg9H
Sun Nov 20, 2005 3:35 pm
Forum: Other words
Topic: What's going on?
Replies: 7
Views: 3144

judge system still not working. The judge is saying "cant be judged" to every problems. i think uva online judge is passing their worst time. For a long time "update info", "recover password" links are not working. the last online contest was NWEPC at 13th november. but still those problems are not...
by Mg9H
Sun Nov 20, 2005 1:45 pm
Forum: Other words
Topic: What's going on?
Replies: 7
Views: 3144

The judge system is back a few minutes ago. Yahoooooooo :D

Go to advanced search