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

Q1) Given a dictionary and a mapping of numbers to sets of letters, and an input sequence consisting of numbers, ‘try alternate’ button pushes and ‘spaces’, determine the output.\u00a0 Assume dictionary is processed in alphabetical order.<\/strong><\/p>\n

A1) Easy enough, make a dictionary of number sequences to list of words that match, sort each list, then process input to produce output…<\/p>\n

Q2) Given a graph with a line of nodes each connecting from one to the next, determine the minimum time to get from the first node to the last.\u00a0 Subject to some special conditions.\u00a0 Each edge has two time options for its travel.\u00a0 The first is always available, but the second can only be used if there are less than k contiguous sections where second option has already been used, or you used the second option for the last edge. The number of nodes n is up to 400thousand, and k is up to n or 40, whichever is lower.\u00a0 The first and second times for each travel option are generated using a pseudo-random number generator with specified parameters.<\/strong><\/p>\n

A2) While writing my question text above I may have made this question even easier due to my phraseology.\u00a0 Its a DP problem, 3 parameters, number of contiguous sections of second option so far, boolean if last was second option and how many nodes passed already.\u00a0 Very easy, only problem is that it requires 64meg ram in the default dp table.\u00a0 Luckily every entry only depends on the ones at one less nodes passed.\u00a0 Lucky because that means we can get rid of the memory problem, and also because if it depended on all of them the processing time would have been excessive.<\/p>\n

Q3) Given a k-partite graph where each ‘layer’ only connects to its neighbours (arranging the k layers in a circle), determine the maximum independent set.\u00a0 Limits: Maximum vertices is 100, k between 10 and 50.<\/strong><\/p>\n

A3) When I first saw this problem I was shocked, a question 3 which maybe I can actually do.\u00a0 (The original question isn’t phrased as given, but still it was obvious this was the real question.)\u00a0 I unfortunately pretty quickly came to the realisation that the graph itself didn’t have any limitations which guaranteed it was bipartite. If k was even, I was good to go, but when k is odd, I had a problem.\u00a0 I thought about it for quite a while, and along the way I had the idea that I could try all the possibilities for one of the layers, and do the rest pretending it was a bipartite graph.\u00a0 Unfortunately I threw this thought away because I didn’t remember that k was at least 10, and so I decided that worst case would be 33 vertices as the smallest layer and 2^33 scenarios is too many to consider.\u00a0 With k at least 10 (or we might as well say 11 since 10 is trivial and a maximum vertices of 100, the worst case scenario is when the 100 vertices are distributed in layers of 10 or 9.\u00a0 Select one of the rows with only 9 in it, and try all 2^9 scenarios.\u00a0 For a given layer if we are trialling a vertex as being in the independent set, we can remove it, and any immediate neighbour vertexes.\u00a0 If not we just remove it.\u00a0 This removes the entire layer, leaving us with a bipartite graph which we can solve via the dual maximum matching problem using simple maxflow on a graph with capacities which are all 1.\u00a0 Add in the number of ‘independent’ vertexes in the current trial and choose maximum over all trials and done.\u00a0 Probably one of the easier question 3’s I’ve seen recently.<\/p>\n","protected":false},"excerpt":{"rendered":"

Q1) Given a dictionary and a mapping of numbers to sets of letters, and an input sequence consisting of numbers, ‘try alternate’ button pushes and ‘spaces’, determine the output.\u00a0 Assume dictionary is processed in alphabetical order. A1) Easy enough, make a dictionary of number sequences to list of words that match, sort each list, then … Continue reading TC SRM 468<\/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-238","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\/238","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=238"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/238\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=238"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=238"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=238"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}