Search found 35 matches
- Sun May 11, 2014 12:39 pm
- Forum: Volume 4 (400-499)
- Topic: 452 - Project Scheduling
- Replies: 23
- Views: 10665
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: 16002
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: 1731
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: 24222
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: 23918
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
It should be
Invalid Input
Code: Select all
1
0
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: 11377
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: 7918
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: 12379
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: 23550
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: 5022
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: 8584
Re: 599-The forest for the trees
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.brianfry713 wrote:acorn not acron
- Thu Apr 03, 2014 12:06 pm
- Forum: Volume 5 (500-599)
- Topic: 558 - Wormholes
- Replies: 30
- Views: 16002
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: 6063
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: 5121
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: 11324
Re: 259 - optimizing..
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.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.