Search found 35 matches

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

Re: 452, Why WA

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

Re: 558 - Wormholes

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

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

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

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
by vsha041
Mon Apr 21, 2014 2:59 am
Forum: Volume 7 (700-799)
Topic: 753 - A Plug for UNIX
Replies: 20
Views: 10589

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

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

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

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

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

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

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

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

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

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.

Go to advanced search