CF Problem Sets

Posted on January 1, 2013

Tags: algorithms

1 Template

2 IO

2.1 Trivial

a, b = list(map(int, input().split()))
print(a+b)

package main
import("fmt")
func main(){
    var a int 
    var b int 
    fmt.Scanf("%d %d", &a, &b)
}

#include <bits/stdc++.h>
using namespace std;
int main() {
    int a,b;
    scanf("%d %d",&a,&b);
}

2.2 Input list

4 100
93 48 59 2

int TC, goal;
std::vector<int> choice;
scanf("%d %d",&TC,&goal);
while (TC--){
    int tmp;
    scanf("%d",&tmp);
    choice.push_back(tmp);
}
//TC is 4
//goal is 100
//choice is vector {93,48,59,2}

2.3 Input w/ TC count

TC is Number of test cases given for us to process.

3                           <--IN  TC 
1 5                         <--IN
sum: 6                      <--OUT
3 6                         <--IN
sum: 9                     <--OUT
4 8                         <--IN
sum: 12                     <--OUT

TC = int(input())
for i in range(TC):
    a, b = list(map(int, input().split()))
    print(a+b)

package main
import("fmt")
func main(){
    var TC int
    fmt.Scanln(&TC)
    for i := 0; i < TC; i++ {
        var a int
        var b int 
        fmt.Scanf("%d %d",&a,&b)
        fmt.Printf("%d\n",a+b)
    }
}

