Short Problem Definition:

You wish to buy video games from the famous online video game store Mist.

Usually, all games are sold at the same price, p dollars. However, they are planning to have the seasonal Halloween Sale next month in which you can buy games at a cheaper price. Specifically, the first game you buy during the sale will be sold at dollars, but every subsequent game you buy will be sold at exactly d dollars less than the cost of the previous one you bought. This will continue until the cost becomes less than or equal to m dollars, after which every game you buy will cost m dollars each.

Link

Halloween Sale

Complexity:

time complexity is O(1)

space complexity is O(1)

Execution:

The solution is based on the Arithmetic Progression. It makes it a bit more complex due to the floor m.

Another option is either a while loop or a recursion.

Solution:

// Complete the howManyGames function below.
int howManyGames(int p, int d, int m, int s) {
    int n=floor( (p-m)/d +1);
    if( (n*(2*p-(n-1)*d))/2 <= s)
    {
        return n + (s-(n*(2*p-(n-1)*d)/2))/m;
    }
    else
    {
        return floor(((-d-2*p)+sqrt((-2*p-d)*(-2*p-d)-(8*d*s)))/(-2*d));
    }
}

Short Problem Definition:

Given the time in numerals we may convert it into words.

Link

The Time In Words

Complexity:

time complexity is O(?)

space complexity is O(?)

Execution:

I might have hinted at my opinion in the past: Why do “challenges” like this even exist? It requires 0 brain power, but you will spend an hour figuring out the fine details of English and fixing bugs.

Solution:

#!/bin/python

import math
import os
import random
import re
import sys

# Complete the timeInWords function below.
def timeInWords(h, m):
    raise RuntimeError("Nope!")

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

    h = int(raw_input())

    m = int(raw_input())

    result = timeInWords(h, m)

    fptr.write(result + '\n')

    fptr.close()

Short Problem Definition:

Happy Ladybugs is a board game having the following properties:

• A ladybug is happy only when it’s left or right adjacent cell (i.e., ) b[i+/-1] is occupied by another ladybug having the same color.

Link

Happy Ladybugs

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

This challenge definition does not require a full sort. It only wants to know whether the array is sortable. Therefore we will assume that if there is at least one free slot, the array is sortable by color.

Further we will assume that each ladybug wants to have at least one neighbor with the same color. If there are two of the same color, the ladybug is happy.

If there is no empty space, the input array needs to be sorted correctly.

Solution:

#!/bin/python

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

# Complete the happyLadybugs function below.
def happyLadybugs(b):
    counter = Counter(b)
    for key, value in counter.items():
        if key != "_" and value == 1:
            return "NO"
    
    if "_" in b:
        return "YES"

    for idx in xrange(1, len(b)):
        if b[idx] == b[idx-1] or b[idx] == b[idx+1]:
            continue
        else:
            return "NO"
        
    return "YES"
    
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    g = int(raw_input())

    for g_itr in xrange(g):
        n = int(raw_input())

        b = raw_input()

        result = happyLadybugs(b)

        fptr.write(result + '\n')

    fptr.close()

Short Problem Definition:

We define P to be a permutation of the first n natural numbers in the range
[1,n]. Let pos[i] denote the value at position i in permutation P using 1-based indexing.

P is considered to be an absolute permutation if |pos[i]-i| = K holds true for every i.

Link

Absolute Permutation

Complexity:

time complexity is O(N)

space complexity is O(N)

Execution:

The time complexity of this solution is a question as is always true with hash maps. It is either O(N), O(NlogN) or O(N^2) depending on your particular implementation and hash algorithm.

After I solved this, I looked at the editorial and was amazed by the complex algorithm that they proposed. This is much simpler. Yet I agree that the editorial is more time/space effective.

Iterate over the list of all values [1,N]. Use the lowest available value from the [1,N] pool. Either i-K or i+k, if i-K is not available.

Solution:

#!/bin/python

import math
import os
import random
import re
import sys

# Complete the absolutePermutation function below.
def absolutePermutation(n, k):
    solution = []
    s = set(range(1,n+1))
    
    for pos in xrange(1, n+1):
        if pos-k in s:
            solution.append(pos-k)
            s.remove(pos-k)
        elif pos+k in s:
            solution.append(pos+k)
            s.remove(pos+k)
        else:
            return [-1]
    
    return solution

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

    t = int(raw_input())

    for t_itr in xrange(t):
        nk = raw_input().split()

        n = int(nk[0])

        k = int(nk[1])

        result = absolutePermutation(n, k)

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

    fptr.close()

Short Problem Definition:

Lilah has a string, s, of lowercase English letters that she repeated infinitely many times. Given an integer, n, find and print the number of letters a in the first n letters of Lilah’s infinite string.

For example, if the string s = ‘abcac’ and n = 10, the substring we consider is abcacabcac, the first 10 characters of her infinite string. There are 4 occurrences of a in the substring.

