OJ Board

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

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

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

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

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

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

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

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

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

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

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.

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

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

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

The judge system is back a few minutes ago. Yahoooooooo