{"id":193,"date":"2013-04-30T15:39:01","date_gmt":"2013-04-30T12:39:01","guid":{"rendered":"http:\/\/www.nicau.ro\/?p=193"},"modified":"2013-04-30T17:06:26","modified_gmt":"2013-04-30T14:06:26","slug":"no-rocket-science","status":"publish","type":"post","link":"https:\/\/www.nicau.ro\/?p=193","title":{"rendered":"No rocket science"},"content":{"rendered":"

\"The<\/a><\/p>\n

Who wants to solve with me a rocket problem? All right \ud83d\ude42 We might not be rocket scientists but we surely enjoy rocket and mountain problems, especially when they act as cover-up for some computer science subject.<\/p>\n

In this case, for those of you seeking the simplest possible method there is a naive approach that can be written in a couple minutes \ud83d\ude09 We will not discuss that. Instead, we are interested in an optimal solution with linear time complexity.<\/p>\n

Problem Description:<\/strong><\/p>\n\n\n\n
\nWe are testing a new type of projectile which is launched in a fixed direction. Each rocket flies horizontally until it hits the ground, and remains there piling up. Launching happens from different heights so they hit the ground at different points. <\/p>\n

As input you will receive two zero based arrays, A and B, each containing respectively M and N integers. Array A describes the lanscape in the direction the projectile is launched. Each element from A represents the height of the ground starting from the projectile launcher. Array B contains successive heights from where rockets are shot.<\/p>\n

Let’s assume the launcher shoots a rocket from height H. If I is the smallest index with 0 < I < M and A[I] >= H, then the rocket falls at position I – 1 and increases ground level A[I – 1] with 1.<\/p>\n

If there is no such I and launch height H > A[I] for all 0 <= I < M the rocket flies beyond horizon and does not affect any part of the lanscape.\n\nIf H <= A[0] then the rocket ricochets away and again there is no effect on the result. \n\nYou will have to write an algorithm to simulate the flight of rockets given A, B vectors of M and N sizes. The algorithm will produce a result array RA, which will contain the updated line of lanscape based on the initial landscape A and the shooting described through the B projectile launcher successive heights.\n\nExample:\n   M = 4; N = 8;\n   A[0] = 0; A[1] = 0; A[2] = 0; A[3] = 4;\n   B[0] = 1; B[1] = 1; B[2] = 0; B[3] = 6; B[4] = 1; B[5] = 2; B[6] = 3; B[7] = 2;\n\nResult:\n   RA[0] = 1; RA[1] = 2; RA[2] = 3; RA[3] = 4;\n\nBounds:\n   M, N - integers [0..50000]\n   each element of A is an integer [0..2000000]\n   each element of B is an integer [0..2000000]\n\nComplexity concerns:\n - worst case time complexity should be O(M + N + H)\n - worst case space complexity should be O(M)\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Discussion:<\/strong><\/p>\n

As we see from the time complexity O(M + N + H) a linear solution is expected. There cannot be any nested loops, recursion or other methods that would make it polynomial or worse. Linear sounds great but how?<\/p>\n

Let’s do some logical connections. What we know or can be found easily:<\/p>\n

• we know the current landscape configuration, a sequence of heights stored in array A<\/p>\n

• based on it we can find the maximum landscape height MAXH<\/p>\n

• maybe the landscape contains MAXH more than once, but we only care for the first “peak”<\/p>\n

• side note. why we only care for the first peak. if the landscape did contain multiple positions having same height, there is no way for a flying rocket to reach the 2nd or other subsequent peak, without crushing into the first peak.<\/p>\n

• we extend this search for all valid heights. so for each height h with 0 <= h <= MAXH we need to find the minimum landscape index MINL(h) = { i | h = A[i] and i is minimum }.\n\n • although it contains the maximal value of MAXH, certain landscape inputs might not contain an index for every other possible height in the range [0 .. MAXH] so there might exist such k with 0 <= k <= MAXH where MINL(k) is empty. this possibility obstructs us from using function MINL to forecast the first landscape index where a projectile is going to hit. To cover, we will define another function named MINLC:\n\nMINLC(h) = MINL(h), if MINL(h) is not ∅ \nOR \nMINLC(h) = smallest, nonempty MINL(h1), where h1 > h, if MINL(h) is ∅<\/p>\n

• here is an example. the landscape array contains four positions:
\n    A[0] = 0, A[1] = 3, A[2] = 3, A[3] = 5. <\/p>\n

The MAXH is 5, meaning that MINL contains the following values: <\/p>\n

    MINL(0) = 0
\n    MINL(1) = ∅
\n    MINL(2) = ∅
\n    MINL(3) = 1
\n    MINL(4) = ∅
\n    MINL(5) = 3<\/p>\n

MINLC will be equal to MINL for all non empty positions. For the rest:<\/p>\n

MINLC(height value 1) = index value 1, because the index 1 in landscape array A contains the first non-empty value satisfying height value 3 > height value 1 <\/p>\n

    MINLC(1) = 1
\n    MINLC(2) = 1
\n    MINCL(4) = 3<\/p>\n

• we should not forget that each rocket crushing into the ground falls at the previous landscape index increasing the local height. we will need to take into account such updates<\/p>\n

• due to the MINLC function, for any launch height, we can find directly which is the landscape index where the rocket falls. all we have to do is iterate the B array, find the index where the rocket falls by applying MINLC, then increase ground level at that position.<\/p>\n

Code:<\/strong><\/p>\n

• Note. This is a C99 solution focusing on readability rather than code length. Also, it can use better error logging or commenting. These aspects were not the purpose of this solution.<\/p>\n

• At this point we achieve the worst case time complexity of O(M + M + H + N) which can be further optimized into O(M + H + N) by introducing some std::map to store the (height, ground index) pairs. This way we eliminate the need for finding the largest height, then allocating memory space. I will leave this small exercise to you \ud83d\ude00<\/p>\n

\r\n\r\nstruct Results \r\n{\r\n    int * A1;\r\n    int M;\r\n};\r\n\r\nstruct Results shootingRockets(int A[], int M, int B[], int N)\r\n{\r\n    struct Results r;\r\n    memset(&r, 0, sizeof(r));\r\n\r\n    if (M < 1 || !A || !B)\r\n        return r;\r\n\r\n    if (N < 1)\r\n    {\r\n        r.A1 = A;\r\n        r.M = M;\r\n    }\r\n\r\n    \/\/find max terrain height\r\n    int maxTerrainH = -1;\r\n    int j = 0;\r\n    for (j = 0; j < M; ++j)\r\n    {\r\n        if (A[j] > maxTerrainH)\r\n            maxTerrainH = A[j];\r\n    }\r\n    \r\n    \/\/all rockets will fall before, or fly over\r\n    if (maxTerrainH <= 0)\r\n        return r;\r\n    \r\n    \/\/we are using extra storage space to accomodate\r\n    \/\/the index of the first peak of certain height.\r\n\r\n    \/\/the heights array will be maxTerrainH + 1 to\r\n    \/\/react correctly to launches from height 0\r\n    \r\n    int heightsCount = maxTerrainH + 1;\r\n    \r\n    int *heights = (int *)malloc(heightsCount * sizeof(int));\r\n    if (!heights)\r\n    {\r\n        return r;\r\n    }\r\n    \r\n    memset(heights, -1, heightsCount * sizeof(int));\r\n    \r\n    \/\/we are building the MINLC function:\r\n    \r\n    \/\/First step. iterate landscape positions,\r\n    \/\/store in heights array, only those indexes\r\n    \/\/with peaks of heights we haven't seen before\r\n    \r\n    int max = -1;\r\n    int k = 0;\r\n    for (k = 0; k < M; ++k)\r\n    {\r\n        if (A[k] > max)\r\n        {\r\n            max = A[k];\r\n            *(heights + max) = k;\r\n        }\r\n    }\r\n    \r\n    \/\/Second step. Some positions are stil storing -1\r\n    \/\/These landscape heights are not accessible\r\n    \/\/at this point through dirrect shots. We need to\r\n    \/\/calculate their heights value based on surrounding\r\n    \/\/heights.\r\n    \r\n    for (k = heightsCount - 1; k > 0; --k)\r\n    {\r\n        if (*(heights + k - 1) == -1)\r\n        {\r\n            *(heights + k - 1 ) = *(heights + k);\r\n        }\r\n    }\r\n    \r\n    \/\/iterate each launch height\r\n\r\n    for (k = 0; k < N; ++k)\r\n    {\r\n        \/\/rocket flies over horizon?\r\n\r\n        if (B[k] > maxTerrainH)\r\n        {\r\n            continue;\r\n        }\r\n        \r\n        \/\/find where does it hit ground\r\n\r\n        int whereItHits = *(heights + B[k]);\r\n        int whereItFalls = whereItHits - 1;\r\n        \r\n        if (whereItFalls >= 0)\r\n        {\r\n            \/\/increase ground level\r\n            A[whereItFalls] += 1;\r\n            \r\n            \/\/before, a rocket would fly over\r\n            \/\/now, due to the latest ground level increase,\r\n            \/\/hits right here. we have to update the heights array\r\n\r\n            if (*(heights + A[whereItFalls]) > whereItFalls)\r\n            {\r\n                *(heights + A[whereItFalls]) = whereItFalls;\r\n            }\r\n        }\r\n    }\r\n\r\n    if (heights)\r\n    {\r\n        free(heights);\r\n    }\r\n    \r\n    r.A1 = A;\r\n    r.M = M;\r\n\r\n    return r;\r\n}\r\n\r\n\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
Who wants to solve with me a rocket problem? All right \ud83d\ude42 We might not be rocket scientists but we surely enjoy rocket and mountain problems, especially when they act as cover-up for some computer science subject. In this case, for those of you seeking the simplest possible method there is a naive approach that […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[9,8,7],"tags":[],"_links":{"self":[{"href":"https:\/\/www.nicau.ro\/index.php?rest_route=\/wp\/v2\/posts\/193"}],"collection":[{"href":"https:\/\/www.nicau.ro\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.nicau.ro\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.nicau.ro\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.nicau.ro\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=193"}],"version-history":[{"count":80,"href":"https:\/\/www.nicau.ro\/index.php?rest_route=\/wp\/v2\/posts\/193\/revisions"}],"predecessor-version":[{"id":274,"href":"https:\/\/www.nicau.ro\/index.php?rest_route=\/wp\/v2\/posts\/193\/revisions\/274"}],"wp:attachment":[{"href":"https:\/\/www.nicau.ro\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=193"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.nicau.ro\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=193"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.nicau.ro\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=193"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}