Link

Repeated String

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

As with most simple problems, there are many ways to write the code that can achieve the correct result. I picked the one that seems the simplest and most Pythonesque.

Solution:

#!/bin/python

import math
import os
import random
import re
import sys

# Complete the repeatedString function below.
def repeatedString(s, n):
    n_per_string = s.count('a')
    n_per_substring = s[0:n%len(s)].count('a')
    return n_per_string * (n/len(s)) + n_per_substring

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
    s = raw_input()
    n = int(raw_input())
    result = repeatedString(s, n)
    fptr.write(str(result) + '\n')
    fptr.close()

Short Problem Definition:

Alice is playing an arcade game and wants to climb to the top of the leaderboard and wants to track her ranking. The game uses Dense Ranking, so its leaderboard works like this:

• The player with the highest score is ranked number 1 on the leaderboard.
• Players who have equal scores receive the same ranking number, and the next player(s) receive the immediately following ranking number

Link

Climbing The Leaderboard

Complexity:

time complexity is O(N*log(N))

space complexity is O(1)

Execution:

I am not a fan of the Dense Rank. Standard Competition ranking makes much more sense.

1) In the Dense Rank, duplicates have no impact on the ranking, so they can be safely removed.

2) The array should be sorted. Since the value range is fairly small (10^5), counting sort would improve the theoretical O-notation to O(N).

3) Take advantage of built-in Python functionality. Bisect right finds an insertion point after potential duplicates, giving us the correct Dense Rank.

Solution:

#!/bin/python

import math
import os
import random
import re
import sys
import bisect

# Complete the climbingLeaderboard function below.
def climbingLeaderboard(scores, alice):
    res = []
    s = sorted(list(set(scores)))
    l = len(s)
    for v in alice:
         res.append(l - bisect.bisect_right(s, v) +1)
            
    return res

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
    scores_count = int(raw_input())
    scores = map(int, raw_input().rstrip().split())
    alice_count = int(raw_input())
    alice = map(int, raw_input().rstrip().split())
    result = climbingLeaderboard(scores, alice)
    fptr.write('\n'.join(map(str, result)))
    fptr.write('\n')
    fptr.close()

Short Problem Definition:

Given an array of integers, determine whether the array can be sorted in ascending order using only one of the following operations one time.

1. Swap two elements.
2. Reverse one sub-segment.

Determine whether one, both or neither of the operations will complete the task. If both work, choose swap. For instance, given an array [2, 3, 5, 4] either swap the 4 and 5; or reverse them to sort the array. Choose swap.

Link

Almost Sorted

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

I wrote this code 4 years ago and I already have no clue what it does. It is linear time and it works even today.

Today, I would have broken this logic down into smaller functions with clear purpose.

If you have solved this in a readable way, please share!

Solution:

#!/usr/bin/py
def getReverseAction(arr):
    is_sorted = True
    
    low_idx = 0
    high_idx = len(arr)-1
    
    while (low_idx < high_idx and arr[low_idx] < arr[low_idx+1]):
        low_idx += 1
   
    if low_idx == high_idx:
        print "yes"
        return

    while (high_idx > 0 and arr[high_idx] > arr[high_idx-1]):
        high_idx -= 1

     
    #print "low", low_idx, arr[low_idx]
    #print "high", high_idx, arr[high_idx]
    
    if low_idx == 0 or arr[high_idx] > arr[low_idx -1]:
        #print "high index swapable"
        if arr[high_idx] < arr[low_idx +1] or low_idx+1 == high_idx:
            #print "high index swapable"
            if high_idx == len(arr)-1 or arr[low_idx] < arr[high_idx+1]:
                #print "low index swapable"
                if arr[low_idx] > arr[high_idx -1] or low_idx == high_idx-1:
                    #print "low index swapable"
                    low_idx_runner = low_idx+1
                    while (low_idx_runner < high_idx and arr[low_idx_runner] < arr[low_idx_runner+1]):
                        low_idx_runner += 1
                    if low_idx_runner == high_idx-1 or low_idx == high_idx-1:    
                        print "yes"
                        print "swap", low_idx+1, high_idx+1
                        return
    
    low_idx_runner = low_idx+1
    while (low_idx_runner < high_idx and arr[low_idx_runner] > arr[low_idx_runner+1]):
        low_idx_runner += 1
    
    if low_idx_runner == high_idx:
        if low_idx == 0 or arr[high_idx] > arr[low_idx -1]:
            if high_idx == len(arr)-1 or arr[low_idx] < arr[high_idx+1]:
                print "yes"
                print "reverse", low_idx+1, high_idx+1
                return
    
    print "no"
    
        
if __name__ == '__main__':
    n = input()
    arr = map(int, raw_input().split())
    getReverseAction(arr)