05/7/15

Codility ‘SqlSegmentsSum’ Kalium 2015 Solution

Short Problem Definition:

Compute the total length covered by 1-dimensional segments.

Link

SqlSegmentSum

Complexity:

time complexity

space complexity

Execution:

I first create a numbers table from 1 to 1.000.000, this could be done just once when creating the DB. In this challenge it adds a flat 0.3sec runtime to all testcases.

In the second step I simply unique join the segments and number tables.

Solution:
-- create numbers utility structure, very basic integer primary key column n
create table numbers(n integer not null, primary key(n asc));
-- insert generated sequential integers
insert into numbers(n)
select rowid
from (

-- build 1,000,000 rows using Cartesian product
select 1
from (
   select 0 union select 1 union select 2 union select 3
   union select 4 union select 5 union select 6
   union select 7 union select 8 union select 9
) a, (
   select 0 union select 1 union select 2 union select 3
   union select 4 union select 5 union select 6
   union select 7 union select 8 union select 9
) b, (
   select 0 union select 1 union select 2 union select 3
   union select 4 union select 5 union select 6
   union select 7 union select 8 union select 9
) c, (
   select 0 union select 1 union select 2 union select 3
   union select 4 union select 5 union select 6
   union select 7 union select 8 union select 9
) d, (
   select 0 union select 1 union select 2 union select 3
   union select 4 union select 5 union select 6
   union select 7 union select 8 union select 9
) e, (
   select 0 union select 1 union select 2 union select 3
   union select 4 union select 5 union select 6
   union select 7 union select 8 union select 9
) f

) derived;

select count(distinct n) from numbers inner join segments
on numbers.n between segments.l+1 and segments.r

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
05/7/15

Codility ‘CannonBalls’ 2012 Chi Solution

Short Problem Definition:

Simulate a cannon shooting and heaps of falling cannonballs

Link

Cannon Balls

Complexity:

expected worst-case time complexity is O(H+M+N)

expected worst-case space complexity is O(H+M)

Execution:

The obvious brute force solution would be to check the minimum index that is high enough to block the shot. This would result in a N*M runtime. Based on observation we can see that the hit location can be precomputed and it changes only with small steps.

  • -1 in the hit_location means, that the ball either ricochets or flies above the highest peak
  • anything that hits the 0th index also does nothing
Solution:
def solution(A, B):
    highest_ball = max(B)
    hit_location = [-1] * (highest_ball+1)
    ricochet = A[0]
    
    for idx, a in enumerate(A):
        lvl = min(a, highest_ball)
        while hit_location[lvl] == -1 and lvl > ricochet:
            hit_location[lvl] = idx
            lvl -= 1
            
    # print hit_location

    for ball in B:
        hits_at = hit_location[ball]
        # print "ball", ball, "hits at", hits_at
        if hits_at <= 0:
            continue
        A[hits_at-1] += 1
        hit_location[A[hits_at-1]] = min(hit_location[A[hits_at-1]], hits_at-1)
        
        
    return A

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin