DEV Community: hackem

Meta Hacker Cup - Questions A, B1, C1

hackem — Wed, 31 Aug 2022 03:40:38 +0000

Since the explanations on the official website are sufficiently clear, I will post only the code solutions without any conceptual origination.

A: Second Hands

import sys

sys.stdin = open('second_hands_input.txt', 'r')

C = int(sys.stdin.readline())
res =[]
for i in range(C):
    arr = [int(x) for x in sys.stdin.readline().split()]
    N, T = arr[0], arr[1]
    S = [int(x) for x in sys.stdin.readline().split()]
    if N > (T*2):
        res.append(False)
        continue
    more_than_twice = False
    hist = {}
    for el in S:
       if el in hist:
           hist[el] += 1
       else:
           hist[el] = 1
       if hist[el] > 2:
           more_than_twice = True
           break
    res.append(not(more_than_twice))
    print(res)
sys.stdout = open('output.txt', 'w')
for i in range(C):
    if res[i]:
        sys.stdout.write(f'Case #{i+1}: YES')
        if i<C-1:
            sys.stdout.write('\n')
    else:
        sys.stdout.write(f'Case #{i+1}: NO')
        if i<C-1:
            sys.stdout.write('\n')

B1: Second Friend

import sys
sys.stdin = open('second_friend_input.txt', 'r')
sys.stdout = open('output.txt', 'w')
N = int(sys.stdin.readline())
for n in range(N):
    sudo = [int(x) for x in sys .stdin.readline().split()]
    R, C = sudo[0], sudo[1]
    tree_present = False
    for r in range(R):
        arr = list(sys.stdin.readline())
        for c in range(C):
            if arr[c] == '^':
                tree_present = True
                break
    if tree_present:
        if (R<2) or (C<2):
            sys.stdout.write(f'Case #{n+1}: Impossible')
            sys.stdout.write('\n')
        else:
            sys.stdout.write(f'Case #{n+1}: Possible')
            for i in range(R):
                sys.stdout.write('\n')
                for i in range(C):
                    sys.stdout.write('^')
            sys.stdout.write('\n')

    else:
        sys.stdout.write(f'Case #{n+1}: Possible')
        for i in range(R):
                sys.stdout.write('\n')
                for i in range(C):
                    sys.stdout.write('.')
        sys.stdout.write('\n')

C1: Second Meaning

import sys
sys.stdin = open('second_meaning_input.txt', 'r')
sys.stdout = open('output_final.txt', 'w')
T = int(sys.stdin.readline())
for t in range(T):
    res = []
    N = int(sys.stdin.readline())
    c = sys.stdin.readline()
    sys.stdout.write(f'Case #{t+1}:')
    sys.stdout.write('\n')
    first_code = c[0]
    if first_code == '.':
        for n in range(N-1):
            c = '-' + c
            sys.stdout.write(f'{c}')
    else:
        for n in range(N-1):
            c = '.' + c
            sys.stdout.write(f'{c}')

Remarks

These were the questions I did for the qualification rounds. Will try to upload the other question solutions before the next round commences for practice sake.

Word Break

hackem — Mon, 15 Aug 2022 15:03:30 +0000

Problem Description

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example:
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example:
Input: s = "catsandog", wordDict =["cats","dog","sand","and","cat"]
Output: false

Concept

It is rather straightforward or 'human-like' to brute force this problem. To segment s, we simply check if we can create a joint of words in wordDict to create s. A simple approach would be to check whether for each segment in s there is a match in wordDict. If the segment is a match, it also has to have a connected path of matched segments until the end of s . Example: It is not enough that 'cats' and 'and' (from wordDict) are matches in 'catsandog' if we do not find a match for segment 'og'.

A dynamic programming solution is applicable here as we are creating a new subproblem each time we find a segment matching in s, the subproblem is s minus the matched segment. Our base case being an empty s.

I did a recursive approach by starting from the beginning of s. The function then breaks off into all subproblems created by all matchings in s and returns True if one subproblem reaches an empty s, i.e. all parts of s matched. I tried this solution however I got a Time Limit Exceeded. I then chanced upon a clever trick in the leetcode discussions section to save computational time.

For this solution, we create a dp array for all indices of s plus one for the base case. Set all value of the array to False except our base case. Then we iterate from the end of s checking for each element whether it is a match and whether that match is connected to the end by checking dp[i + len(matched_word)]. The advantage of this method is that we save computational time by caching our results.

Implementation

My initial solution, recursion

class Solution:
    def wordBreak(self,s, wordDict, i=0):
        res = []
        for w in wordDict:
            if (i+len(w))<=len(s) and (s[i:i+len(w)]==w):
                if i+len(w) == len(s): return True
                else:
                    res.append(self.wordBreak(s[i+len(w):],wordDict))
        if True in res:
            return True
        return False

