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

Q1) Given a n rows of m seats, and a list of specific taken seats, return how many ways 2 people can sit next to each other. Limits: n and m up to 1 billion and number of taken seats up to 50.<\/strong><\/p>\n

A1) Very very easy.\u00a0 Use long long to avoid overflow.\u00a0 For each row with taken seats get the sorted taken seats in that row, then for each gap greater than 1, add gap-1 to the total.\u00a0 Finally add number of empty rows times m-1.<\/p>\n

Not my favourite kind of question, simply because I am not uber-speed code writer.<\/p>\n

Q2) Given a counter which ticks down every minute, and a set of k items which each have a time length, but increase the counter by j at a specific time within that time length, determine the maximum number of items which can be processed completely before the counter drops below 0.\u00a0 If there are multiple ways to achieve this goal, return the order which prefers lower numbered items first. Limits: k up to 20.
\n<\/strong><\/p>\n

A2) Each item has a minimum requirement, and a net effect. If there is a non-negative net effect which we can meet the minimum requirement for, we want to use it. If there are only negative net effects, which we can meet the minimum requirements for, we will never be able to use anything which is currently not at minimum requirement.\u00a0 However, the order of the things left is non-trivial.<\/p>\n

With a limit on k of only 20, every possible subset is a valid consideration if we can process it quickly. This provided a hint, but I needed to look at a solution to get the rest. If we divide the input into start and end sections, we can determine which of the end section can be placed immediately after the start section.\u00a0 This lets us create a DP of maximum number which can be processed from a set which appear after the rest not in the set (regardless of whether the rest not in the set can actually all be processed before it).\u00a0 That final condition may sound crazy, but once you get to the full set,\u00a0 the not-in set becomes empty set and the condition is fine, so the rest doesn’t matter.<\/p>\n

Once the DP is done, you just have to do the ‘reverse dp walk’ to construct the output.<\/p>\n

Q3) Given a list of items and 2 queues to put them in, where each item has a processing time, which depends which queue it is in, and after processing is placed into the other queue, unless it has already been processed by that queue, determine how many different ways to place the items in the 2 queues subject to 2 conditions.\u00a0 1) The items have to be added to the queues in the same order as the input. 2) Neither queue must ever be empty before the other queue has finished its initial list. Limits: up to 47 items and each processing time is between 1 and 20.<\/strong><\/p>\n

A3) No clue – the processing time limit seems suspiciously small though. Maybe a dp on the number of solutions with an initial queue time of n?\u00a0 Let me look at a solution.<\/p>\n

Rather than solving the problem as given, solve a different problem, number of ways for queue 1 to run out before queue 2 is done its initial list.\u00a0 Then switch queues and use the same logic again.\u00a0 Subtract both from number of possible distributions.<\/p>\n

So, how to count the number of ways for it to run out. Each time we put something on to queue 1, it makes it harder to run out, each time we put something on queue 2 it is easier to run out.\u00a0 Some analysis is required to work out the DP.\u00a0 The definition of fail is if total queue 1 time + total time of first i-1 from queue 2 processed at queue 1 speed – total time of first i from queue 2 processed at queue 2 speed < 0 for any i.\u00a0 We want to know what the minimum of the left for any i is, for each possible distribution in order to know whether it has failed, if that minimum is less than 0, then it is a fail.\u00a0 As each new item is added to the pile this function changes.\u00a0 If we add one to queue 1, all possible left hand sides increase by the processing time, thus also increasing the minimum.\u00a0 If we add one to queue 2, the inequality doesn’t change except for the new i=new length of queue 2 case.\u00a0 In that case the inequality equals the previous scenario where all were processed minus the new addition as a possible new minimum.\u00a0 So we can minimize between that and the old minimum.\u00a0 The only problem is we need to know that previous scenario as well.\u00a0 So ‘previous scenario’ and ‘minimum’ are 2 parameters to the DP, the 3rd being number of items en-queued.<\/p>\n

Now that we have this new parameter we need to know how it changes.\u00a0 If we add to the first pile, it goes up exactly the same as the minimum does, adding the queue 1 processing time.\u00a0 If its added to the second queue, that causes a subtraction of the queue 2 processing time, and an addition of the queue 1 processing time.<\/p>\n

Potential range on previous scenario and minimum are pretty large so memory is an issue if the entire dp was kept in memory.\u00a0 Helpfully each case only depends on the previous number of items en-queued, and the final summation is only on the full list of items en-queued, so we can throw away memory as we go. (Avoid garbage collection issues and alternate arrays, don’t keep allocating.)\u00a0 Additionally with the inequality range being +\/- ~900, that is close to 200million dp locations filled without any optimisation.\u00a0 Running with c++ this is probably reasonable, but with Java further trimming helped.\u00a0 For instance minimums only ever get smaller and we are only interested in the negative ones, so treat all positive minimums as 0, and we save half the state space.\u00a0 Furthermore the area of the DP increases by +\/- 20 in both dimensions with each step, taking this into account can save another factor of ~3 rather than blindly checking every spot.<\/p>\n

Again out of my range, but useful to sit down and understand how it works.<\/p>\n","protected":false},"excerpt":{"rendered":"

Q1) Given a n rows of m seats, and a list of specific taken seats, return how many ways 2 people can sit next to each other. Limits: n and m up to 1 billion and number of taken seats up to 50. A1) Very very easy.\u00a0 Use long long to avoid overflow.\u00a0 For each … Continue reading TC SRM 469<\/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-235","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\/235","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=235"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/235\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=235"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=235"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=235"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}