## Search found 18 matches

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