Monday, August 31, 2020

Replay of BSMRSTU Intra University Programming Contest 2019 


Contest : Replay of BSMRSTU Intra University Programming Contest 2019
Link    : https://toph.co/c/bsmrstu-intra-2019-r

A. Hamming Distance
  1. const int maxn = 2e6 + 5;
  2.  
  3. int Tree[maxn];
  4. int N;
  5.  
  6. void update(int pos, int val = 1) {
  7.       while (pos <= N) {
  8.             Tree[pos] += val;
  9.             pos += (pos & -pos);
  10.       }
  11. }
  12.  
  13. void range_update(int l, int r, int val = 1) {
  14.       update(l, 1);
  15.       update(r + 1, -1);
  16. }
  17.  
  18. int query(int pos) {
  19.       int sum = 0;
  20.       while (pos > 0) {
  21.             sum += Tree[pos];
  22.             pos -= (pos & -pos);
  23.       }
  24.       return sum;
  25. }
  26.  
  27. int cumsum[maxn][26];
  28.  
  29. signed main()
  30. {
  31.       int n, m;
  32.       cin >> n >> m;
  33.       string text, pat;
  34.       cin >> text >> pat;
  35.       if (n < m) {
  36.             cout << 0 << endl;
  37.             return 0;
  38.       }
  39.       if (n == m) {
  40.             ll ans = 0;
  41.             for (int i = 0; i < n; i++) {
  42.                   ans += (text[i] != pat[i]);
  43.             }
  44.             cout << ans << endl;
  45.             return 0;
  46.       }
  47.       for (int i = 1; i <= m; i++) {
  48.             cumsum[i][ pat[i - 1] - 'a' ]++;
  49.             for (int j = 0; j < 26; j++) {
  50.                   cumsum[i][j] += cumsum[i - 1][j];
  51.             }
  52.       }
  53.       N = n;
  54.       for (int i = 1; i <= n; i++) {
  55.             int j = i + m - 1;
  56.             if (j > n) {
  57.                   break;
  58.             }
  59.             range_update(i, j, 1);
  60.       }
  61.       int middle = (n + 1) / 2;
  62.       ll ans = 0;
  63.       for (int i = 0; i < n; i++) {
  64.             int add = query(i + 1);
  65.             int v = text[i] - 'a';
  66.             if (add == m) {
  67.                   ans += add;
  68.                   int bad = cumsum[m][v];
  69.                   ans -= bad;
  70.                   continue;
  71.             }
  72.             int len = i + 1;
  73.             int st = len - add;
  74.             int ed = st + add - 1;
  75.             if (st >= m or ed >= m) {
  76.                   st = m - add;
  77.                   ed = st + add - 1;
  78.             }
  79.             {
  80.                   ans += add;
  81.                   int bad = cumsum[ed + 1][v] - cumsum[st][v];
  82.                   ans -= bad;
  83.             }
  84.       }
  85.       cout << ans << endl;
  86. }
B. Aloyna and Can Buying
  1. signed main()
  2. {
  3.       int n, k;
  4.       cin >> n >> k;
  5.       map <int, int> mp;
  6.       for (int i = 0; i < n; i++) {
  7.             int x;
  8.             cin >> x;
  9.             mp[x]++;
  10.       }
  11.       int maxi = 0;
  12.       int ans = -1;
  13.       for (auto it : mp) {
  14.             if (it.second > maxi) {
  15.                   maxi = it.second;
  16.                   ans = it.first;
  17.             }
  18.       }
  19.       cout << ans << endl;
  20. }
