## Search found 35 matches

Sun May 11, 2014 12:39 pm
Forum: Volume 4 (400-499)
Topic: 452 - Project Scheduling
Replies: 23
Views: 9436

### Re: 452, Why WA

Thanks for the test cases Brian Fry. For this problem it requires some work to create testcases.
Tue May 06, 2014 12:08 am
Forum: Volume 5 (500-599)
Topic: 558 - Wormholes
Replies: 30
Views: 14182

### Re: 558 - Wormholes

Oh ok thanks, may be I didn't consider that.
Sat Apr 26, 2014 1:04 pm
Forum: Volume 120 (12000-12099)
Topic: 12083 - Guardian of Decency
Replies: 2
Views: 1503

### 12083 - Guardian of Decency

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...
Fri Apr 25, 2014 4:59 am
Forum: Volume 7 (700-799)
Topic: 796 - Critical Links
Replies: 54
Views: 21546

### Re: 796 - Critical Links

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...
Wed Apr 23, 2014 1:31 pm
Forum: Volume 3 (300-399)
Topic: 315 - Network
Replies: 68
Views: 20174

### Re: 315: Network

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

Code: Select all

``````1
0
``````
It should be

Code: Select all

``````1
0
0
``````
Mon Apr 21, 2014 2:59 am
Forum: Volume 7 (700-799)
Topic: 753 - A Plug for UNIX
Replies: 20
Views: 10083

### Re: 753 - A Plug for UNIX

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...
Sun Apr 20, 2014 10:08 am
Forum: Volume 103 (10300-10399)
Topic: 10349 - Antenna Placement
Replies: 16
Views: 7147

### Re: 10349 - Antenna Placement

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...
Fri Apr 18, 2014 6:07 am
Forum: Volume 111 (11100-11199)
Topic: 11159 - Factors and Multiples
Replies: 19
Views: 11482

### Re: 11159 - Factors and Multiples

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...
Wed Apr 09, 2014 10:47 pm
Forum: Volume 4 (400-499)
Topic: 454 - Anagrams
Replies: 97
Views: 19952

### Re: 454 Anagrams WA

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...
Tue Apr 08, 2014 1:19 pm
Forum: Volume 114 (11400-11499)
Topic: 11418 - Clever Naming Patterns
Replies: 9
Views: 4203

### Re: 11418 - Clever Naming Patterns

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 ...
Thu Apr 03, 2014 12:10 pm
Forum: Volume 5 (500-599)
Topic: 599 - The Forrest for the Trees
Replies: 18
Views: 7383

### Re: 599-The forest for the trees

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.
Thu Apr 03, 2014 12:06 pm
Forum: Volume 5 (500-599)
Topic: 558 - Wormholes
Replies: 30
Views: 14182

### Re: 558 - Wormholes

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...
Wed Apr 02, 2014 12:23 pm
Forum: Volume 115 (11500-11599)
Topic: 11506 - Angry Programmer
Replies: 6
Views: 5602

### Re: 11506 - Angry Programmer

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...
Wed Apr 02, 2014 10:50 am
Forum: Volume 12 (1200-1299)
Topic: 1225 - Digit Counting
Replies: 17
Views: 4023

### Re: 1225 - Digit Counting

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...
Mon Mar 31, 2014 9:02 am
Forum: Volume 2 (200-299)
Topic: 259 - Software Allocation
Replies: 28
Views: 10398

### Re: 259 - optimizing..

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.