CareerCup

Let F(N,L,K) = N*(N-1)...(N-K) * [(N-K)*(N-K)*....(N-L)].(length is L)
The answer should be :
F(N,L,K) - C(N,1)F(N-1,L,K) + C(N,2)F(N-2,L,K)F(N,3)F(N-3,L,K) .....where C(n,i) means combination number of selecting i items from n items.

string max_substr(string str){
    vector<pair<int,int>> vec;
    char maxx = 'a';
    for (int i = 0; i < str.size(); ++i){
        maxx = max(maxx, str[i]);
    }
    vector<pair<int,int>> candidates;
    for (int i = 0; i < str.size(); ++i){
        if (str[i] == maxx){
            candidates.push_back(make_pair(i, i));
        }
    }
    while (candidates.size() > 1){
        char maxx = 'a';
        for (int i = 0; i < candidates.size(); ++i){
            if (candidates[i].second + 1 < str.size()){
                maxx = max(maxx, str[candidates[i].second + 1]);
            }
        }
        vector<pair<int, int>> newcan;
        for (int i = 0; i < candidates.size(); ++i){
            if (candidates[i].second + 1 < str.size() && str[candidates[i].second + 1] == maxx){
                newcan.push_back(make_pair(candidates[i].first, candidates[i].second + 1));	
            }
        }
        candidates = newcan;
    }
    return str.substr(candidates[0].first);
}

Suppose all digit mean the times of following string in bracket. "abc2a" is invalid.

string inner_expand(string str, int& site){
    string ret = "";
    while (site < str.size()){
        if (str[site] >= '0' && str[site] <='9'){
            int times = 0;
            while (str[site] != '['){
                times = times * 10 + str[site++] - '0';
            }
            
            ++site;
            string sub_ret = inner_expand(str, site);
            for(int i = 0; i < times; ++i){
                ret += sub_ret;
            }
        }
        else if (str[site] == ']'){
            ++site;
            return ret;
        }
        else{
            ret += str[site++];
        }
    }
    return ret;
}

string expand(string str){
    int site = 0;
    return inner_expand(str, site);
}

int inner_min_swap(vector<int> &vec){
	int l = 0;
	int sum = 0;
	for (int i = 0; i < vec.size(); ++i){
	if (vec[i] == 0){
	sum += i - l;
	++l;
}
}
return sum;
}
int min_swap(vector<int> vec){
	int ans = inner_Min_swap(vec);
	reverse(vec.begin(), vec.end());
	ans = min(inner_min_swap(vec));
	return ans;
}

map<long, int> search(TreeNode *root){
    if (root == NULL){
        return map<long,int>();
    }
    if (root->left == NULL && root->right == NULL){
        map<long, int> mp;
        mp[root->val] = 1;
        return mp;
    }
    map<long, int> l = search(root->left);
    map<long, int> r = search(root->right);
    map<long, int> ret;
    if (l.size() != 0){
        for (auto it = l.begin(); it != l.end(); ++it){
            ret[it->first + root->val] += it->second;
        }
    }
    if (r.size() != 0){
        for (auto it = r.begin(); it != r.end(); ++it){
            ret[it->first + root->val] += it->second;
        }
    }
    return ret;
}

int pathSum(TreeNode *root, int target){
    map<long, int> mp = search(root);
    return mp[target];
}

Sort every time point including departure time and arrival time.
Then scan all the time point. Firstly, drop off crews for arrival flights. Then let some crews go to departure flights. If no enough crews, then return false result.

struct Flight{
    string start;
    string destination;
    int start_time;
    int arrive_time;
    Flight(string s, string d, int st, int ar){
        start = s;
        destination = d;
        start_time = st;
        arrive_time = ar;
    }
};

bool check(vector<Flight> flights, vector<string> crews){
    vector<string> arrive[25];
    vector<string> departs[25];
    map<string, int> crew_in_place;
    for (int i = 0; i < crews.size(); ++i){
        crew_in_place[crews[i]]++;
    }
    for (int i = 0; i < flights.size(); ++i){
        arrive[flights[i].arrive_time].push_back(flights[i].destination);
        departs[flights[i].start_time].push_back(flights[i].start);
    }
    for (int i = 0; i < 25; ++i){
        for (int j = 0; j < arrive[i].size(); ++j){
            crew_in_place[arrive[i][j]]++;
        }
        for (int j = 0; j < departs[i].size(); ++j){
            crew_in_place[departs[i][j]]--;
            if (crew_in_place[departs[i][j]] < 0){
                return false;
            }
        }
    }
    return true;
}

1. set current first on as the start car of the cluster.
2.find following car whose speed is smaller than start car, so all cars before this one are belong to previous cluster.
3.Repeat step #1 and #2 till the end.

I don't quite understand what follow-up is talking.

Easy DP could be O(n*m*(n+m)).
Greedy algorithm is iteratively choosing minimum from rest values, then check if it is valid in previous selected path by comparing its coordinate with previous coordinate and next coordinate in path. O(n*m*log(n+m))

