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. }


No comments:

Post a Comment

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