Short Problem Definition:

The member states of the UN are planning to send 2 people to the moon. They want them to be from different countries. You will be given a list of pairs of astronaut ID’s. Each pair is made of astronauts from the same country. Determine how many pairs of astronauts from different countries they can choose from.

Link

Birthday Chocolate

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

Keep track of Melements at a time. Basically a simplified prefix sum.

Solution:

#!/bin/python

import sys

def getWays(squares, d, m):
    cnt = 0
    q = squares[:m-1]
    for ele in squares[m-1:]:
        q.append(ele)
        if (sum(q) == d):
            cnt += 1
        q.pop(0)
    return cnt

n = int(raw_input().strip())
s = map(int, raw_input().strip().split(' '))
d,m = raw_input().strip().split(' ')
d,m = [int(d),int(m)]
result = getWays(s, d, m)
print(result)

Short Problem Definition:

A left rotation operation on an array shifts each of the array’s elements 1 unit to the left. For example, if 2 left rotations are performed on array [1,2,3,4,5], then the array would become [3,4,5,1,2].

Link

Arrays: Left Rotation

Complexity:

time complexity is O(N)

space complexity is O(N)

Execution:

Solutions like this is where python really shines. Simple and straight forward.

Solution:

#!/bin/python

import math
import os
import random
import re
import sys

# Complete the rotLeft function below.
def rotLeft(a, d):
    return a[d:] + a[:d]

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    nd = raw_input().split()

    n = int(nd[0])

    d = int(nd[1])

    a = map(int, raw_input().rstrip().split())

    result = rotLeft(a, d)

    fptr.write(' '.join(map(str, result)))
    fptr.write('\n')

    fptr.close()

Short Problem Definition:

Maria plays college basketball and wants to go pro. Each season she maintains a record of her play. She tabulates the number of times she breaks her season record for most points and least points in a game. Points scored in the first game establish her record for the season, and she begins counting from there.

Link

Breaking The Records

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

Just track the min and max.

Solution:

#!/bin/python

import sys

def getRecord(s):
    min_ele = s[0]
    max_ele = s[0]
    min_cnt = 0
    max_cnt = 0
    
    for ele in s:
        if ele > max_ele:
            max_ele = ele
            max_cnt += 1
        if ele < min_ele:
            min_ele = ele
            min_cnt += 1
    
    return [max_cnt, min_cnt]
    
n = int(raw_input().strip())
s = map(int, raw_input().strip().split(' '))
result = getRecord(s)
print " ".join(map(str, result))

Short Problem Definition:

You will be given two arrays of integers and asked to determine all integers that satisfy the following two conditions:

1. The elements of the first array are all factors of the integer being considered
2. The integer being considered is a factor of all elements of the second array

Link

Between Two Sets

Complexity:

time complexity is O(A* (N+M))

space complexity is O(1)

Execution:

This challenge could also be solved using the Greatest Common Divisor. Given that the range of values is only [1,100], it is safe to assume that the naive solution will terminate within the time limit.

Solution:

#!/bin/python

import sys

def isValid(a, b, candidate):
    for a_ele in a:
        if candidate % a_ele != 0:
            return False
    for b_ele in b:
        if b_ele % candidate != 0:
            return False
    return True

n,m = raw_input().strip().split(' ')
n,m = [int(n),int(m)]
a = map(int,raw_input().strip().split(' '))
b = map(int,raw_input().strip().split(' '))

cnt = 0
for candidate in xrange(max(a), min(b)+1):
    if isValid(a, b, candidate):
        cnt += 1

print cnt

Short Problem Definition:

The member states of the UN are planning to send 2 people to the moon. They want them to be from different countries. You will be given a list of pairs of astronaut ID’s. Each pair is made of astronauts from the same country. Determine how many pairs of astronauts from different countries they can choose from.

Link

Journey To The Moon

Complexity:

time complexity is O(a(N))

space complexity is O(N)

Execution:

The algorithm has two parts. Part one calculates the size of all countries with the use of Union-Find. Both operations on the data structure take O log-star time. The second part derives the number of all pairs based on country sizes. That algorithm is very similar to Handshakes.

I used the UF implementation from ActiveState. For more cool uses of Union-Find, see WireBurnouts.

Solution:

#!/bin/python

import math
import os
import random
import re
import sys
from collections import defaultdict