struct Node{
    int val;
    int x;
    int y;
};
int cmp(Node &a, Node &b){
    return  a.val < b.val;
}
vector<int> get_ans(vector<vector<int>> &grid){
    int n = grid.size();
    int m = grid[0].size();
    vector<Node> vec(n * m - 2);
    int site = 0;
    for (int i = 0; i < n; ++i){
        for (int j = 0; j < m; ++j){
            if ((i == 0 && j == 0) || (i == n-1 && j == m-1)){
                continue;
            }
            vec[site].val = grid[i][j];
            vec[site].x = i;
            vec[site].y = j;
            ++site;
        }
    }
    sort(vec.begin(), vec.end(), cmp);
    map<pair<int,int>, int> mp;
    mp[make_pair(0,0)] = grid[0][0];
    mp[make_pair(n-1,m-1)] = grid[n-1][m-1];
    for (int i = 0; i < vec.size(); ++i){
        pair<int, int> p = make_pair(vec[i].x, vec[i].y);
        cout << p.first << ", " << p.second << endl;
        auto it = mp.upper_bound(p);
        if (it != mp.end() && (vec[i].x > it->first.first || vec[i].y > it->first.second)){
            continue;
        }
        --it;
        if (it != mp.end() && (vec[i].x < it->first.first || vec[i].y < it->first.second)){
            continue;
        }
        cout << "pass" << endl;
        mp[p] = vec[i].val;
    }
    vector<int> ans;
    for (auto it = mp.begin(); it != mp.end(); ++it){
        ans.push_back(it->second);
    }
    sort(ans.begin(), ans.end());
    return ans;
}

0
01
0110
01101001
.......
You could find that prefix is same as previous line, and postfix is the reverse of number of prefix. So jth is the only variable you need to care.

jth is 0 indexed.

int get_ans(int k, int jth){
    int str[4] = {0,1,1,0};
    if (jth < 4){
        return str[jth];
    }
    bool reverse = 0;
    while (jth >= 4){
        jth = jth - pow(2,(int)log(jth));
        reverse ^= 1;
    }
    if (reverse){
        return str[jth] ^1;
    }
    return str[jth];
}

It is really cool ! Thanks a lot!

you could not pass the case in my ps.

you could get the conception form wiki~

If the string contains 26 characters, the integer will overflow.

If the string val contains '(' or ')', it will not work well.

change the solution a little.

#include <iostream>
#include <vector>
#include <queue>
#include <sstream>

using namespace std;

struct tree_node {
	string val;
	vector<tree_node *> children;
	tree_node(string v) : val(v) { }
};

string serialize(tree_node *root) {
	if (root == NULL)
		return "";

	queue<tree_node*> queue;
	ostringstream oss;

	queue.push(root);
	oss << root->val.size();
	oss << " " << root->val;

	while (!queue.empty()) {
		tree_node *curr = queue.front();
		queue.pop();
		oss << " " <<  curr->children.size();

		for (vector<tree_node*>::const_iterator it = curr->children.begin();
		     it != curr->children.end();
		     it++) {

			oss << " " << (*it)->val.size() << " " << (*it)->val;
			queue.push(*it);
		}
	}
	return oss.str();
}
bool read(istringstream& iss, char buf[], int len){
    int totallen = 0;
    int restlen = len;
    while (1){
        int sz = iss.readsome(buf, restlen);
        totallen += sz;
        if (totallen >= len){
            break;
        }
        if (sz == 0){
            return false;
        }
    }
    buf[len] = '\0';
    return true;
}
tree_node *deserialize(const string &tree_str) {
	if (tree_str == "")
		return NULL;

	queue<tree_node*> queue;
	istringstream iss(tree_str);
    int length;
    iss >> length;
    char buf[1000];
    read(iss, buf, length + 1);
	tree_node *root = new tree_node(buf + 1);

	queue.push(root);

	while (!queue.empty()) {
		tree_node *curr = queue.front();
		queue.pop();
		int count;
		iss >> count;
		for (int i = 0; i < count; i++) {
            iss >> length;
			read(iss, buf, length +1);
			tree_node *new_node = new tree_node(buf + 1);
			curr->children.push_back(new_node);
			queue.push(new_node);
		}
	}
	return root;
}
void traverse(tree_node* root){
    if (root == NULL)
        return;
    cout << root->val.size() << ":" << root->val << endl;
    for (int i = 0; i < root->children.size(); ++i){
        traverse(root->children[i]);
    }
}
int main(void) {

    tree_node* root = new tree_node("ro ot1");
    tree_node* r1 = new tree_node("r\n1");
    tree_node* r2 = new tree_node("r 2");
    tree_node* r3 = new tree_node("r 3");
    tree_node* r21 = new tree_node("r21");
    root->children.push_back(r1);
    root->children.push_back(r2);
    root->children.push_back(r3);
    r3->children.push_back(r21);

    string ret = serialize(root);
    //cout << ret.size() << " " << ret << endl;

    tree_node* newroot = deserialize(ret);
    traverse(newroot);

	return 0;
}

OH, I found something wrong that this solution could't solve the val is string type and val is like that "ro ot" or "ro\n ot".

It's really cool. I don't aware that i could use the *stream to deal with this problem.

In network, you can only transform byte stream, maybe you could assume that you can keep the tree in a string not a list.

c!

this is a famous algorithm which can select nums from data stream equally.

i think it is hard to understand... but it's really cool.
we can transform the integer to 32-bit, and use a array to store the sum of each bit. at last, mod 3 and all the bit is not 0 is the special num 's bit.

and check n is positive

there are a data structure named Binary Indexed Tree(BIT), it can solve this problem well. ps. if the data range is so large, we can hash each different num to a continuous sequence.

i can't analyze your time complexity, but your answer is wrong. because you will lose some nodes.

i think your work is O(N^2) time complexity... each time you have to merge the list... it's really O(n^2)

Actually，this problem is a maximum independent set problem. we can use each vote to build a bipartite graph， and use Hungarian algorithm to calculate the maximum number of matches，and total number of V minus the maximum matches is the answer.

No,but the idea which use a array dp[i][j] to solve this problem is right.So I think n^3 is OK.

yes!

why the worst is o(n^2),Could you give a sample.

I think it is o(nlogn) time.En...this solution is the best here.