weekly-contest-226

Welcome to Weekly Contest 226! Feel free to share and post your contest experience here!

You can also view the rankings for the contest here.

Links to the individual problems are included below:

Maximum Number of Balls in a Box (3 points)

Restore the Array From Adjacent Pairs (4 points)

Can You Eat Your Favorite Candy on Your Favorite Day? (5 points)

Comparing to the last 10 contests, Q1: harder than usual, 73.70% acceptance; Q2: average difficulty, 42.74% acceptance; Q3: average difficulty, 20.47% acceptance; Q4: easiest among the last 10 contests, 17.58% acceptance; overall: this contest is easier than usual. I compile past contest data to provide a data-driven way to assess problem difficulty. See more at:
https://docs.google.com/spreadsheets/d/14UU9Ny7ohum7JTgG1zPL0Z5IsR_qbSeLM8jNcMVfvJI/edit?usp=sharing
(Acceptance rate is calculated with caveats detailed in the spreadsheet.)

1742. Maximum Number of Balls in a Box

leetcode.com/problems/maximum-number-of-balls-in-a-box/

Easy

352Add to ListShare

You are working in a ball factory where you have n balls numbered from lowLimit up to highLimit inclusive (i.e., n == highLimit - lowLimit + 1), and an infinite number of boxes numbered from 1 to infinity.

Your job at this factory is to put each ball in the box with a number equal to the sum of digits of the ball's number. For example, the ball number 321 will be put in the box number 3 + 2 + 1 = 6 and the ball number 10 will be put in the box number 1 + 0 = 1.

Given two integers lowLimit and highLimit, return the number of balls in the box with the most balls.

Example 1:

Input: lowLimit = 1, highLimit = 10 Output: 2 Explanation: Box Number: 1 2 3 4 5 6 7 8 9 10 11 ... Ball Count: 2 1 1 1 1 1 1 1 1 0 0 ... Box 1 has the most number of balls with 2 balls.

Example 2:

Input: lowLimit = 5, highLimit = 15 Output: 2 Explanation: Box Number: 1 2 3 4 5 6 7 8 9 10 11 ... Ball Count: 1 1 1 1 2 2 1 1 1 0 0 ... Boxes 5 and 6 have the most number of balls with 2 balls in each.

Example 3:

Input: lowLimit = 19, highLimit = 28 Output: 2 Explanation: Box Number: 1 2 3 4 5 6 7 8 9 10 11 12 ... Ball Count: 0 1 1 1 1 1 1 1 1 2 0 0 ... Box 10 has the most number of balls with 2 balls.

Constraints:

1 <= lowLimit <= highLimit <= 105

Note that both lowLimit and highLimit are of small constraints so you can iterate on all nubmer between them

Show Hint 2

You can simulate the boxes by counting for each box the number of balls with digit sum equal to that box number

    def countBalls(self, lowLimit: int, highLimit: int) -> int:
        cnt, mx = [0] * 46, 0
        for i in range(lowLimit, highLimit + 1):
            sm = 0
            while i > 0:
                sm += i % 10
                i //= 10
            cnt[sm] += 1
            mx = max(mx, cnt[sm])
        return mx

1743. Restore the Array From Adjacent Pairs

leetcode.com/problems/restore-the-array-from-adjacent-pairs/

Medium

992Add to ListShare

There is an integer array nums that consists of n unique elements, but you have forgotten it. However, you do remember every pair of adjacent elements in nums.

You are given a 2D integer array adjacentPairs of size n - 1 where each adjacentPairs[i] = [ui, vi] indicates that the elements ui and vi are adjacent in nums.

It is guaranteed that every adjacent pair of elements nums[i] and nums[i+1] will exist in adjacentPairs, either as [nums[i], nums[i+1]] or [nums[i+1], nums[i]]. The pairs can appear in any order.

Return the original array nums. If there are multiple solutions, return any of them.

Example 1:

Input: adjacentPairs = [[2,1],[3,4],[3,2]] Output: [1,2,3,4] Explanation: This array has all its adjacent pairs in adjacentPairs. Notice that adjacentPairs[i] may not be in left-to-right order.

Example 2:

Input: adjacentPairs = [[4,-2],[1,4],[-3,1]] Output: [-2,4,1,-3] Explanation: There can be negative numbers. Another solution is [-3,1,4,-2], which would also be accepted.

