{"id":229,"date":"2010-07-22T11:24:57","date_gmt":"2010-07-22T11:24:57","guid":{"rendered":"http:\/\/www.themissingdocs.net\/wordpress\/?p=229"},"modified":"2010-07-22T11:24:57","modified_gmt":"2010-07-22T11:24:57","slug":"tc-srm-470","status":"publish","type":"post","link":"https:\/\/www.themissingdocs.net\/?p=229","title":{"rendered":"TC SRM 470"},"content":{"rendered":"

Q1) Given a line of n (up to 51) rooms\u00a0 separated by gates of up to 16 different types, a game is to be played.\u00a0 One of the (non-end) rooms is the ‘target’ room, where both player 1 and player 2 want to get to.\u00a0 Player 1 starts in room 0, and player 2 starts in room n-1.\u00a0 Each player (starting with player 1) takes turns removing all gates of a specific type.\u00a0 At any time if someone can reach the target room, they have won.\u00a0 If both can reach the target room the game is considered a draw.\u00a0 Assuming optimal play return how quickly player 1 can win (if they can), or how quickly player 2 can win (if they can), or ‘draw’.<\/strong><\/p>\n

A1) This is a simple memotized recursion, using the bitset of gates removed as its state.\u00a0 At each stage of the recursion first check if the given bitset is a p1 win, p2 win or draw.\u00a0 If it is one of these 3 states, return 1, -1 or 0 – swapping the first two if the popcount of bitset is odd (cache the result of course).\u00a0 If it is not a win for either player and not a draw, recurse on each bit which is not in the bitset, and select the closest negative number to 0, 0, or largest number of all recursion options and return that (after caching it).<\/p>\n

While this approach is fast enough (50*2^16 worst case), a greedy implementation actually works.\u00a0 If you divide gate types into left, right, or both compared to the target room, then player 1 wins if left + both <= right, player 2 wins if right + both < left and in all other cases its a draw.\u00a0 Number of turns is 2*(left + both)-1 in the former, and 2*(right + both) in the later.\u00a0 Giving an O(n) solution, which works regardless of the number of gate types.<\/p>\n

Q2) Given two parallel rows of n dots, where some specific dots in row 1 are already connected to specific dots in row 2, determine the expected number of pairwise crosses formed if each remaining dot in row 1 is joined to a random remaining dot in row 2.\u00a0 Every dot in both rows will have exactly 1 line connecting it to another dot in a valid randomly generated situation. Limits: n is up to 10000 and count of specific starting joins is up to 50.
\n<\/strong><\/p>\n

A2) Summation of the expectation value of crossing for a specific pair over each pair of dots in row 1 will give the answer.\u00a0 However with n=10k n^2 is not fast enough.\u00a0 We can divide the problem into 3 cases.<\/p>\n

    \n
  1. 2 non-specified dots.\u00a0 Expectation value for all of these pairs is exactly 0.5, so we can sum all of these quickly. (O(1) time even.)<\/li>\n
  2. 2 specified dots.\u00a0 1 or 0, we know whether they cross.\u00a0 The 50*49\/2 pairs to consider is easily executed.<\/li>\n
  3. 1 specified dot and 1 non-specified dot.\u00a0 At 50*10k, this could be brute forced, with probability defined by the ratio of non-specified locations to the left\/right of the specified location in row 2, flipped if the specified dot in row 1 is to the left instead of right of the non-specified dot.\u00a0 However every non-specified dot is going to have the same ratio, only depending on whether it is left or right of the specified dot in row 1.\u00a0 Therefore by knowing how many specified dots there are to the left\/right of each end of each specified dot pair, this can be performed much faster.<\/li>\n<\/ol>\n

    Q3) Given a map, up to 50×50, with up to 4 pairs of towns which want a road built between them, determine the minimum cost to build the up to 4 roads required.\u00a0 Roads are free to build, and can go anywhere, except through a rock.\u00a0 Rocks are a side to side connected set of square tiles for which the entire set can revert to being normal ground for a specific cost.\u00a0 There are up to 62 rocks, and no 2 rocks have the same cost.\u00a0 No rocks overlap with any town, nor do any towns overlap with other towns.<\/strong><\/p>\n

    A3) This is a tough question.\u00a0 No one solved it in the competition.<\/p>\n

    A single pair of towns is trivial, you just create a directed graph where nodes are connected sets of map tiles of the same type, and side-to-side adjacency defines the graph edges.\u00a0 The incoming edges to rocks all have a cost equal to the cost of removing the rock, and the outgoing edges are free.\u00a0 Then you calculate shortest path from town to town.<\/p>\n

    Handling 4 town pairs is tricky, because you have to consider the case where the cost of a given rock is shared between more than 1 road.\u00a0 Looking at the solution write up, the suggested way to approach this is a dp over location and a mask indicating the towns are you are trying to join through this location, and the towns which are already joined.\u00a0 For\u00a0 each mask and position you consider each possible way of breaking the mask into 2 submasks.\u00a0 The cost for that combination is then the sum of the 2 sub mask costs minus the cost of getting to this node if both of the submasks have one or more lone towns out of the town pairs.\u00a0 The reason for the subtraction is if the submasks have a lone town then both of them have already incurred the cost of destroying this rock to get here, and so we need to refund it.<\/p>\n

    So far so good, however we have not handled anything to do with the cost between between nodes yet.\u00a0 For a given mask and location, we need to minimise its cost by considering we could come from another location with the same mask.\u00a0 If the mask has only pairs, it is already fully connected, so there is no road being built and we freely minimise everything.\u00a0 This lets us combine any road with another when we build up the mask to a higher bit count.\u00a0 If it does have a lone town, we have to pay the shortest path cost between the two vertexes (if it has multiple lone towns, we only have to pay the cost once!).\u00a0 This second case requires n^2 steps to ensure minimisation is complete. (The former can be performed in n steps, but it isn’t a significant performance boost.)<\/p>\n

    The final problem is that n^2 is kind of expensive considering we have to do it for most of the up to 256 masks.\u00a0 A particularly nasty arrangement of rocks can result in ~800 nodes in the graph.\u00a0 However, excluding the empty space nodes, there can only be at most 70 nodes ( 8 towns and 62 rocks).\u00a0 Every empty space node can be eliminated by connecting its incoming edges to its outgoing edges, since the incoming edges always have 0 cost, you basically just throw away that edge.\u00a0 Number of edges will increase significantly in some scenarios, but still all points shortest path\u00a0 will easily run in time with the lesser number of vertexes, and the overall algorithm benefits hugely from the decreased vertex count.<\/p>\n

    An interesting algorithm, certainly beyond my abilities to create on the fly.<\/p>\n","protected":false},"excerpt":{"rendered":"

    Q1) Given a line of n (up to 51) rooms\u00a0 separated by gates of up to 16 different types, a game is to be played.\u00a0 One of the (non-end) rooms is the ‘target’ room, where both player 1 and player 2 want to get to.\u00a0 Player 1 starts in room 0, and player 2 starts … Continue reading TC SRM 470<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,6],"tags":[],"class_list":["post-229","post","type-post","status-publish","format-standard","hentry","category-code-competitions","category-random-musings"],"_links":{"self":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/229","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=229"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/229\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=229"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=229"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=229"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}