catvsdog's Introduction
This program solves the Kattis catvsdog problem that is available here: https://open.kattis.com/problems/catvsdog. It also prints trace output to stderr that identifies the animals that can be kept and the people satisfied in the optimal solution. The graph class used in this implementation, named FlowNetwork, is quite unusual. The graph edges are stored in an adjacency matrix. The implementation actually uses two matricies, one for capacity, one for flow. These matricies completely define the graph. Additionally, an adjacencyList is kept. However, this list does not mirrror the information in the matricies. Rather, it stores nodes with residual flow that are adjacent. This is done so that the residual capacity adjacency lsit can be returned in constant time. This design came about because iterating through the matricies to determine residual flow adjacency caused the program to time out. Also, the FlowNetwork class includes a convenience feature that maps VoterPreferences (the internal representation of people) to an integer index. The integer is then used to index the matricies and lists that represent the graph. This is not strictly necessary, but was convenient. Basically, the program parses the input and, for each test case, builds a list of the preferences for the voters. The voters are divided into two groups: dog lovers and cat lovers. A FlowNetwork is initialized as a bipartite graph with a soure connected to the cat lovers and the dog lovers connected to the sink. The cat lovers are connected to the dog lovers if their preferences conflict. On this graph, we run Edmunds-Karp max flow algorithm. The max flow represents the minimum number of dissatisfied voters. Thus the maximum number of satisfied voters is the number of voters minus the max flow. To produce the trace informatoin we run BFS (which is also used by Edmunds-Karp) one last time. From this BFS, the satisfied voters are the reachable cat lovers and the unreachable dog lovers. The animals that can be kept are the preferred animals of the satisfied voters. There are no known problems with the correctness of the code.
catvsdog's People
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. ๐๐๐
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google โค๏ธ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.