D. Poltu and Interesting Number
  1. ll dp[70][10][3];
  2. bool memoize[70][10][3];
  3. int a[70];
  4.  
  5. ll solve(int pos, int last = 0, bool ok = 0, bool flag = 1, bool take = 0) {
  6.       if (pos < 0) {
  7.             return (take && ok == 0);
  8.       }
  9.       ll &ret = dp[pos][last][ok];
  10.       bool &mem = memoize[pos][last][ok];
  11.       if (!flag && take && mem) {
  12.             return ret;
  13.       }
  14.       int loop = 9;
  15.       if (flag) {
  16.             loop = a[pos];
  17.       }
  18.       ll sum = 0;
  19.       for (int i = 0; i <= loop; i++) {
  20.             if (!take && i == 0) {
  21.                   sum += solve(pos - 1, 0, 0, 0, 0);
  22.             }
  23.             else {
  24.                   sum += solve(pos - 1, i, ok | (i == 0) | (i == last), flag & i == a[pos], 1);
  25.             }
  26.       }
  27.       if (!flag && take) {
  28.             mem = 1, ret = sum;
  29.       }
  30.       return sum;
  31. }
  32.  
  33. ll digit_dp(ll num) {
  34.       int len = 0;
  35.       while (num) {
  36.             a[len++] = num % 10;
  37.             num /= 10;
  38.       }
  39.       return solve(len-1);
  40. }
  41.  
  42. signed main()
  43. {
  44.       int tc;
  45.       cin >> tc;
  46.       for (int tcase = 1; tcase <= tc; tcase++) {
  47.             ll n;
  48.             cin >> n;
  49.             ll lo = 1;
  50.             ll hi = 1e16;
  51.             ll ans = -1;
  52.             while (lo <= hi) {
  53.                   ll mid = lo + (hi - lo) / 2;
  54.                   ll total = digit_dp(mid);
  55.                   if (total >= n) {
  56.                         ans = mid;
  57.                         hi = mid - 1;
  58.                   }
  59.                   else {
  60.                         lo = mid + 1;
  61.                   }
  62.             }
  63.             cout << "Case " << tcase << ": " << ans << endl;
  64.       }
  65. }
E. Erik and His Buggy Code
  1. int main() {
  2.     printf("2 x 2 = 4");
  3.     return 0;
  4. }
F. Poltu and Graph
  1. int par[maxn];
  2. int compo_sze[maxn];
  3.  
  4. void makeSet() {
  5.       for (int i = 1; i < maxn; i++) {
  6.             par[i] = i;
  7.             compo_sze[i] = 1;
  8.       }
  9. }
  10.  
  11. int findRep(int r) {
  12.       if (r == par[r]) {
  13.             return r;
  14.       }
  15.       return par[r] = findRep(par[r]);
  16. }
  17.  
  18. struct Edge {
  19.       int u, v;
  20.       long long w;
  21.       Edge(int u, int v, ll w) 
  22.             : u(u), v(v), w(w) {}
  23.  
  24.       bool operator < (const Edge &other) const {
  25.             return w < other.w;
  26.       }
  27. };
  28.  
  29. struct Query {
  30.       int v;
  31.       ll max_weight;
  32.       int id;
  33.       Query(int v, ll max_weight, int id) 
  34.             : v(v), max_weight(max_weight), id(id) {}
  35.  
  36.       bool operator < (const Query &other) const {
  37.             return max_weight < other.max_weight;
  38.       }
  39. };
  40.  
  41. signed main()
  42. {
  43.       int n, m;
  44.       cin >> n >> m;
  45.       deque <Edge> graph;
  46.       for (int e = 1; e <= m; e++) {
  47.             int u, v;
  48.             ll w;
  49.             cin >> u >> v >> w;
  50.             graph.emplace_back(u, v, w);
  51.       }
  52.       sort(graph.begin(), graph.end());
  53.       int q;
  54.       cin >> q;
  55.       vector <Query> queries;
  56.       for (int i = 1; i <= q; i++) {
  57.             int v;
  58.             ll max_weight;
  59.             cin >> v >> max_weight;
  60.             queries.emplace_back(v, max_weight, i);
  61.       }
  62.       sort(queries.begin(), queries.end());
  63.       vector <int> ans(q + 1);
  64.       makeSet();
  65.       for (Query it : queries) {
  66.             int v = it.v;
  67.             int id = it.id;
  68.             ll max_weight = it.max_weight;
  69.             while (graph.empty() == false and graph.front().w <= max_weight) {
  70.                   int u = graph.front().u;
  71.                   int v = graph.front().v;
  72.                   graph.pop_front();
  73.                   int p = findRep(u);
  74.                   int q = findRep(v);
  75.                   if (p == q) {
  76.                         continue;
  77.                   }
  78.                   par[q] = p;
  79.                   compo_sze[p] += compo_sze[q];
  80.                   compo_sze[q] = 0;
  81.             }
  82.             int p = findRep(v);
  83.             ans[id] = compo_sze[p];
  84.       }
  85.       for (int i = 1; i <= q; i++) {
  86.             cout << ans[i] << '\n';
  87.       }
  88. }
