UVa OJ Board

Thanks for the test cases Brian Fry. For this problem it requires some work to create testcases.

Oh ok thanks, may be I didn't consider that.

This is an interesting MIS problem (Maximum Independent Set). You can create a bipartite graph between men and women. Connect men to all those women whose height difference with men is <= 40 and music is different and sport is the same (3 conditions). After that just use the MCBM algorithm to get th...

Here a single large test case with 100 nodes. 100 2 (1) 0 18 (15) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 39 (30) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 13 (10) 0 1 2 3 4 5 6 7 8 9 83 (38) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 2...

The following test case is wrong because in the problem statement it says that each block ends with a 0 and the entire input itself ends with a 0. So we are missing a zero here.

Invalid Input
It should be

Here is some input - output for those getting WA. Also note that you don't need to use edmonds-karp/ford-fulkerson algorithm to solve this problem. It's a bipartite graph and can be solved by an n^3 algorithm explained here. http://www.geeksforgeeks.org/maximum-bipartite-matching/ Output for this in...

This is a standard MCBM problem. Just create the bipartite graph and run the alternating path algorithm (n^3) explained here. http://www.geeksforgeeks.org/maximum-bipartite-matching/ Here are some test cases: Input 50 40 7 *o***oo ooooo*o oo**ooo ***o*** *o***o* *oooooo oo*ooo* **oo*o* ***o*oo o*o*o...

Don't use ford-fulkerson/edmond-karp in its direct form to solve this problem or else you will get TLE. That's because these two are n^5. You can either use relabel to front or the algorithm explained here. Both of these are n^3. http://www.geeksforgeeks.org/maximum-bipartite-matching/ . The later o...

But you're printing a newline after each case - including the last one. True. But sometimes we get away with it and get AC and at other times it gives WA instead of PE which can be frustating. I realized there are two ways this is mentioned in the problems. 1. Print a new line between every testcas...

This is a standard Maximum Flow problem and you can get AC in 1/10th of a second with Edmond - Karp algorithm (augumenting path by BFS). Main thing is to build the graph correctly. Attached is an image of what the graph will look for the first case. All edge weights are 1. You will also need to add ...

brianfry713 wrote:acorn not acron

That was nice ! Attention to detail ! Sometimes I use windiff to compare sample output with my output just to catch these kind of "eye tricking" errors.

Standard Bellman-Ford Algorithm : Given a weighted directed graph, check whether it has a negative weight cycle. You only need to run bellman-ford algorithm once from vertex 0. Here are testcases: Input 200 6 10 2 3 235 5 1 -151 0 4 845 2 1 -20 4 0 554 2 0 -161 1 4 1039 1 3 85 2 4 -262 0 3 -442 6 10...

The main thing in this problem is to build the graph correctly. If you split a node, make sure you add two edges between Vin and Vout. The edge Vin - Vout will have the cost specified in the question. The back edge Vout - Vin will have cost 0 initially. Now for edges between nodes, you will need 2 f...

On problems with a special judge you may be able to get away with extra spaces and still get AC. oh okay, thanks brian, actually i have made a rule to not put spaces if they haven't asked for as this has caused lot of suffereing. That's because in some cases extra spaces give wrong answer instead o...

Any one can get runtime error because input may be like

A1 13579;
B1 a-123;

Handle this i got accepted other wise i got runtime error.

There is no test case like this in the judge's input. Input format isn't tricky either. I use cin and cout to read/write input/output.