plesiv
BAN USERSolution would be subgraph with n vertices which has most edges that connect two vertices in that subraph.
1) If we have subgraph, counting edges in it can be done fast (worst, n^2).
2) If we can find subgraph fast, e.g. in O(P(m)) time where P(m) is some polynomial - we could do binary search on number of vertices n in a subgraph in range (0..m) and find smallest subgraph that has n*(n-1)/2 connections, which would be fully connected subgraph i.e. clique.
3) this would mean that we could find clique in a graph in worst case O(P(m)*log(m)*m^2), and since finding clique is NP-complete, we conclude that finding best subgraph is at least as hard as finding a clique (can't be done in O(P(m)) time) - it is NP-complete.
Brute force solution has O( nchoosek(m, n) ) complexity (iterates over all subgraphs and finds best one).
Here's the implementation for proposed algorithm. I tested output correspondence with the slower solution:
#include <fstream>
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <functional>
using namespace std;
struct Graph {
struct Node {
Node *parent;
Node *max1Child;
Node *max2Child;
int max1;
int max2;
Node(): parent(nullptr), max1Child(nullptr), max2Child(nullptr),
max1(0), max2(0) {}
};
int di;
int sz;
vector<Node*> nd;
Graph(): di(0), sz(1), nd(vector<Node*> (1, new Node()) ) {}
int insert(int);
};
int Graph::insert(int n) {
Node *nn = new Node();
nn->parent = nd[n];
nd.push_back(nn);
++sz;
Node *pn = nullptr;
Node *cn = nn;
int dpth = 0;
while (true) {
if (pn == cn->max1Child) {
if (dpth > cn->max1) {
cn->max1 = dpth;
}
}
else {
if (dpth > cn->max1) {
cn->max2 = cn->max1;
cn->max2Child = cn->max1Child;
cn->max1 = dpth;
cn->max1Child = pn;
}
else if (dpth > cn->max2){
cn->max2 = dpth;
cn->max2Child = pn;
}
}
di = max(di, cn->max1 + cn->max2);
if (!cn->parent) {
break;
}
dpth = cn->max1 + 1;
pn = cn;
cn = cn->parent;
}
return di;
}
int main() {
Graph graph;
int N; cin >> N;
for (int i = 0; i < N; ++i) {
int tmp; cin >> tmp;
cout << graph.insert(tmp) << endl;
}
}
// Since there are no requirements to optimize accoring to some criteria,
// greedily assign icecreams to free machines as they come. When there are no
// free machines, wait for the first free one.
//input: order-time, order-number, icecream-type
//output: order-num, depart-time, total-time
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
struct Order {
int numb;
int type;
int start_time;
int end_time;
Order(): numb(0), type(0), start_time(0), end_time(0) {}
Order(int n, int y, int t): numb(n), type(y), start_time(t), end_time(0) {}
};
bool cmp_start_time(const Order &le, const Order &ri) {
return le.start_time < ri.start_time ||
(le.start_time == ri.start_time && le.type < ri.type) ||
(le.start_time == ri.start_time && le.type == ri.type && le.numb < ri.numb);
}
bool cmp_numb(const Order &le, const Order &ri) {
return le.numb < ri.numb ||
(le.numb == ri.numb && le.start_time < ri.start_time) ||
(le.numb == ri.numb && le.start_time == ri.start_time && le.type < ri.type);
}
int machine[3] = {0};
int main() {
vector<Order> orders {
Order(0, 0, 15),
Order(1, 0, 5),
Order(2, 1, 10),
Order(3, 1, 20),
Order(4, 1, 35) };
/* 00 05 10 15 20 25 30 35 40 45 50 55 60 65 70
* 0 |=========================|
* 1 |=========================|
* 2 |=======|
* 3 ***|=======|
* 4 ***|=======|
*/
// sort by start_time
sort(orders.begin(), orders.end(), cmp_start_time);
// process orders
for (auto it = orders.begin(); it != orders.end(); ++it) {
int which = -1;
int free = INT_MAX;
for (int i = 0; i < 3; ++i) {
if (machine[i] < free) {
free = machine[i];
which = i;
}
}
int real_start = max(machine[which], it->start_time);
if (it->type == 0) {
machine[which] = real_start + 45;
}
else {
machine[which] = real_start + 15;
}
it->end_time = machine[which];
}
// sort by order-number
sort(orders.begin(), orders.end(), cmp_numb);
// display
for (const auto &o : orders) {
cout << o.numb << ' ' << o.end_time << ' ' << (o.end_time - o.start_time);
cout << endl;
}
}
**Edit:** This is not asymptotically optimal. See CT's answer...
[WRONG: I think this is asymptotically optimal:]
// TIME: O(N) for update on every node insertion; O(N^2) total
// MEMORY: O(N^2) for storing all pair-wise distances
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 1010;
/*
* sz -> nodes in the graph
* max_di -> current diameter
* di -> pair-wise distance between nodes
* wh -> wh[i] is index of node that is farthest from node i
*/
struct Graph {
int sz;
int max_di;
int di[MAXN][MAXN];
int wh[MAXN];
Graph(): sz(1), max_di(0), di{0}, wh{0} {}
int insert(int);
void write_di(int x, int y, int d) { di[x][y] = di[y][x] = d; };
};
int Graph::insert(int n) {
wh[sz] = 0;
for (int i = 0; i < sz; ++i) {
// pair-wise distance between new node and every node already in graph
write_di(sz, i, di[i][n] + 1);
// new distances contend for maximal distance
max_di = max(max_di, di[sz][i]);
// update farthest node for new node
if (di[sz][wh[sz]] < di[sz][i]) {
wh[sz] = i;
}
// update farthest node for every node already in graph
if (di[i][wh[i]] < di[i][sz]) {
wh[i] = sz;
}
}
++sz;
return max_di;
}
int main() {
Graph graph;
int N;
cin >> N;
for (int i = 0; i < N; ++i) {
int tmp;
cin >> tmp;
cout << graph.insert(tmp) << endl;
}
}
// Local minimum
// On high level binary search is used:
// 1) escape long streak of monotone values,
// 2) degenerates to gradient-descent on ranges with 2 or 3 elements
#include <iostream>
//int L = 8;
//int arr[] = { 1, 3, 2, 4, 5, 7, 8, 9 };
//int L = 7;
//int arr[] = { 30, 10, 20, 25, 14, 12, 8 };
int L = 3;
int arr[] = { 3, 2, 1 };
int indexMinimum(int a[], int al) {
int lb = 0;
int ub = al-1;
while (lb < ub) {
int mid = lb + (ub - lb + 1)/2;
if (a[lb] < a[mid]) {
ub = mid-1;
}
else {
lb = mid;
}
}
return lb;
}
int main() {
int index = indexMinimum(arr, L);
std::cout << "arr[" << index << "] = " << arr[index] << std::endl;
}
// Solution with segment trees.
//
// TIME: O(log(N)) for both getNumber() and requestNumber(), since N
// is bound to 10^10 in this case, each lookup is done in
// exactly 34 steps
// MEMORY: grows towards O(N) maximum as numbers are added
// Basic idea: traverse the segment tree from the root to the leaf at each
// getNumber() or requestNumber() invocation, creating child nodes as needed.
// When number is successfully chosen (wasn't chosen before), decrease the
// remain counter of the each node in the chain from the leaf to the parrent
// by 1.
//
// [ lb=0 : ub=7 ]
// [ remain = 8 ]
// / \
// / \
// [ lb=0 : ub=3 ] [ lb=4 : ub=7 ]
// [ remain = 4 ] [ remain = 4 ]
//
#include <iostream>
#include <cassert>
class SegmentTree {
private:
struct Node {
long long lb;
long long ub;
long long remain;
Node *parent;
Node *left;
Node *right;
Node(long long lb_i, long long ub_i, Node *parent_i): lb(lb_i),
ub(ub_i), remain(ub_i-lb_i+1), parent(parent_i), left(nullptr),
right(nullptr) { }
};
Node *root;
int MSB;
public:
SegmentTree(long long lb_i, long long ub_i) {
MSB = 0;
while (ub_i) {
++MSB;
ub_i >>= 1;
}
this->root = new Node(lb_i, (1LL << MSB)-1, nullptr);
}
long long getNumber() {
if (this->root->remain > 0) {
Node *cn = this->root;
while (true) {
cn->remain -= 1;
if (cn->lb == cn->ub) {
return cn->lb;
}
long long mid = cn->lb + (cn->ub - cn->lb)/2LL;
if (!cn->left) {
cn->left = new Node(cn->lb, mid, cn);
cn = cn->left;
}
else if (cn->left->remain > 0) {
cn = cn->left;
}
else if (!cn->right) {
cn->right = new Node(mid+1, cn->ub, cn);
cn = cn->right;
}
else {
assert(cn->right->remain > 0);
cn = cn->right;
}
}
}
return -1;
}
bool requestNumber(long long num) {
if (this->root->remain > 0) {
Node *cn = root;
while (true) {
if (cn->lb == cn->ub) {
if (cn->remain > 0) {
while (cn) {
cn->remain -= 1;
cn = cn->parent;
}
return true;
} else {
break;
}
}
long long mid = cn->lb + (cn->ub - cn->lb)/2LL;
if (num <= mid) {
if (!cn->left) {
cn->left = new Node(cn->lb, mid, cn);
}
cn = cn->left;
} else {
if(!cn->right) {
cn->right = new Node(mid+1, cn->ub, cn);
}
cn = cn->right;
}
}
}
return false;
}
};
int main() {
SegmentTree store(0, (long long) (1e10) - 1);
std::cout << "getNum > " << store.getNumber() << std::endl;
std::cout << "reqNum(0) > " << (store.requestNumber(0)?"true":"false");
std::cout << std::endl;
std::cout << "reqnum(1) > " << (store.requestNumber(1)?"true":"false");
std::cout << std::endl;
std::cout << "reqNum(1) > " << (store.requestNumber(1)?"true":"false");
std::cout << std::endl;
std::cout << "reqNum(3) > " << (store.requestNumber(3)?"true":"false");
std::cout << std::endl;
std::cout << "getNum > " << store.getNumber() << std::endl;
std::cout << "getNum > " << store.getNumber() << std::endl;
std::cout << "getNum > " << store.getNumber() << std::endl;
}
N being upper bound (10^10 here), your getNumber() is O(1) if you assign <= 10^8 numbers, assigning numbers after that makes it O(N). I think that there is no amortization here, granted linear scan will be done rarely, but it will still be done after you assign 10^8 numbers.
- plesiv February 27, 2015#include <iostream>
#include <string>
using std::string;
int calculate(string expr) {
int len = int(expr.size());
int ub = 0;
int op_plus = true;
int total = 0;
while (ub < len) {
int lb = ub;
++ub;
if (expr[lb] == '+' || expr[lb] == ' ') {
continue;
}
if (expr[lb] == '*') {
op_plus = false;
total = 1;
continue;
}
int num = 0;
if ('0' <= expr[lb] && expr[lb] <= '9') {
while (ub < len && '0' <= expr[ub] && expr[ub] <= '9') {
++ub;
}
num = std::stoi(expr.substr(lb, ub-lb));
}
else if (expr[lb] == '(') {
int c = 1;
++ub;
while (ub < len && c) {
if (expr[ub] == '(') {
++c;
}
else if (expr[ub] == ')') {
--c;
}
++ub;
}
num = calculate(expr.substr(lb+1, ub-lb-2));
}
if (op_plus) {
total += num;
}
else {
total *= num;
}
}
return total;
}
int main() {
string expr[3] = {
string("+ 2 4"),
string("* 8 ( + 7 12)"),
string("( + 7 ( * 8 12 ) ( * 2 (+ 9 4) 7 ) 3 )")
};
for (int i = 0; i < 3; ++i) {
std::cout << expr[i] << " = " << calculate(expr[i]) << std::endl;
}
}
// Bash pattern generation, e.g. "(a,b,cy)n,m", or "((a,b)o(m,n)p,b)"
#include <vector>
#include <iostream>
#include <string>
using std::string;
using std::vector;
vector<string> parse(string pat) {
int L = int( pat.size() );
int lp = 0;
int up = 0;
vector<string> aseg;
vector<string> cseg(1, "");
while (up<L) {
lp = up;
++up;
switch (pat[lp]) {
case '(': {
int c = 1;
while (up<L && c) {
if (pat[up] == '(') {
++c;
} else if (pat[up] == ')') {
--c;
}
++up;
}
vector<string> part = parse(pat.substr(lp+1, up-lp-2));
vector<string> tmp;
for (auto s1 : cseg) {
for (auto s2 : part) {
tmp.push_back(s1 + s2);
}
}
cseg = tmp;
break;
}
case ',': {
if (!cseg[0].empty()) {
aseg.insert(aseg.end(), cseg.begin(), cseg.end());
cseg = vector<string> (1, "");
}
break;
}
default: {
while(up<L && pat[up] != '(' && pat[up] != ')'
&& pat[up] != ',') {
++up;
}
string part = pat.substr(lp, up-lp);
vector<string> tmp;
for (auto s : cseg) {
tmp.push_back(s + part);
}
cseg = tmp;
break;
}
}
}
if (!cseg[0].empty()) {
aseg.insert(aseg.end(), cseg.begin(), cseg.end());
}
return aseg;
}
int main() {
const string s1 = "(a,b,cy)n,m";
vector<string> r1 = parse(s1);
std::cout << "First case:" << std::endl;
for (auto t : r1) {
std::cout << t << std::endl;
}
const string s2 = "((a,b)o(m,n)p,b)";
vector<string> r2 = parse(s2);
std::cout << "Second case:" << std::endl;
for (auto t : r2) {
std::cout << t << std::endl;
}
}
// TIME: O(log(L))
// MEMORY: O(1)
// L -> length of the blacklist
// Generate random numbers with some of the numbers blacklisted,
// for example range is (-2,12), list is [2,3,5,9].
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <map>
int generate(int lb, int ub, const int bl[], int L) {
int gen = rand() % (ub - lb + 1 - L);
int l = 0;
int u = L;
while (l < u) {
int m = l + (u-l)/2;
int f = bl[m] - m - lb;
if (f >= gen+1) {
u = m;
} else {
l = m + 1;
}
}
int f = bl[l] - l - lb;
int d = f - gen;
return bl[l] - d;
}
int main() {
srand(time(NULL)); // init seed
const int lb = -2;
const int ub = 12;
const int L = 4;
const int bl[L+1] = { 2, 3, 5, 9, ub+1 };
std::map<int, int> count;
for (int i = 0; i < 1000000; ++i) {
++count[ generate(lb, ub, bl, L) ];
}
for (std::map<int, int>::iterator it = count.begin(); it != count.end(); ++it) {
std::cout << "cnt[" << it->first << "] = " << it->second << std::endl;
}
}
// Popular number in an array occurs n/4 times.
// Assuming rounding down division of n/4, perform counting of every
// element on the index k*(n/4)-1 in the range [ 0, ..., n-1 ]
// - where k ∈ [1, ... ]
// Complexity: number of searches performed will be 4 or 5 times 2
// (lower and upper bound), each with O(log(n)) time.
// Example 1:
// o 12 / 4 = 3
// o [ 1, 2, 3, 4, 4, 4, 4, 4, 5, 6, 7, 8 ]
// ^ ^ ^ ^ 4 * 2 * binary-search
// Example 2:
// o 11 / 4 = 2
// o [ 1, 2, 3, 4, 4, 4, 4, 4, 5, 6, 7 ]
// ^ ^ ^ ^ ^ 5 * 2 * binary-searches
#include <iostream>
#include <algorithm>
void print_popular(int a[], int L) {
using std::lower_bound;
using std::upper_bound;
int step = L / 4;
for (int i = step-1; i < L;) {
int val = a[i];
int *ub = upper_bound(a, a+L, val);
int *lb = lower_bound(a, a+L, val);
if (ub-lb >= step) {
std::cout << val << " ";
}
// next i from ub (draw array to understand this one...)
i = ((ub-a)/step + 1) * step - 1;
}
std::cout << std::endl;
}
int main() {
const int La = 12;
std::cout << "First case: ";
int a[La] = { 1, 2, 3, 4, 4, 4, 4, 4, 5, 6, 7, 8 };
print_popular(a, La);
const int Lb = 11;
std::cout << "Second case: ";
int b[Lb] = { 1, 2, 3, 4, 4, 4, 4, 4, 5, 6, 7 };
print_popular(b, Lb);
}
// TIME: O(n + n^(2/3))
// SPACE: O(n^(2/3))
#include <vector>
#include <cmath>
#include <map>
#include <iostream>
void print_combos(int n) {
std::vector<int> cubes;
int cuberoot_max = int(pow(n, 1.0 / 3.0)) + 1;
for (int i = 1; i <= cuberoot_max; ++i) {
cubes.push_back(i*i*i);
}
int cubes_sz = int(cubes.size()); // == cuberoot_max
std::map<int, int> nc;
for (int i = 0; i < cubes_sz; ++i) {
for (int j = i; j < cubes_sz; ++j) {
nc[cubes[i] + cubes[j]] += 1;
}
}
for (int i = 1; i <= n; ++i) {
if (nc.count(i) && nc[i] >= 2) {
std::cout << i << std::endl;
}
}
}
int main() {
int N = 15000;
print_combos(N);
}
// Longest increasing subsequence
// TIME: O(n*log(n))
// SPACE: O(n)
#include <iostream>
// input
//const int L = 9;
//int a[L] = {-1, 2, 100, 100, 101, 3, 4, 5, -7};
const int L = 16;
int a[L] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
// output
int b[L+1] = {0};
int le = 0;
// STRICTLY INCREASING subsequence:
// --------------------------------
int M[L+1] = {0}; // M[j] -> index of a, such that a[M[j]] is
// smallest a with the sub-sequence of the
// lenght j ending at index M[j]
int P[L+1] = {-1};// P[k] -> index of a, such that a[P[k]] is
// predecessor of a[k] in the longest
// increasing sub-sequence
// M ( 0, ..., le ) -> index in a
// P ( index in a ) -> previous index in a
int main() {
for (int i = 0; i < L; ++i) {
int lb = 0;
int ub = le;
while (lb < ub) {
int mid = lb + (ub - lb) / 2;
if (a[i] <= a[M[mid]]) {
ub = mid;
} else {
lb = mid + 1;
}
}
// j = le
M[lb] = i;
if (lb > 0) {
P[i] = M[lb-1];
}
if (lb == le) {
++le;
}
}
int k = M[le-1];
for (int i = le-1; i >= 0; --i) {
b[i] = a[k];
if (i > 0) {
k = P[k];
}
}
for (int i = 0; i < le; ++i) {
std::cout << (i == 0 ? "" : " ") << b[i];
}
std::cout << std::endl;
}
Solution according to @deepanshu's suggested answer. Generates all permutations and the does binary search over the chunks of dictionary (default chunks 50 lines). Dictionary is assumed to contain only lower-letter-latin-character words, sorted and without repetitions.
This solution is also convenient for large dictionary (when dictionary can't fit in the memory) because of it's buffering nature.
- plesiv March 18, 2015