# 2D range sum and DP and via multi-source 0–1 BFS.

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

`int solve(vector<vector<int>>& matrix) {    const int n = matrix.size();    if (n<=1) return 0;    const int m = matrix[0].size();    for (int j = 1; j < m; ++j)matrix[0][j] += matrix[0][j-1];    for (int i = 1; i < n; ++i)matrix[i][0] += matrix[i-1][0];for (int i = 1; i < n; ++i)…`

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

`conda install -c anaconda ipykernelpython -m ipykernel install --user --name=YOUR_ENVIRONMENT_NAME`

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.

`// find special cases:        // 1) a pk b, this is the basecase, return        // 2) a is…`

# A tree problem: Special Nodes

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.

`int ret = 0;int seen[100010];bool helper(int node, vector<vector<int>>& tree, vector<int>& color, unordered_set<int>&s) {    unordered_set<int> thiss;    auto x = color[node];    s.insert(x);    bool good = true;    for (auto &next: tree[node]) {        if (!seen[next]) {…`

# Build the shortest path tree

## Delete edges in a graph

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.

`#include <iostream>#include <cstring>#include <algorithm>#include<vector>#include<set>#include<map>using namespace std;typedef long long LL;const LL INF = 1e16;typedef pair<int, int> PII;int main(){    int n, m, k…`

# Think the problem reversely

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

# 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.

`typedef long long LL;const int mod = 1e9+7;const long long INF = 1e10+6;class Solution {public:    int minWastedSpace(vector<int>& packages, vector<vector<int>>&…`

# Best video to explain the Dijkstra algorithm

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

# C++ sort by word length

From [1]

`std::vector<std::string> v;std::sort(v.begin(), v.end(), []    (const std::string& first, const std::string& second){        return first.size() < second.size();    });`

An application is here

# Longest Prefix Sequence

`int solve(vector<string>& words) {    sort(words.begin(), words.end(), [](string &a, string &b){        return a.size() < b.size();});    int ret = 0;    unordered_map<string, int> memo;    for (auto word: words) {        if (word.size() > 1) {            memo[word] = 1;            string subword = word.substr(0,word.size() - 1);            if (memo.find(subword) != memo.end()){                memo[word] = max(memo[word], memo[subword] + 1);            }        } else {            memo[word] = 1;        }    }    for (auto [k, v]: memo) ret = max(ret, v);    return ret;}`

# Why does priority queue (max heap) in C++ use less<T> instead of greater<T>?

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

`struct Foo{  int key;};inline bool operator<(const Foo& lhs, const Foo& rhs){  return lhs.key < rhs.key;}`

# Two

`struct Foo{  int key;};bool compareFoo(const Foo &lhs, const Foo &rhs){    return lhs.x < rhs.x;}std::set<Foo,compareFoo> mySet;`

# Three

`struct Foo {  int key;  bool operator < (const Foo &other) const  {    return key < other.key;  }};`

# Four (lambda expression)

`struct Foo{  int key;};auto compareFoo = [](Foo lhs, Foo rhs) { return lhs.x < rhs.x;};set<Foo, decltype(compareFoo)> mySet(compareFoo);`

# Reference

## Jimmy Shen

Data Scientist/MLE/SWE @takemobi

Get the Medium app