#include <bits/stdc++.h>
using namespace std;
int main() {
int TC;
scanf("%d", &TC);
while (TC--){
    int a,b; 
    scanf("%d %d",&a,&b);
    printf("%d\n" a+b);
}

2.4 Input w/o TC count

we arent given the count so we process input until we stop

while True:
    try:
        a, b = list(map(int, input().split()))
    except:
        break 
    print(a+b)

package main
import("fmt")
func main(){
    var a int 
    var b int 
    for {
        n, err := fmt.Scanf("%d %d", &a, &b)
        fmt.Printf("%d\n",a+b)
        if n == 0 || err != nil { break }
    }
}

#include <bits/stdc++.h>
using namespace std;
int main() {
int a,b; 
while (scanf("%d %d", &a, &b) != 0){
    printf("%d\n", a+b);
}
//terminates when you input `/0`

2.5 Input w/ different sizes

2.6 File

INPUT    OUTPUT
3      | 6
1 5    | 14
5 9    | 10
7 3    |

#include <bits/stdc++.h>
using namespace std;

int main() {
  // comment all lines and only uncomment demo code that you are interested with
  
  freopen("IO_in1.txt", "r", stdin);
  int TC;
  scanf("%d", &TC); // number of test cases
  while (TC--) { // shortcut to repeat until 0
    int a, b; scanf("%d %d", &a, &b);
    printf("%d\n", a+b); // compute on the fly
  }
  return 0;
}

3 Create File and Read File

For Golang:

fmt.Scanln() to read input into different KNOWN variables
bufio.Reader to read full line w/ newline char
bufio.Scanner to read full line w/o newline char

package main

import (
    "fmt"
    "log"
    "os"
)

func main() {
    content, err := os.ReadFile("file.txt")
    if err != nil {
        log.Fatal(err)
    }
    fmt.Println(string(content))
}

package main

import (
    "fmt"
    "io"
    "os"
)

func main() {
	f,_ := os.Create("shit.txt")
	defer f.Close()
	io.Copy(f,"AHHH")
    }

4 Data Structures

4.1 LinkedList - ProductType

Product types are structs/records

struct linkedlist {
    int val;
    struct linkedlist* next;
};

void printList(struct linkedlist* head){
    while((*head).next != NULL ){
        printf("%d\n",(*head).val);
        head = (*head).next;
    }
    printf("%d\n",(*head).val); //print last
}

int main(){
    struct linkedlist a;
    struct linkedlist b;
    struct linkedlist c;
    a.val = 5;
    b.val = 2;
    c.val = 9;
    a.next = &b;
    b.next = &c;
    c.next = NULL;
    printList(&a);
}

#include <bits/stdc++.h>

using namespace std;

struct LinkedList {
    int x = 0;
    LinkedList* next;
};


int main(){
    std::cout << "hi";
    struct LinkedList x ;
    struct LinkedList a, b, c ;
    x->next = &a;

    std::cout << x.x;
    return 0;
}

package main
import(
	"fmt"
)

type LinkedList[T any] struct {
    Data T
    Next *LinkedList[T]
}

func (e *LinkedList[T]) Append(data T) *LinkedList[T] {
    if e.Next == nil {
        e.Next = &LinkedList[T]{data, nil}
    } else {
        tmp := &LinkedList[T]{data, e.Next}
        e.Next = tmp
    }
    return e.Next
}

func (e *LinkedList[T]) String() string {
    return fmt.Sprintf("LinkedList: %v", e.Data)
}

func main(){
	var b LinkedList[int]
	b.Data = 4
	fmt.Println(b.String())
}

class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = None
a = ListNode(val=2)
a.next = ListNode(val=5)
a.next.next = ListNode(val=9)

4.2 Adjacency list

a = [[1,3],[3,4],[2],[5],[],[3]]

b =  [[0 for col in range(0,len(a))] for row in range(0,len(a))]

class Node:
    def __init__(self,data):
        self.children = []
        self.data = data
    def printout(self):
        print(self.data)


def adjToMat(adj,mat):
    for row,adjlist in enumerate(adj):
        for col in adjlist:
           mat[row][col] = 1 
    return mat

c = adjToMat(a,b)

def prettyMat(x):
    colLabel = "  ".join([str(i) for i in range(0,len(x))])
    print(f"   {colLabel}")
    for row,i in enumerate(x):
        print(f"{row} {i}")
prettyMat(c)

#    0  1  2  3  4  5
# 0 [0, 1, 0, 1, 0, 0]
# 1 [0, 0, 0, 1, 1, 0]
# 2 [0, 0, 1, 0, 0, 0]
# 3 [0, 0, 0, 0, 0, 1]
# 4 [0, 0, 0, 0, 0, 0]
# 5 [0, 0, 0, 1, 0, 0]

5 Codeforces

5.1 698A - DP

nil = input()
a = [int(x) for x in input().split()]
n = len(a)

dp = [[999999 for x in range(0,3)] for y in range(0,n)]

REST = 0
GYM = 1
CODE = 2

NO_CODEGYM = 0
NO_GYM = 1
NO_CODE = 2
YES_BOTH = 3

def basecase():
    dp[0][REST] = 1
    if a[0] == NO_GYM or a[0] == YES_BOTH:
        dp[0][CODE] = 0
    if a[0] == NO_CODE or a[0] == YES_BOTH:
        dp[0][GYM] = 0

def restPrev(i):
    restVal =dp[i-1][REST]
    gymVal = dp[i-1][GYM]
    codeVal = dp[i-1][CODE]
    return 1 + min([restVal,gymVal,codeVal]) 
def codePrev(i):
    restVal =dp[i-1][REST]
    codeVal = dp[i-1][CODE]
    return min([restVal,codeVal])
def gymPrev(i):
    restVal =dp[i-1][REST]
    gymVal = dp[i-1][GYM]
    return min([restVal,gymVal])

def lastday(i):
    restVal =dp[i-1][REST]
    gymVal = dp[i-1][GYM]
    codeVal = dp[i-1][CODE]
    return min([restVal,gymVal,codeVal])

basecase()
# print(dp)
for k in range(1,n):
    #print(dp[k])
    if a[k] == NO_CODEGYM:
        dp[k][REST] = restPrev(k)
    if a[k] == NO_CODE:
        dp[k][REST] = restPrev(k)#optimal(rest) today is based on optimal(rest) yesterday
        dp[k][GYM] = codePrev(k)#optimal(gym) today is based on optimal(code) yesterday
    if a[k] == NO_GYM:
        dp[k][REST] = restPrev(k)#optimal(rest) today is based on optimal(rest) yesterday
        dp[k][CODE] = gymPrev(k)#optimal(code) today is based on optimal(gym) yesterday
    if a[k] == YES_BOTH:
        dp[k][REST] = restPrev(k)
        dp[k][CODE] = gymPrev(k)
        dp[k][GYM] = codePrev(k)
        

print(lastday(n))

5.2 Takeaway

Initialize all value in dp as INF or unoptimal
look at the code, how does it account for rejecting 2 consecutive days?
- Notice that (gym) –depends–> (gym yesterday) BUT Optimal(gym) –depends–> (Optimal(rest) yesterday,Optimal(code) yesterday)

\[gym \overset{depends}{\rightarrow} gym_yesterday \tag{Red Herring}\] \[Optimal(gym) \overset{depends}{\rightarrow} (Optimal(code_yesterday),Optimal(rest_yesterday)) \tag{Correct}\]

Think about constraint WRT TO OPTIMALITY, not the action itself

6 YeetCode

6.1 LC91 Decoding

Question, How many ways we can decode the string with each word being either 1 or 2 letters.

Lesson: How many ways = COUNT # paths in DFS from root to leaf. We can always cache memoize DFS.

"""
either terminate 1-next or terminate 2-next
(1|13..) or (11|3..)
ConstraintA: Reject 2-next when > "26"
ConstraintB: When 2-next is "0", must ONLY terminate 2-next NOT 
(1|03) BAD
(10|3) GOOD

DFS, pruning bad decisions

2 possible cases

(..10) 
(..04) if there is a 0 we must take it
"""
class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        
        def dfs(s):
            if len(s) == 0:
                return 1
            if len(s) == 1:
                if s == "0":
                    return 0
                return 1
            take1 = s[:1]
            rest1 = s[1:]
            take2 = s[:2]
            rest2 = s[2:]
            if take2[0] == "0":
                return 0
            if int(take2) > 26:
                return dfs(rest1) + 0
            if take1 == "0":
                return 0
            else:
                return dfs(rest1) + dfs(rest2)

        return dfs(s)
        #TLE but correct


"""
either terminate 1-next or terminate 2-next
(1|13..) or (11|3..)
ConstraintA: Reject 2-next when > "26"
ConstraintB: When 2-next is "0", must ONLY terminate 2-next NOT 
(1|03) BAD
(10|3) GOOD
ConstraintC: Reject 1-next when "0". This is no map from a single "0".

DFS, pruning bad decisions

2 possible cases

(..10) 
(..04) if there is a 0 we must take it
"""
class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        def cache(func):
            cache_ = {}
            def wrapper(*args):
                try:
                    return cache_[args]
                except:
                    cache_[args] = func(*args)
                    return cache_[args]
            return wrapper
        @cache      
        def dfs(s):
            if len(s) == 0:
                return 1
            if len(s) == 1:
                if s == "0":
                    return 0
                return 1
            take1 = s[:1]
            rest1 = s[1:]
            take2 = s[:2]
            rest2 = s[2:]
            if take2[0] == "0":
                return 0
            if int(take2) > 26:
                return dfs(rest1) + 0
            if take1 == "0":
                return 0
            else:
                return dfs(rest1) + dfs(rest2)

        return dfs(s)
        #SUCCESS due to cache memo


class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        memo = {}
        def dfs(s):
            if len(s) == 0:
                return 1
            if len(s) == 1:
                if s == "0":
                    return 0
                return 1
            take1 = s[:1]
            rest1 = s[1:]
            take2 = s[:2]
            rest2 = s[2:]
            if take2[0] == "0":
                return 0
            if int(take2) > 26:
                dfsOUT1 = -999
                if rest1 in memo:
                    dfsOUT1= memo[rest1] + 0
                else:
                    memo[rest1] = dfs(rest1)
                    dfsOUT1 = memo[rest1] + 0
                return dfsOUT1
            if take1 == "0":
                return 0
            else:
                dfsOUT1 = -999
                dfsOUT2 = -999
                if rest1 in memo:
                    dfsOUT1 = memo[rest1]
                else:
                    memo[rest1] = dfs(rest1)
                    dfsOUT1 = memo[rest1]
                if rest2 in memo:
                    dfsOUT2 = memo[rest2]
                else:
                    memo[rest2] = dfs(rest2)
                    dfsOUT2 = memo[rest2]
                return dfsOUT1 + dfsOUT2
                    
                #return dfs(rest1) + dfs(rest2)

        return dfs(s)
        #Even faster than decorator memo for somereason

using std::string;
string tail(string mystr){
    return mystr.substr(1);
}

int minDistanceR(string word1, string word2){
    if(word2.size() == 0){
        return word1.size();
    }
    if(word1.size() == 0){
        return word2.size();
    }
    string tail1 = tail(word1);
    string tail2 = tail(word2);
    string head1 = string(1,word1[0]);
    string head2 = string(1,word2[0]);
    if (head1 == head2){
        int cost = 0;
        int opt_Match = cost + minDistanceR(tail1,tail2); 
        return opt_Match;
    }
    if (head1 != head2){
        int cost = 1;
        int opt_Insert = cost + minDistanceR(word1,tail2);
        int opt_Del = cost + minDistanceR(tail1,word2);
        int opt_Subst = cost + minDistanceR(tail1,tail2);
        return std::min(opt_Subst,std::min(opt_Insert,opt_Del));

    }
    return 0;
}

6.2 LC1299

Replace Elements with Greatest Element on Right Side

class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        rMax = -1
        for i in range(len(arr) - 1, -1, -1):
            newMax = max(rMax,arr[i])
            arr[i] = rMax
            rMax = newMax
        return arr


impl Solution {
    pub fn replace_elements(arr: Vec<i32>) -> Vec<i32> {
        let mut rMax = -1;
        let mut arrT = arr;
        for i in (0..arrT.len()).rev(){
            let mut newMax = std::cmp::max(rMax, arrT[i]);
            arrT[i] = rMax;
            rMax = newMax;
        }
        return arrT
    }
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
func replaceElements(arr []int) []int {
    var rMax int
    rMax = -1
    for i := len(arr)-1; i > -1; i-- {
        newMax := max(rMax,arr[i])
        arr[i] = rMax
        rMax = newMax
        }
    return arr
}

function replaceElements(arr: number[]): number[] {
    let rMax: number = -1
    for (let i: number = arr.length-1; i > -1; i--){
        let newMax: number = Math.max(rMax,arr[i])
        arr[i] = rMax
        rMax = newMax
    }
    return arr
};

7 UVA

7.1 495 fib

To return arrays in C++, you must return pointer
all function local var are destroyed in C++ unlike python or JS.
- This means you cant initialize an array in a function and hope to return it for use in main

int* fib(int dp[]){
    dp[0] = 1;
    dp[1] = 1;
    for(int i = 2; i < 5001; i++){
        dp[i] = dp[i-1]+dp[i-2];
    }
    return dp;
}

using std::cin;

int main(){
    int dp[5001];
    fib(dp);
    print(dp[4]);
    int n;
    while(cin >> n){
        print(dp[n]);
    }

}

8 Fr

8.1 Closest values in list

def closestvalues(L): 
    L.sort()
    valmin,argmin = min(((L[i]-L[i-1]),i) for i in range(1,len(L)))
    return L[argmin-1],L[argmin]
print(closestvalues([6,4,8,7,3,5]))

8.2 Counting sort

sort using O(n) by throwing stuff at an ordered hashmap

def countingsort(L):
    mymax = max(L)
    mydic = {}
    for i in range(0,mymax+1):
        mydic[i] = 0  
    for j in L:
        mydic[j] = mydic[j] + 1
    output = []
    for k,v in mydic.items():
        for c in range(0,v):
            output.append(k)
    return output
print(countingsort([1,7,6,7,84,35,5]))

Given a list of intervals, find a point that is included in max # of intervals.

def maxinterval(S):
    bounds = [(left,+1) for (left,right) in S] + [(right,-1) for (left,right) in S]
    bounds.sort(key=lambda x: x[0])
    partSol = 0
    best = (partSol, None)
    for (startbound,energy) in bounds:
        partSol += energy
        if best[0] < partSol:
            best = (partSol,startbound)
    return best 
print(maxinterval([(1,5),(3,6),(5,8),(6,9),(5,10)]))