Algorithm Problem Sets

Posted on January 1, 2013
Tags: algorithms

1 python vs C++ in CSES

a, goal = list(map(int, input().split()))
choice  = list(map(int, input().split()))

DP = [-1 for i in range(goal+1000000)]
DP[0] = 0
maxj = max(choice)
for i in choice:
    DP[i] = 1
k = 0
while k <= goal:
    for j in choice:
        if k+j > goal:
            choice.remove(j)
            pass
        if DP[k] >= 0:
            if DP[k+j] >= 0:
                DP[k+j] = min(DP[k+j],DP[k]+1)
            else:
                DP[k + j] = DP[k]+1
    k = k + 1
print(DP[goal])

#include <bits/stdc++.h>

int main(){
int DP[1000100];
    DP[0]=0;
    for(int i = 0; i < 1000101; i++){
        DP[i] = -1;
    }
    int TC, goal;
    std::vector<int> choice;
    scanf("%d %d",&TC,&goal);
    // std::cout<< TC<< goal << "\n";
    while (TC--){
        int tmp;
        scanf("%d",&tmp);
        choice.push_back(tmp);
    }
    for(int j : choice){
        DP[j] = 1;
    }
    int k = 0;
    while(k < goal){
        for(int j : choice){
            // std::cout << j;
            if (DP[k] >= 0 && k + j <= goal){
                if(DP[k+j] >= 0){
                    DP[k+j] = std::min(DP[k+j],DP[k]+1);
                }else{
                    DP[k+j]=DP[k]+1;
                }
            }
        }
        k = k+1;
    }
    // for(int i = 0; i < 13; i++){
    //     std::cout << DP[i] << " ";
    // }
    std::cout <<DP[goal] << "\n";
   
}
//g++ shit.cpp && ./a.out

2 Documenting some random algorithmic problems:

Describe an algorithm that given a linked list,
if odd returns the middle element,
if even length then return the first of the two middle elements.

Design recursive procedure that takes n::int and returns ALL n-length lists where all consecutive letters are distinct. Only letters {A,B,C} can be used.
Eg. ‘AB’ ‘AC’ ‘BA’ ‘BC’ ‘CA’ ‘CB’

Misconception:

4-pole Hanoi. Given 4 poles A,B,C,D clockwise in a square, you can only move clock wise. Design a method to move n::int disk from A to B.

A–B
|   |
D–C

Take Tree T as an input. For every node C, output the shortest path from C to the closest leaf.

3 TwoSum

#Psuedocode
Goal: Return INDEX of nums that sum to target

nums = [2,7,11,15]
hmap = {Value#1stpartialSum |-> Index#2ndpartialSum} 
also   {Value#2ndpartialSum |-> Index#1stpartialSum}
     where Invariant is Value#1stpartialSum + Value#2ndPartialSum = target
let nums = Value#1stpartialSum
enumerate(nums) = {index |-> nums} where i::index, k::Value#1stpartialSum
check k::Value#1stpartialSum in hmap
    true => return [hmap(k)::Index#2ndpartialSum, (index of k::Value#1stpartialSum)::Index#1ndpartialSum
    false => SET hmap[target - Value#1stpartialSum |-> Index#2ndpartialSum]
class Solution(object):
    def twoSum(self, nums, target):
        hmap = {}
        for Index1stPartial,Value1stPartial in enumerate(nums):
            if Value1stPartial in hmap:
                Index2ndPartial=hmap[Value1stPartial]
                return [Index2ndPartial,Index1stPartial]
            Value2ndPartial = target-Value1stPartial
            hmap[Value2ndPartial] = Index1stPartial
        return []

#Test = Solution().twoSum([2,7,11,15],9)
#print(Test)
func twoSum(nums []int, target int) []int {
	hmap := make(map[int]int)
	for Index1stPartial, Value1stPartial := range nums {
		if _, exists := hmap[Value1stPartial]; exists {
			Index2ndPartial := hmap[Value1stPartial]
			return []int{Index2ndPartial, Index1stPartial}
		} else {
			Value2ndPartial := target - Value1stPartial
			hmap[Value2ndPartial] = Index1stPartial
		}

	}
	return []int{}
}

2 cases:

Hashmap Miss

Hashmap hit