Example 3:

Input: adjacentPairs = [[100000,-100000]] Output: [100000,-100000]

Constraints:

nums.length == n
adjacentPairs.length == n - 1
adjacentPairs[i].length == 2
2 <= n <= 105
-105 <= nums[i], ui, vi <= 105
There exists some nums that has adjacentPairs as its pairs.

Greedy

Find the first element of nums - it will only appear once in adjacentPairs.

The adjacent pairs are like edges of a graph. Perform a depth-first search from the first element.

class Solution:
    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:
        adj, ans, n = defaultdict(list), [], len(adjacentPairs) + 1
        for a, b in adjacentPairs:
            adj[a] += [b]
            adj[b] += [a]
            
        prev = cur = -math.inf
        for k, v in adj.items():
            if len(v) == 1:
                cur = k
                break
                
        ans += [cur]   
        while len(ans) < n:
            for v in adj.pop(cur):
                if v != prev:
                    ans += [v]
                    prev = cur
                    cur = v
                    break
        return ans

1744. Can You Eat Your Favorite Candy on Your Favorite Day?

leetcode.com/problems/can-you-eat-your-favorite-candy-on-your-favorite-day/

Medium

31108Add to ListShare

You are given a (0-indexed) array of positive integers candiesCount where candiesCount[i] represents the number of candies of the ith type you have. You are also given a 2D array queries where queries[i] = [favoriteTypei, favoriteDayi, dailyCapi].

You play a game with the following rules:

You start eating candies on day 0.
You cannot eat any candy of type i unless you have eaten all candies of type i - 1.
You must eat at least one candy per day until you have eaten all the candies.

Construct a boolean array answer such that answer.length == queries.length and answer[i] is true if you can eat a candy of type favoriteTypei on day favoriteDayi without eating more than dailyCapi candies on any day, and false otherwise. Note that you can eat different types of candy on the same day, provided that you follow rule 2.

Return the constructed array answer.

Example 1:

Input: candiesCount = [7,4,5,3,8], queries = [[0,2,2],[4,2,4],[2,13,1000000000]] Output: [true,false,true] Explanation: 1- If you eat 2 candies (type 0) on day 0 and 2 candies (type 0) on day 1, you will eat a candy of type 0 on day 2. 2- You can eat at most 4 candies each day. If you eat 4 candies every day, you will eat 4 candies (type 0) on day 0 and 4 candies (type 0 and type 1) on day 1. On day 2, you can only eat 4 candies (type 1 and type 2), so you cannot eat a candy of type 4 on day 2. 3- If you eat 1 candy each day, you will eat a candy of type 2 on day 13.

Example 2:

Input: candiesCount = [5,2,6,4,1], queries = [[3,1,2],[4,10,3],[3,10,100],[4,100,30],[1,3,1]] Output: [false,true,true,false,false]

Constraints:

1 <= candiesCount.length <= 105
1 <= candiesCount[i] <= 105
1 <= queries.length <= 105
queries[i].length == 3
0 <= favoriteTypei < candiesCount.length
0 <= favoriteDayi <= 109
1 <= dailyCapi <= 109

The query is true if and only if your favorite day is in between the earliest and latest possible days to eat your favorite candy.

To get the earliest day, you need to eat dailyCap candies every day. To get the latest day, you need to eat 1 candy every day.

The latest possible day is the total number of candies with a smaller type plus the number of your favorite candy minus 1.

The earliest possible day that you can eat your favorite candy is the total number of candies with a smaller type divided by dailyCap.

The query is true if and only if your favorite day is in between the earliest and latest possible days to eat your favorite candy.

Hide Hint 2

To get the earliest day, you need to eat dailyCap candies every day. To get the latest day, you need to eat 1 candy every day.

Hide Hint 3

The latest possible day is the total number of candies with a smaller type plus the number of your favorite candy minus 1.

Hide Hint 4

The earliest possible day that you can eat your favorite candy is the total number of candies with a smaller type divided by dailyCap.

    def canEat(self, candiesCount, queries):
        A = [0] + list(accumulate(candiesCount))
        return [A[t] // c <= d < A[t + 1] for t, d, c in queries]