Today I solved an interesting problem. We can use both 2D range sum and DP to solve this problem.

Social Distancing 2

The critical part is converting the problem into find the largest square contains all 0s.

The problem can be solve by using 2D range sum, DP or

2D range sum


Suppose you have a conda environment name as “YOUR_ENVIRONMENT_NAME”, then the following two steps can make it work.


This is the lastest question of the weekly contest of June 12, 2021. It is pretty hard if you don’t know the bit mask DP before.

1900. The Earliest and Latest Rounds Where Players Compete

Basic idea:

Using the bit mask to represent the exist player. If that specified bit is 1, it means we have a plyer at that position.

0, 1, 2, 3, will have 1111.


This is a pretty hard problem.

Special Nodes

Naively solve the problem by using a dfs way to traverse each subtree.

Each subtree will maintain a set contains all the colors values. Then check each subtree by using a DFS way.


The problem is described in Chinese. The basic ideas if find k edges after deleting a connected graph to make sure:

the shortest path after deletion can be kept.

The basic idea to solve this problem is keeping the edges which can be used to built the shortest path. Delete the rest then the shortest path to the root node 1 will be preserved.

A naive dijkstra is used here.


This week’s (Jun 5, 2021) 4th problem, we can solve it by thinking the problem process reversely.

1889. Minimum Space Wasted From Packaging

A naive approach got TLE

A naive approach is putting the pacakage in a map and traverse each package to see the smallest fit box. And harvest the results.

The time complexity is O(n*m*log m) where n is the length of the packages and m is the maximum length of the box. Since n and m can as large as 10⁵, this solution will get TLE.


Today I found a pretty nice video in Chinese to explain the Dijkstra’s algorithm. It is very clear explained.


From [1]

An application is here

Longest Prefix Sequence

Reference

[1] https://stackoverflow.com/questions/18831470/sorting-a-string-vector-based-on-the-string-size


The question can be found from [1]. I am looking for answers as I also have the same confusion. Why less gives us the largest number (max heap), isn’t it be a minimum number (min heap)?

From the reply of [1], we can see the reason for using less is:

For consistency. less is used as the default comparator for many algorithms and containers, and us mere humans don't have to try and remember which one uses which comparator by default since they are all the same. From [1]

From [2]

The underlying container may be any of the standard…


One

Two

Three

Four (lambda expression)

Reference

[1] https://stackoverflow.com/questions/5816658/how-to-have-a-set-of-structs-in-c

Jimmy Shen

Data Scientist/MLE/SWE @takemobi

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store