algorithm - Solving a graph game -


i've struggled time problem programming contest (andrew stankevich contest 21) game goes follows:

nick , peter play following game [...]. draw undirected bipartite graph g on sheet of paper, , put token 1 of vertices. after make moves in turn. nick moves first.

a move consists of moving token along graph edge. after vertex token before move, edges incident it, removed graph. player has no valid moves loses game.

the graph given , task find given start node, whether starting player wins or loses if both players play optimally. summarize

  • bipartite graph
  • we given start node (say on left side)
  • we move in turns, move consists of following edge, can't visit node visited
  • the player cannot move loses

since graph bipartite, nick (the first player) remove node left side , peter remove node right side.

the graph can have 1000 nodes (at 500 @ each side) , 50000 edges, polynomial time algorithm needed (the time limit here 2 seconds solve starting positions, think can share lot of information between different starting positions).

i'm pretty sure can reduced kind of vertex covering or packing problem, because graph bipartite, can't find strategy correlates of these.

i know solution special case: let's sides have n1 , n2 vertices, respectively. if there matching of size min(n1, n2) , if player on smaller side begins, there exists winning strategy: has follow matched edges , automatically wins.

any ideas?

proposition. nick (the first player) wins starting vertex v iff vertex belongs every possible maximum matching of given graph. prove in 2 steps.

  1. if there maximum matching without v, nick loses.
    indeed, since matching maximum, there no augmenting path v. means every simple odd-length path v can prolonged edge of matching. in terms of our problem, means game can continued peter after every nick's move.

  2. if there no maximum matching without v, nick wins.
    consider possible maximum matching. move along edge of matching v to, say, u. now, initial matching minus edge u-v maximum matching of remaining graph not include u. know step 1, player move (which peter) @ loss.

as implementation, can first construct maximum matching in o(ve) utilizing straightforward algorithm (see here example implementation) — turns out common name kuhn's augmenting paths algorithm.

after that, maintain maximum matching , @ every vertex. if vertex, v, not in matching, nick loses. if is, remove corresponding edge, v-u, matching, forbid vertex v temporarily , run search augmenting path u in o(e). if don't find such path, nick wins, , have restore edge removed. otherwise, nick loses again, , new maximum matching can left untouched. total running time o(ve) again.


Comments

Post a Comment

Popular posts from this blog

android - Get AccessToken using signpost OAuth without opening a browser (Two legged Oauth) -

i using signpost oauth access data magento server. have read various tutorials on same , reach point open browser user can enter credentials. however, per requirement have automate part. hence, user should not browser page. have set-up done on server side ( magento ), hit url , returned call page. same through program in android. i have tried below, consumer = new commonshttpoauthconsumer(key, secret); provider = new commonshttpoauthprovider(oauth_init_url,access_token_url, authorize_url); try { provider.retrieverequesttoken(consumer, oauth.out_of_band); log.d("tokens" , consumer.gettoken() + " -- " + consumer.gettokensecret()); } and request tokens. dont know how bypass next step. tried directly accessing accesstoken (stupid of me) provider.retrieveaccesstoken(consumer, "mycallback://callback"); no luck, ends in oauth.signpost.exception.oauthnotauthorizedexception: authorization failed (server replied 401). ...
Read more

org.mockito.exceptions.misusing.InvalidUseOfMatchersException: mockito -

getting error org.mockito.exceptions.misusing.invaliduseofmatchersexception: invalid use of argument matchers! 1 matchers expected, 2 recorded. exception may occur if matchers combined raw values: //incorrect: somemethod(anyobject(), "raw string"); when using matchers, arguments have provided matchers. example: //correct: somemethod(anyobject(), eq("string matcher")); at when( getprogramservice .callservice(any(getprogramtype.class))) .thenreturn(jaxbresponse); please explain error , possible resolution the code posted looks fine; don't see problem it. code before or above causing exception. key here: invalid use of argument matchers! 1 matchers expected, 2 recorded. any , used above, doesn't return "special kind of null" or "special kind of getprogramtype"; don't exist. instead, returns null , side effect puts matcher on stack. whe...
Read more

google shop client API returns 400 bad request error while adding an item -

i'm working on solution add items in google shopping market java application. following tutorial real mess because of missing classes of laste release, after setting 1.5-beta maven managed make base example typecheck correctly classes. still can make simple task of adding 1 item. instead of posting whole code i'm posting part creates product feed. private product createproduct(string id) { product product = new product(); product.title = "red wool sweater"; product.content = new content( "text", "comfortable , soft, sweater keep warm on " + "cold winter nights. red , blue stripes."); product.appcontrol = new appcontrol(); product.appcontrol.addrequireddestination("productads"); product.externalid = id; product.lang = "it"; product.country = "it"; product.condition = "nuovo"; product.price = new price("eu...
Read more