alphadraco
BAN USERO(N), sliding window approach, returns start and end indices of subsequence.
#include <bits/stdc++.h>
using namespace std;
pair<int, int> lexographically_smallest(vector<int>& v, int k) {
assert (v.size() >= k );
int mul = pow(10, k - 1);
int cur = 0, ans = 0;
pair<int, int> result_pair = {0, k-1};
for (int i = k - 1; i >= 0; i --) ans += v[i] * pow(10, k - i - 1);
cur = ans;
// cout << "cur " << cur << endl;
for (int i = k; i < v.size(); i ++) {
int temp_num = (cur % mul) * pow(10, k - 2) + v[i];
cout << "temp_num " << temp_num << endl;
if (ans > temp_num) {
ans = temp_num;
result_pair = {i - k + 1, i};
}
cur = temp_num;
}
return result_pair;
}
int main() {
vector<int> v = {6,3,2,4,2,6,8,9};
auto result = lexographically_smallest(v, 3) ;
cout << "indices " << result.first << " " << result.second << endl;
return 0;
}
to find people to bikes mapping bfs in matrix. For second part naive approach could be to find distance between each pair of person and bike and choose bike with least sum.
- alphadraco April 26, 2020O(nlogn)
bool print_result(vector<pair<int, int > >& v, pair<int, int>& p) {
if (v.size() == 0) return false;
sort(v.begin(), v.end());
vector<pair<int, int> > x;
//print_a(v);
x.emplace_back(v[0]);
for (int i = 1; i < v.size(); i ++) {
if (x[x.size() - 1].second >= v[i].first) {
x[x.size() - 1].second = v[i].second;
}
else {
x.emplace_back(v[i]);
}
}
//print_a(x);
for (int i = 0; i < x.size(); i ++) {
if (p.first >= x[i].first && p.second <= x[i].second) return true;
}
return false;
}
won't work! what if a number is greater than 10**10? In that case you need to split at 10th position.
- alphadraco April 26, 2020