Yong's Blog
0%

Biweekly Contest 30

Posted on Edited on In Views: Valine:

Ranking: 606 / 8175 😔😂😭

Q1. 5177. Reformat Date

Given a date string in the form Day Month Year, where:

Day is in the set {“1st”, “2nd”, “3rd”, “4th”, …, “30th”, “31st”}.
Month is in the set {“Jan”, “Feb”, “Mar”, “Apr”, “May”, “Jun”, “Jul”, “Aug”, “Sep”, “Oct”, “Nov”, “Dec”}.
Year is in the range [1900, 2100].
Convert the date string to the format YYYY-MM-DD, where:

YYYY denotes the 4 digit year.
MM denotes the 2 digit month.
DD denotes the 2 digit day.

Note

Very straight forward. Just do the string conversion.

1
2
3
4
5
6
7
8
class Solution:
    def reformatDate(self, date: str) -> str:
        m_to_idx = ["Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"]
        day, month, year = date.split()
        day, month = day[:-2], str(m_to_idx.index(month)+1)
        if len(day) < 2: day = '0' + day
        if len(month) < 2: month = '0' + month
        return f'{year}-{month}-{day}'

Q2. 5445. Range Sum of Sorted Subarray Sums

Given the array nums consisting of n positive integers. You computed the sum of all non-empty continous subarrays from the array and then sort them in non-decreasing order, creating a new array of n * (n + 1) / 2 numbers.

Return the sum of the numbers from index left to index right (indexed from 1), inclusive, in the new array. Since the answer can be a huge number return it modulo 10^9 + 7.

Note

Use prefix-sum to generate the list of sum of all non-empty continous subarrys.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Time O(N^2) Space O(N^2)
class Solution:
    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
        p_s = [nums[0]]
        for val in nums[1:]:
            p_s.append(p_s[-1]+val)

        arr = []
        for i, v in enumerate(p_s):
            arr.append(v)
            for j in range(i):
                arr.append(v - p_s[j])
        arr = sorted(arr)

        return sum(arr[i] for i in range(left-1, right))

Q3. 5446. Minimum Difference Between Largest and Smallest Value in Three Moves

Given an array nums, you are allowed to choose one element of nums and change it by any value in one move.

Return the minimum difference between the largest and smallest value of nums after perfoming at most 3 moves.

Note

OMG, this problem is killing me! Spent more than 40 minutes here.

This is kind of a brute force solution.
Just try to exhaust it in a nicer way.

1
2
3
def minDifference(self, A):
    A.sort()
    return min(b - a for a, b in zip(A[:4], A[-4:]))

Q4. 5447. Stone Game IV

Alice and Bob take turns playing a game, with Alice starting first.

Initially, there are n stones in a pile. On each player’s turn, that player makes a move consisting of removing any non-zero square number of stones in the pile.

Also, if a player cannot make a move, he/she loses the game.

Given a positive integer n. Return True if and only if Alice wins the game otherwise return False, assuming both players play optimally

Note

  1. Typical 1-D DP
  2. Top-down DP will cause stack overflow
1
2
3
4
5
6
7
8
9
10
# Time O(N^1.5)
class Solution:
    def winnerSquareGame(self, n: int) -> bool:
        dp = {}
        for i in range(n+1):
            if i == 0: dp[i] = False
            elif i == 1: dp[i] = True
            else:
                dp[i] = any(dp[i-j*j] is False for j in range(1, int(i**0.5) + 1))
        return dp[n]

Summary

  1. Brute force might be OK. Exhaust all possible case in a nice way.