class UnionFind:
'''http://code.activestate.com/recipes/215912-union-find-data-structure/'''
    def __init__(self):
        self.num_weights = {}
        self.parent_pointers = {}
        self.num_to_objects = {}
        self.objects_to_num = {}
        self.__repr__ = self.__str__

    def insert_objects(self, objects):
        for object in objects:
            self.find(object);

    def find(self, object):
        if not object in self.objects_to_num:
            obj_num = len(self.objects_to_num)
            self.num_weights[obj_num] = 1
            self.objects_to_num[object] = obj_num
            self.num_to_objects[obj_num] = object
            self.parent_pointers[obj_num] = obj_num
            return object
        stk = [self.objects_to_num[object]]
        par = self.parent_pointers[stk[-1]]
        while par != stk[-1]:
            stk.append(par)
            par = self.parent_pointers[par]
        for i in stk:
            self.parent_pointers[i] = par
        return self.num_to_objects[par]

    def union(self, object1, object2):
        o1p = self.find(object1)
        o2p = self.find(object2)
        if o1p != o2p:
            on1 = self.objects_to_num[o1p]
            on2 = self.objects_to_num[o2p]
            w1 = self.num_weights[on1]
            w2 = self.num_weights[on2]
            if w1 < w2:
                o1p, o2p, on1, on2, w1, w2 = o2p, o1p, on2, on1, w2, w1
            self.num_weights[on1] = w1+w2
            del self.num_weights[on2]
            self.parent_pointers[on2] = on1

# Complete the journeyToMoon function below.
def journeyToMoon(n, astronauts):
    # generate disjoint sets
    uf = UnionFind()
    uf.insert_objects(xrange(n))

    for astronaut in astronauts:
        uf.union(astronaut[0], astronaut[1])

    # calculate sizes of countries
    country_sizes = defaultdict(int)
    for i in xrange(n):
        country_sizes[uf.find(i)] += 1

    # calculate number of viable pairs
    sm = 0
    result = 0
    for size in country_sizes.values():
        result += sm*size;
        sm += size; 

    return result

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    np = raw_input().split()

    n = int(np[0])

    p = int(np[1])

    astronaut = []

    for _ in xrange(p):
        astronaut.append(map(int, raw_input().rstrip().split()))

    result = journeyToMoon(n, astronaut)

    fptr.write(str(result) + '\n')

    fptr.close()

Short Problem Definition:

Sam’s house has an apple tree and an orange tree that yield an abundance of fruit. In the diagram below, the red region denotes his house, where s is the start point, and i is the endpoint. The apple tree is to the left of his house, and the orange tree is to its right. You can assume the trees are located on a single point, where the apple tree is at point a, and the orange tree is at point b.

Link

Apple And Orange

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

Follow the problem specification.

Solution:

def solve(house_left, house_right, tree, elements):
    cnt = 0
    for ele in elements:
        if tree+ele >= house_left and tree+ele <= house_right:
           cnt += 1
    return cnt

Short Problem Definition:

HackerLand University has the following grading policy:

• Every student receives a grade in the inclusive range from 0 to 100.
• Any grade less than 40 is a failing grade.

Link

Grading Students

Complexity:

time complexity is O(N)

space complexity is O(N)

Execution:

Follow the problem specification. The solution could be further optimized to remove all unnecessary copies and the whole res array.

Solution:

#!/bin/python

from __future__ import print_function

import os
import sys

#
# Complete the gradingStudents function below.
#
def gradingStudents(grades):
    res = []
    for grade in grades:
        if grade >= 38 and grade % 5 >= 3:
            grade = grade + 5 - (grade % 5)
        res.append(grade)
    return res

if __name__ == '__main__':
    f = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(raw_input())

    grades = []

    for _ in xrange(n):
        grades_item = int(raw_input())
        grades.append(grades_item)

    result = gradingStudents(grades)

    f.write('\n'.join(map(str, result)))
    f.write('\n')

    f.close()

Short Problem Definition:

Given five positive integers, find the minimum and maximum values that can be calculated by summing exactly four of the five integers. Then print the respective minimum and maximum values as a single line of two space-separated long integers.

Link

Mini-Max Sum

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

Rather than recalculating the sum every time, keep track of the minimal element and maximal element. The result is the overall sum minus the min/max element.

Note: The editorial claims that the task is O(1), but I disagree. It is O(N).

Solution:

#!/bin/python

import math
import os
import random
import re
import sys

# Complete the miniMaxSum function below.
def miniMaxSum(arr):
    min_ele = sys.maxint
    max_ele = 0
    arr_sum = 0

    for val in arr:
        min_ele = min(min_ele, val)
        max_ele = max(max_ele, val)
        arr_sum += val
    
    return arr_sum-max_ele, arr_sum-min_ele


if __name__ == '__main__':
    arr = map(int, raw_input().rstrip().split())

    print " ".join(map(str, miniMaxSum(arr)))

Short Problem Definition:

You are in charge of the cake for your niece’s birthday and have decided the cake will have one candle for each year of her total age. When she blows out the candles, she’ll only be able to blow out the tallest ones. Your task is to find out how many candles she can successfully blow out.

Link

Birthday Cake Candles

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

Keep track of the tallest one along with the count.

Solution:

#!/bin/python

import sys

n = int(raw_input().strip())
height = map(int,raw_input().strip().split(' '))

cnt = 0
running_top = 0
for candle in height:
    if (candle > running_top):
        cnt = 1
        running_top = candle
    elif candle == running_top:
        cnt += 1
        
print cnt