The bottom-up dp caching solution

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [False] * (len(s) + 1)
        dp[len(s)] = True
        for i in range(len(s)-1,-1,-1):
            for w in wordDict:
                if ((i+len(w))<=len(s)) and (s[i:i+len(w)]==w):
                    dp[i] = dp[i+len(w)]
                if dp[i]:
                    break
        return dp[0]

Remarks

This problem appeared uncomplicated but had an interesting elusiveness that made it different from other dp problems. The solutions remind us to consider computational time beyond just time complexity. Both solutions were

O(n^2*m)

where n is the length of s and m the length of wordDict. Yet, only the caching solution was accepted. Remarkception, still trying to figure out dev.to's mathematical text support, currently using katex.

Longest Increasing Subsequence

hackem — Sat, 13 Aug 2022 15:48:06 +0000

Problem Description

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Concept

A brute force method is applied by simply making all possible increasing subsequences from the zeroth index then keeping all of them in memory and eventually returning the longest among the candidate lists. This approach has an O(n^2) time complexity where n is the length of the array. This is due to n number of permutations from the zeroth index with each permutation requiring at worst n number of checks (to form the subsequence).

From the brute force method it is obvious that there are potential improvements if we take into account that we want to keep the elements in the subsequence as small as we can before we increment another element. For example: we would obviously discard the 3 in [0,3] for our next element if it is smaller than 3 as it increases the range of numbers we can get for our next larger element, i.e., [0,1] is better than [0,3]. If we apply the same concept not only to the last number in our current subsequence but to all the numbers in the subsequence we will then be able to increase the range of possible numbers in all positions in the subsequence. Hence, we will be creating and maintaining the longest increasing subsequence throughout the loop. Our algorithm would work like so: 1. If the next element is larger than the last element in our subsequence, append it to subsequence. 2. Else, find the biggest number in the subsequence the element can replace such that the number is smaller than the element and replacing the number with the element maintains the incremental condition of the subsequence. I know this sounds confusing, the example will illustrate the concept better.

Notice a couple of things from this example. Firstly, the final longest increasing subsequence is not an existent valid subsequence in nums. Fortunately, the problem requires only to return the length of the subsequence. Secondly, we guarantee the past existence of a valid subsequence after we substituted an element in the subsequence with the next element so long as the next element is smaller than the past element. Example: The 5th iteration produces subsequence [1,2,6] although this is not derivable from nums, we certainly know such a a valid subsequence existed, [4,5,6] from the third iteration. Hence, it also stands to reason that the existence of [1,2,6,7,8], a non-existent subsequence, guaranteed a past valid subsequence that fulfils our condition of incrementation, in this example is [4,5,6,7,8]. These two observations show us that the algorithm does not produce false subsequences. To illustrate the power of the algorithm see the following example.

Notice that by finding the smallest possible number to occupy each index we are maximising the range of numbers we can find. Although we could have created the longest increasing subsequence similarly by our elements in the 3rd iteration, [4,5,6], by minimising the elements such as in the 6th iteration we increase the potential of our subsequence as the next element needs to only be bigger than 3, not 6. Understand that we can only place 3 at the 6th iteration because the element before 3 is 2 and not 5, highlighting the importance of minimising the number in all indices due to the domino effect.

The algorithm keeps a current longest increasing subsequence at each iteration and iterates once throughout the list. To find the position of our next element in the current subsequence we do a binary search. Hence, the time complexity of the algorithm is O(n*log(n)).

Implementation

We create a variable tmp to keep track of the current longest increasing subsequence. We then loop over each element in nums. In each iteration we check whether, upon insertion, the element will be the largest element or not. This check is done by bisect_left which accept the sorted list tmp and a number x and returns the position x occupies in tmp so that tmp maintains sorted. The function bisect_left uses a binary search. If the element is the biggest then bisect_left will return the last index of the newly appended a which is which is equals to len(temp). As we established, if the element, n, is the biggest we append it, else, we find the smallest element that is bigger than n in tmp and replace it with n, bisect_left returns the index to be replaced. Finally we return the variable.

def lengthOfLIS(self, nums: List[int]) -> int:
        N = len(nums)
        tmp = [nums[0]]
        for n in nums:
            x = bisect_left(tmp,n)
            if x == len(tmp):
                tmp.append(n)
            else:
                tmp[x] = n
        return len(tmp)

Real-life application of the Longest Increasing Subsequence Algorithm

Part of Maximum Unique Match Finder for aligning entire genomes.

Remarks

Surprisingly, the algorithm to find the longest increasing subsequence, not merely its length, also has a time complexity of O(n*log(n)). The algorithm is inspired by the card game Patience or Klondike. Here's a great resource to learn about Patience Sort. Funnily enough, during my Police Officer Basic Course I sat beside my friend who would play Klondike throughout class, it was one of the few games available on our issued laptops.