Contest : Replay of BSMRSTU Intra University Programming Contest 2019
Link : https://toph.co/c/bsmrstu-intra-2019-r
A. Hamming Distance
const int maxn = 2e6 + 5;
int Tree[maxn];
int N;
void update(int pos, int val = 1) {
while (pos <= N) {
Tree[pos] += val;
pos += (pos & -pos);
}
}
void range_update(int l, int r, int val = 1) {
update(l, 1);
update(r + 1, -1);
}
int query(int pos) {
int sum = 0;
while (pos > 0) {
sum += Tree[pos];
pos -= (pos & -pos);
}
return sum;
}
int cumsum[maxn][26];
signed main()
{
int n, m;
cin >> n >> m;
string text, pat;
cin >> text >> pat;
if (n < m) {
cout << 0 << endl;
return 0;
}
if (n == m) {
ll ans = 0;
for (int i = 0; i < n; i++) {
ans += (text[i] != pat[i]);
}
cout << ans << endl;
return 0;
}
for (int i = 1; i <= m; i++) {
cumsum[i][ pat[i - 1] - 'a' ]++;
for (int j = 0; j < 26; j++) {
cumsum[i][j] += cumsum[i - 1][j];
}
}
N = n;
for (int i = 1; i <= n; i++) {
int j = i + m - 1;
if (j > n) {
break;
}
range_update(i, j, 1);
}
int middle = (n + 1) / 2;
ll ans = 0;
for (int i = 0; i < n; i++) {
int add = query(i + 1);
int v = text[i] - 'a';
if (add == m) {
ans += add;
int bad = cumsum[m][v];
ans -= bad;
continue;
}
int len = i + 1;
int st = len - add;
int ed = st + add - 1;
if (st >= m or ed >= m) {
st = m - add;
ed = st + add - 1;
}
{
ans += add;
int bad = cumsum[ed + 1][v] - cumsum[st][v];
ans -= bad;
}
}
cout << ans << endl;
}
B. Aloyna and Can Buying
signed main()
{
int n, k;
cin >> n >> k;
map <int, int> mp;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
mp[x]++;
}
int maxi = 0;
int ans = -1;
for (auto it : mp) {
if (it.second > maxi) {
maxi = it.second;
ans = it.first;
}
}
cout << ans << endl;
}
D. Poltu and Interesting Number
ll dp[70][10][3];
bool memoize[70][10][3];
int a[70];
ll solve(int pos, int last = 0, bool ok = 0, bool flag = 1, bool take = 0) {
if (pos < 0) {
return (take && ok == 0);
}
ll &ret = dp[pos][last][ok];
bool &mem = memoize[pos][last][ok];
if (!flag && take && mem) {
return ret;
}
int loop = 9;
if (flag) {
loop = a[pos];
}
ll sum = 0;
for (int i = 0; i <= loop; i++) {
if (!take && i == 0) {
sum += solve(pos - 1, 0, 0, 0, 0);
}
else {
sum += solve(pos - 1, i, ok | (i == 0) | (i == last), flag & i == a[pos], 1);
}
}
if (!flag && take) {
mem = 1, ret = sum;
}
return sum;
}
ll digit_dp(ll num) {
int len = 0;
while (num) {
a[len++] = num % 10;
num /= 10;
}
return solve(len-1);
}
signed main()
{
int tc;
cin >> tc;
for (int tcase = 1; tcase <= tc; tcase++) {
ll n;
cin >> n;
ll lo = 1;
ll hi = 1e16;
ll ans = -1;
while (lo <= hi) {
ll mid = lo + (hi - lo) / 2;
ll total = digit_dp(mid);
if (total >= n) {
ans = mid;
hi = mid - 1;
}
else {
lo = mid + 1;
}
}
cout << "Case " << tcase << ": " << ans << endl;
}
}
E. Erik and His Buggy Code
int main() {
printf("2 x 2 = 4");
return 0;
}
F. Poltu and Graph
int par[maxn];
int compo_sze[maxn];
void makeSet() {
for (int i = 1; i < maxn; i++) {
par[i] = i;
compo_sze[i] = 1;
}
}
int findRep(int r) {
if (r == par[r]) {
return r;
}
return par[r] = findRep(par[r]);
}
struct Edge {
int u, v;
long long w;
Edge(int u, int v, ll w)
: u(u), v(v), w(w) {}
bool operator < (const Edge &other) const {
return w < other.w;
}
};
struct Query {
int v;
ll max_weight;
int id;
Query(int v, ll max_weight, int id)
: v(v), max_weight(max_weight), id(id) {}
bool operator < (const Query &other) const {
return max_weight < other.max_weight;
}
};
signed main()
{
int n, m;
cin >> n >> m;
deque <Edge> graph;
for (int e = 1; e <= m; e++) {
int u, v;
ll w;
cin >> u >> v >> w;
graph.emplace_back(u, v, w);
}
sort(graph.begin(), graph.end());
int q;
cin >> q;
vector <Query> queries;
for (int i = 1; i <= q; i++) {
int v;
ll max_weight;
cin >> v >> max_weight;
queries.emplace_back(v, max_weight, i);
}
sort(queries.begin(), queries.end());
vector <int> ans(q + 1);
makeSet();
for (Query it : queries) {
int v = it.v;
int id = it.id;
ll max_weight = it.max_weight;
while (graph.empty() == false and graph.front().w <= max_weight) {
int u = graph.front().u;
int v = graph.front().v;
graph.pop_front();
int p = findRep(u);
int q = findRep(v);
if (p == q) {
continue;
}
par[q] = p;
compo_sze[p] += compo_sze[q];
compo_sze[q] = 0;
}
int p = findRep(v);
ans[id] = compo_sze[p];
}
for (int i = 1; i <= q; i++) {
cout << ans[i] << '\n';
}
}
H. Poltu and Odd Number
int par[maxn];
int compo_sze[maxn];
void makeSet() {
for (int i = 1; i < maxn; i++) {
par[i] = i;
compo_sze[i] = 1;
}
}
int findRep(int r) {
if (r == par[r]) {
return r;
}
return par[r] = findRep(par[r]);
}
struct Edge {
int u, v;
long long w;
Edge(int u, int v, ll w)
: u(u), v(v), w(w) {}
bool operator < (const Edge &other) const {
return w < other.w;
}
};
struct Query {
int v;
ll max_weight;
int id;
Query(int v, ll max_weight, int id)
: v(v), max_weight(max_weight), id(id) {}
bool operator < (const Query &other) const {
return max_weight < other.max_weight;
}
};
signed main()
{
int n, m;
cin >> n >> m;
deque <Edge> graph;
for (int e = 1; e <= m; e++) {
int u, v;
ll w;
cin >> u >> v >> w;
graph.emplace_back(u, v, w);
}
sort(graph.begin(), graph.end());
int q;
cin >> q;
vector <Query> queries;
for (int i = 1; i <= q; i++) {
int v;
ll max_weight;
cin >> v >> max_weight;
queries.emplace_back(v, max_weight, i);
}
sort(queries.begin(), queries.end());
vector <int> ans(q + 1);
makeSet();
for (Query it : queries) {
int v = it.v;
int id = it.id;
ll max_weight = it.max_weight;
while (graph.empty() == false and graph.front().w <= max_weight) {
int u = graph.front().u;
int v = graph.front().v;
graph.pop_front();
int p = findRep(u);
int q = findRep(v);
if (p == q) {
continue;
}
par[q] = p;
compo_sze[p] += compo_sze[q];
compo_sze[q] = 0;
}
int p = findRep(v);
ans[id] = compo_sze[p];
}
for (int i = 1; i <= q; i++) {
cout << ans[i] << '\n';
}
}
I. Palindromic Naming Convention
struct PTree {
int next[27];
int st;
int len;
int sufflink;
PTree(int st = 0, int len = 0, int sufflink = 0)
: st(st), len(len), sufflink(sufflink) {
memset(next, 0, sizeof next);
}
};
PTree Tree[maxn];
int num;
int suff;
void init() {
for (int i = 0; i < maxn; i++) {
Tree[i] = PTree();
}
num = 2;
suff = 2;
Tree[1].len = -1; Tree[1].sufflink = 1;
Tree[2].len = 0; Tree[2].sufflink = 1;
}
bool addLetter(string &s, int pos) {
int cur = suff;
int curlen = 0;
int let = s[pos] - 'a';
while (true) {
curlen = Tree[cur].len;
if (pos - 1 - curlen >= 0 and s[pos - 1 - curlen] == s[pos]) {
break;
}
cur = Tree[cur].sufflink;
}
if (Tree[cur].next[let]) {
suff = Tree[cur].next[let];
return false;
}
++num;
suff = num;
Tree[num].len = Tree[cur].len + 2;
Tree[num].st = pos - Tree[num].len + 1;
Tree[cur].next[let] = num;
if (Tree[num].len == 1) {
Tree[num].sufflink = 2;
return true;
}
while (true) {
cur = Tree[cur].sufflink;
curlen = Tree[cur].len;
if (pos - 1 - curlen >= 0 and s[pos - 1 - curlen] == s[pos]) {
Tree[num].sufflink = Tree[cur].next[let];
break;
}
}
return true;
}
signed main()
{
int tc;
cin >> tc;
for (int tcase = 1; tcase <= tc; tcase++) {
string s;
cin >> s;
init();
int n = s.size();
for (int i = 0; i < n; i++) {
addLetter(s, i);
}
int bad_len = Tree[suff].len;
if (bad_len == n) bad_len = Tree[ Tree[suff].sufflink ].len;
cout << s << ' ';
for (int i = n - bad_len - 1; i >= 0; i--) {
cout << s[i];
}
cout << endl;
}
}
K. Mad Engineering Aksir
ll Tree[maxn];
int N;
void update(int pos, ll val = 1) {
while (pos <= N) {
Tree[pos] += val;
pos += (pos & -pos);
}
}
void range_update(int l, int r, ll val = 1) {
update(l, val);
update(r + 1, -val);
}
ll query(int pos) {
ll sum = 0;
while (pos > 0) {
sum += Tree[pos];
pos -= (pos & -pos);
}
return sum;
}
signed main()
{
int n, q;
cin >> n >> q;
N = n;
while (q--) {
int l, r;
cin >> l >> r;
range_update(l, r);
}
for (int i = 1; i <= n; i++) {
cout << query(i) % 2 << " \n"[i == n];
}
}
M. Most Dificult Problem Ever
signed main()
{
int tc;
cin >> tc;
while (tc--) {
ll a, b, c, l, r;
cin >> a >> b >> c >> l >> r;
ll lo = 1;
ll hi = 1e9;
ll lb = 0;
while (lo <= hi) {
ll mid = (lo + hi) / 2;
ll sum = a * mid * mid + b * mid + c;
if (sum >= l) lb = mid, hi = mid - 1;
else lo = mid + 1;
}
lo = 1;
hi = 1e9;
ll rb = 0;
while (lo <= hi) {
ll mid = (lo + hi) / 2;
ll sum = a * mid * mid + b * mid + c;
if (sum <= r) rb = mid, lo = mid + 1;
else hi = mid - 1;
}
ll ans = rb - lb + 1;
if (lb == 0 or rb == 0) {
ans = 0;
}
cout << ans << endl;
}
}