H. Poltu and Odd Number
  1. int par[maxn];
  2. int compo_sze[maxn];
  3.  
  4. void makeSet() {
  5.       for (int i = 1; i < maxn; i++) {
  6.             par[i] = i;
  7.             compo_sze[i] = 1;
  8.       }
  9. }
  10.  
  11. int findRep(int r) {
  12.       if (r == par[r]) {
  13.             return r;
  14.       }
  15.       return par[r] = findRep(par[r]);
  16. }
  17.  
  18. struct Edge {
  19.       int u, v;
  20.       long long w;
  21.       Edge(int u, int v, ll w) 
  22.             : u(u), v(v), w(w) {}
  23.  
  24.       bool operator < (const Edge &other) const {
  25.             return w < other.w;
  26.       }
  27. };
  28.  
  29. struct Query {
  30.       int v;
  31.       ll max_weight;
  32.       int id;
  33.       Query(int v, ll max_weight, int id) 
  34.             : v(v), max_weight(max_weight), id(id) {}
  35.  
  36.       bool operator < (const Query &other) const {
  37.             return max_weight < other.max_weight;
  38.       }
  39. };
  40.  
  41. signed main()
  42. {
  43.       int n, m;
  44.       cin >> n >> m;
  45.       deque <Edge> graph;
  46.       for (int e = 1; e <= m; e++) {
  47.             int u, v;
  48.             ll w;
  49.             cin >> u >> v >> w;
  50.             graph.emplace_back(u, v, w);
  51.       }
  52.       sort(graph.begin(), graph.end());
  53.       int q;
  54.       cin >> q;
  55.       vector <Query> queries;
  56.       for (int i = 1; i <= q; i++) {
  57.             int v;
  58.             ll max_weight;
  59.             cin >> v >> max_weight;
  60.             queries.emplace_back(v, max_weight, i);
  61.       }
  62.       sort(queries.begin(), queries.end());
  63.       vector <int> ans(q + 1);
  64.       makeSet();
  65.       for (Query it : queries) {
  66.             int v = it.v;
  67.             int id = it.id;
  68.             ll max_weight = it.max_weight;
  69.             while (graph.empty() == false and graph.front().w <= max_weight) {
  70.                   int u = graph.front().u;
  71.                   int v = graph.front().v;
  72.                   graph.pop_front();
  73.                   int p = findRep(u);
  74.                   int q = findRep(v);
  75.                   if (p == q) {
  76.                         continue;
  77.                   }
  78.                   par[q] = p;
  79.                   compo_sze[p] += compo_sze[q];
  80.                   compo_sze[q] = 0;
  81.             }
  82.             int p = findRep(v);
  83.             ans[id] = compo_sze[p];
  84.       }
  85.       for (int i = 1; i <= q; i++) {
  86.             cout << ans[i] << '\n';
  87.       }
  88. }
I. Palindromic Naming Convention
  1. struct PTree {
  2.       int next[27];
  3.       int st;
  4.       int len;
  5.       int sufflink;
  6.       PTree(int st = 0, int len = 0, int sufflink = 0)
  7.             : st(st), len(len), sufflink(sufflink) {
  8.                   memset(next, 0, sizeof next);
  9.             }
  10. };
  11.  
  12. PTree Tree[maxn];
  13. int num;
  14. int suff;
  15.  
  16. void init() {
  17.       for (int i = 0; i < maxn; i++) {
  18.             Tree[i] = PTree();
  19.       }
  20.       num = 2;
  21.       suff = 2;
  22.       Tree[1].len = -1; Tree[1].sufflink = 1;
  23.       Tree[2].len = 0; Tree[2].sufflink = 1;
  24. }
  25.  
  26. bool addLetter(string &s, int pos) {
  27.       int cur = suff;
  28.       int curlen = 0;
  29.       int let = s[pos] - 'a';
  30.       while (true) {
  31.             curlen = Tree[cur].len;
  32.             if (pos - 1 - curlen >= 0 and s[pos - 1 - curlen] == s[pos]) {
  33.                   break;
  34.             }
  35.             cur = Tree[cur].sufflink;
  36.       }
  37.       if (Tree[cur].next[let]) {
  38.             suff = Tree[cur].next[let];
  39.             return false;
  40.       }
  41.       ++num;
  42.       suff = num;
  43.       Tree[num].len = Tree[cur].len + 2;
  44.       Tree[num].st = pos - Tree[num].len + 1;
  45.       Tree[cur].next[let] = num;
  46.       if (Tree[num].len == 1) {
  47.             Tree[num].sufflink = 2;
  48.             return true;
  49.       }
  50.       while (true) {
  51.             cur = Tree[cur].sufflink;
  52.             curlen = Tree[cur].len;
  53.             if (pos - 1 - curlen >= 0 and s[pos - 1 - curlen] == s[pos]) {
  54.                   Tree[num].sufflink = Tree[cur].next[let];
  55.                   break;
  56.             }
  57.       }
  58.       return true;
  59. }
  60.  
  61. signed main()
  62. {
  63.       int tc;
  64.       cin >> tc;
  65.       for (int tcase = 1; tcase <= tc; tcase++) {
  66.             string s;
  67.             cin >> s;
  68.             init();
  69.             int n = s.size();
  70.             for (int i = 0; i < n; i++) {
  71.                   addLetter(s, i);
  72.             }
  73.             int bad_len = Tree[suff].len;
  74.             if (bad_len == n) bad_len = Tree[ Tree[suff].sufflink ].len;
  75.             cout << s << ' ';
  76.             for (int i = n - bad_len - 1; i >= 0; i--) {
  77.                   cout << s[i];
  78.             }
  79.             cout << endl;
  80.       }
  81. }
K. Mad Engineering Aksir
  1. ll Tree[maxn];
  2. int N;
  3.  
  4. void update(int pos, ll val = 1) {
  5.       while (pos <= N) {
  6.             Tree[pos] += val;
  7.             pos += (pos & -pos);
  8.       }
  9. }
  10.  
  11. void range_update(int l, int r, ll val = 1) {
  12.       update(l, val);
  13.       update(r + 1, -val);
  14. }
  15.  
  16. ll query(int pos) {
  17.       ll sum = 0;
  18.       while (pos > 0) {
  19.             sum += Tree[pos];
  20.             pos -= (pos & -pos);
  21.       }
  22.       return sum;
  23. }
  24.  
  25. signed main()
  26. {
  27.      int n, q;
  28.      cin >> n >> q;
  29.      N = n;
  30.      while (q--) {
  31.             int l, r;
  32.            cin >> l >> r;
  33.            range_update(l, r);
  34.      }
  35.      for (int i = 1; i <= n; i++) {
  36.             cout << query(i) % 2 << " \n"[i == n];
  37.      }
  38. }
M. Most Dificult Problem Ever
  1. signed main()
  2. {
  3.       int tc;
  4.       cin >> tc;
  5.       while (tc--) {
  6.             ll a, b, c, l, r;
  7.             cin >> a >> b >> c >> l >> r;
  8.             ll lo = 1;
  9.             ll hi = 1e9;
  10.             ll lb = 0;
  11.             while (lo <= hi) {
  12.                   ll mid = (lo + hi) / 2;
  13.                   ll sum = a * mid * mid + b * mid + c;
  14.                   if (sum >= l) lb = mid, hi = mid - 1;
  15.                   else lo = mid + 1;
  16.             }
  17.             lo = 1;
  18.             hi = 1e9;
  19.             ll rb = 0;
  20.             while (lo <= hi) {
  21.                   ll mid = (lo + hi) / 2;
  22.                   ll sum = a * mid * mid + b * mid + c;
  23.                   if (sum <= r) rb = mid, lo = mid + 1;
  24.                   else hi = mid - 1;
  25.             }
  26.             ll ans = rb - lb + 1;
  27.             if (lb == 0 or rb == 0) {
  28.                   ans = 0;
  29.             }
  30.             cout << ans << endl;
  31.       }
  32. }


Posted by at

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.

Subscribe to: Post Comments (Atom)