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

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

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 ipykernel`

python -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…

This is a pretty hard problem.

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]) {…

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.

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

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

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>>&…

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

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

`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;

}

[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]

`struct Foo`

{

int key;

};

inline bool operator<(const Foo& lhs, const Foo& rhs)

{

return lhs.key < rhs.key;

}

struct Foo

{

int key;

};bool compareFoo(const Foo &lhs, const Foo &rhs)

{

return lhs.x < rhs.x;

}

std::set<Foo,compareFoo> mySet;

`struct Foo `

{

int key;

bool operator < (const Foo &other) const

{

return key < other.key;

}

};

struct Foo

{

int key;

};auto compareFoo = [](Foo lhs, Foo rhs) { return lhs.x < rhs.x;};

set<Foo, decltype(compareFoo)> mySet(compareFoo);

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

Data Scientist/MLE/SWE @takemobi