Skip to content

Instantly share code, notes, and snippets.

@yodalee
Last active March 25, 2017 12:21
Show Gist options
  • Save yodalee/76040de7957d478ec09a7da50f6bd091 to your computer and use it in GitHub Desktop.
Save yodalee/76040de7957d478ec09a7da50f6bd091 to your computer and use it in GitHub Desktop.
Some algorithm problem solve
#include <iostream>
#include <vector>
using namespace std;
void peak(vector<vector<int>> &table, int row, int col) {
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
cout << table[i][j] << " ";
}
cout << endl;
}
}
//solve position -1
int solver(vector<vector<int>> &table, int n, int k) {
if (table[n][k] != -1) {
return table[n][k];
} else {
if (k > n*(n-1)/2) {
table[n][k] = 0;
return 0;
} else {
int sum = 0;
//cout << "process: (" << n << "," << k << ")" << endl;
// pos is the position that ith number place
for (int pos = 1; pos <= n; ++pos) {
if (n-pos > k) {
// if i-pos > j => place ith in pos will introduce too man inversion
continue;
} else {
//cout << "pos: " << pos << " remainInversion: " << j-(i-pos) << endl;
int remainInversion = k-(n-pos); // remain number of Inversion
sum += solver(table, n-1, remainInversion);
}
}
table[n][k] = sum;
return sum;
}
}
}
int solve(int n, int k) {
// prepare table
vector<vector<int>> table(n+1, vector<int>(k+1, -1));
for (int i = 1; i < n+1; ++i) {
table[i][0] = 1;
}
int ans = solver(table, n, k);
return ans;
}
int main(int argc, char *argv[])
{
int n, k;
cin >> n >> k;
cout << solve(n, k) << endl;
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
void printVec(vector<pair<unsigned int, unsigned int>> &v) {
cout << "peak: ";
for (auto i: v) {
cout << "(" << i.first << "," << i.second << ") ";
}
cout << endl;
}
int query(vector<pair<unsigned int, unsigned int>> &peak, unsigned int idx)
{
for (auto iter = peak.begin(); iter != peak.end(); iter++) {
if (iter->first >= idx) {
return iter->second;
}
}
}
void add(vector<pair<unsigned int, unsigned int>> &peak, unsigned int length, int insert) {
// update peak list
while (peak.size()) {
if (peak.back().second < insert) {
peak.pop_back();
} else {
break;
}
}
peak.push_back(pair<int, int>(length, insert));
}
int main() {
int m;
char ch[2];
unsigned int mod = 0;
unsigned int lastQuery = 0;
unsigned int length = 0;
vector<pair<unsigned int, unsigned int>> peak;
cin >> m >> mod;
while (m--) {
int x;
cin >> ch >> x;
if (ch[0] == 'I')
{
int insert = (x+lastQuery) % mod;
add(peak, length, insert);
length++;
//printVec(peak);
} else {
lastQuery = query(peak, length-x);
cout << lastQuery << endl;
}
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment