Editorial by muhaiminbinmunir

Implementation by DrSwad

#include <bits/stdc++.h>
using namespace std;
 
void test_case() {
  int n;
  cin >> n;
 
  vector<int> h(n);
  for (int &i : h) cin >> i;
 
  vector<int> left_max(n), right_max(n);
 
  for (int i = 0; i < n; i++) {
    if (i == 0) left_max[i] = i;
    else left_max[i] = max(i, left_max[i - 1], [&](int i, int j) { return h[i] < h[j]; });
  }
 
  for (int i = n - 1; i >= 0; i--) {
    if (i == n - 1) right_max[i] = i;
    else right_max[i] = max(i, right_max[i + 1], [&](int i, int j) { return h[i] < h[j]; });
  }
 
  int ans = 0;
 
  for (int i = 0; i < n; i++) {
    ans += min(h[left_max[i]], h[right_max[i]]) - h[i];
  }
 
  cout << ans << "\n";
}
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
 
  int t;
  cin >> t;
 
  for (int cs = 1; cs <= t; cs++) {
    test_case();
  }
 
  return 0;
}

• Amazing Problem
• Good Problem
• Bad Problem
• Didn't Solve

Editorial by adibhossain

Implementation by DrSwad

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
const int A = 1e9;
 
void test_case() {
  int n, k;
  cin >> n >> k;
 
  vector<int> a(n), b(n);
  for (int &i : a) cin >> i;
  for (int &i : b) cin >> i;
 
  auto check = [&](int forms) {
    long long have = k;
    for (int i = 0; i < n; i++) {
      long long need = (ll)forms * a[i] - (ll)b[i];
      if (need > have) return false;
      if (need > 0) have -= need;
    }
    return true;
  };
 
  int L = 0, R = A + 1;
  while (R - L > 1) {
    int mid = (R + L) / 2;
    if (check(mid)) L = mid;
    else R = mid;
  }
 
  cout << L << "\n";
}
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
 
  int t;
  cin >> t;
 
  for (int cs = 1; cs <= t; cs++) {
    test_case();
  }
 
  return 0;
}

• Amazing Problem
• Good Problem
• Bad Problem
• Didn't Solve

Editorial by adibhossain

Implementation by DrSwad

#include <bits/stdc++.h>
using namespace std;
 
void test_case() {
  int n;
  cin >> n;
 
  assert(n % 2 == 0);
 
  vector<int> a(n);
  for (int &i : a) cin >> i;
 
  sort(a.begin(), a.end());
 
  long long ans = 0;
  for (int i = 0; i < n; i += 2) {
    ans += a[i + 1];
  }
 
  cout << ans << "\n";
}
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
 
  int t;
  cin >> t;
 
  for (int cs = 1; cs <= t; cs++) {
    test_case();
  }
 
  return 0;
}

• Amazing Problem
• Good Problem
• Bad Problem
• Didn't Solve

Editorial by adibhossain

Implementation by DrSwad

#include <bits/stdc++.h>
using namespace std;
 
const int N = 1e5 + 5;
 
vector<int> factors[N];
 
void init() {
  for (int div = 1; div < N; div++) {
    for (int mul = div; mul < N; mul += div) {
      factors[mul].push_back(div);
    }
  }
}
 
void test_case() {
  int n, q;
  cin >> n >> q;
 
  set<int> a;
  for (int i = 0; i < n; i++) {
    int v;
    cin >> v;
    a.insert(v);
  }
 
  while (q--) {
    int b;
    cin >> b;
 
    int ans = 0;
 
    for (int div : factors[b]) {
      ans += a.find(div) == a.end();
    }
 
    cout << ans << "\n";
  }
}
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
 
  init();
 
  int t;
  cin >> t;
 
  for (int cs = 1; cs <= t; cs++) {
    test_case();
  }
 
  return 0;
}

• Amazing Problem
• Good Problem
• Bad Problem
• Didn't Solve

Editorial by DrSwad

Implementation by DrSwad

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
 
  int t;
  cin >> t;
 
  while (t--) {
    int n, m;
    cin >> n >> m;
 
    map<int, bool> div_banned;
    for (int d = 1; d * d <= m; d++) {
      if (m % d == 0) {
        div_banned[d] = false;
        div_banned[m / d] = false;
      }
    }
 
    for (int i = 0; i < n; i++) {
      int a;
      cin >> a;
      int g = gcd(a, m);
      div_banned[g] = true;
    }
 
    int ans = 0;
    for (auto it1 = prev(div_banned.end()); ; it1--) {
      bool good = true;
      if (it1->second) good = false;
      for (auto it2 = it1; it2 != div_banned.end(); it2++) {
        if (it2->second and it2->first % it1->first == 0) {
          good = false;
        }
      }
      ans += good;
      if (it1 == div_banned.begin()) break;
    }
 
    cout << ans << "\n";
  }
 
  return 0;
}

• Amazing Problem
• Good Problem
• Bad Problem
• Didn't Solve

Editorial by DrSwad

Implementation by DrSwad

#include <bits/stdc++.h>
using namespace std;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
void test_case() {
  int n, m;
  cin >> n >> m;
  
  vector<vector<int>> constraints;
  vector<vector<pair<int, int>>> adj(n);
  bool okay = true;
 
  for (int i = 0; i < m; i++) {
    int type;
    cin >> type;
 
    if (type == 1) {
      int i, x;
      cin >> i >> x;
      i--;
      constraints.push_back({type, i, x});
    }
    else {
      int i, j, x;
      cin >> i >> j >> x;
      i--, j--;
      constraints.push_back({type, i, j, x});
      adj[i].emplace_back(j, x);
      adj[j].emplace_back(i, x);
    }
  }
 
  vector<int> a(n, -1);
 
  auto check = [&]() {
    for (int q = 0; q < m; q++) {
      int type = constraints[q][0];
      if (type == 1) {
        int i = constraints[q][1];
        int x = constraints[q][2];
        if (a[i] == x) return false;
      }
      else {
        int i = constraints[q][1];
        int j = constraints[q][2];
        int x = constraints[q][3];
        if ((a[i] ^ a[j]) != x) return false;
      }
    }
    return true;
  };
 
  function<void(int)> dfs = [&](int at) {
    for (auto [to, x] : adj[at]) {
      if (a[to] == -1) a[to] = a[at] ^ x, dfs(to);
      if ((a[at] ^ a[to]) != x) okay = false;
    }
  };
 
  uniform_int_distribution<int> uid(0, (1 << 30) - 1);
  auto gen = bind(uid, rng);
 
  do {
    fill(a.begin(), a.end(), -1);
    for (int i = 0; i < n; i++) {
      if (a[i] == -1) {
        a[i] = gen();
        dfs(i);
      }
    }
 
    if (!okay) {
      cout << "No\n";
      return;
    }
  } while (!check());
 
  cout << "Yes\n";
  for (int i = 0; i < n; i++) {
    if (i) cout << " ";
    cout << a[i];
  }
  cout << "\n";
}
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
 
  int t;
  cin >> t;
 
  for (int cs = 1; cs <= t; cs++) {
    test_case();
  }
 
  return 0;
}

• Amazing Problem
• Good Problem
• Bad Problem
• Didn't Solve

Editorial by adibhossain

Implementation by RF_Faisal

#include<bits/stdc++.h>
using namespace std;
 
signed main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int tc; cin>>tc;
    while(tc--){
        string s; cin>>s;
 
        string inv = "zxcvbnm";
        for(int i=0; i<s.size(); ++i){
            if(inv.find(s[i]) == string::npos)
                cout<<s[i];
        }
        cout<<'\n';
    }
}

• Amazing Problem
• Good Problem
• Bad Problem
• Didn't Solve

Editorial by adibhossain

Implementation by asif3058

#include<iostream>
using namespace std;
 
long long answer[100010];
int MOD=1000000007;
void answer_generator ()
{
    for (int i=0; i<=100007; i++)
    {
        if (i==0)
            answer[i]=0;
        else if (i<4)
            answer[i]=1;
        else
            answer[i]=(answer[i-1]+answer[i-3])%MOD;
    }
}
 
int main ()
{
 
    answer_generator();
    int t, n, k;
    cin>>t;
    for (int i=0; i<t; i++)
    {
        cin>>k>>n;
        long long output = (((2*k)%MOD) * (answer[n]%MOD))%MOD;
        cout<<"Case "<<i+1<<": "<<output<<endl;
    }
}

• Amazing Problem
• Good Problem
• Bad Problem
• Didn't Solve

Editorial by samee.sevas

Implementation by DrSwad

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,
    tree_order_statistics_node_update>
    ordered_set;

void test_case() {
  ordered_set st;
  int n, q;
  cin >> n >> q;

  vector<int> key(n + 1, 0);
  for (int i = 1; i <= n; i++) {
    int c;
    cin >> c;
    if (key[c] == 0) key[c] = i;
    st.insert(i);
  }

  int lowest_key = -1;
  while(q--) {
    int d;
    cin >> d;
    int ans = st.order_of_key(key[d]);
    cout << ans + 1 << "\n";

    st.erase(st.find(key[d]));
    st.insert(lowest_key);
    key[d] = lowest_key;
    lowest_key--;
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int t;
  cin >> t;

  for (int cs = 1; cs <= t; cs++) {
    test_case();
  }

  return 0;
}

• Amazing Problem
• Good Problem
• Bad Problem
• Didn't Solve

Editorial by RF_Faisal

Implementation by DrSwad

#include <bits/stdc++.h>
using namespace std;
 
/**
 * Time: O(E + V)
 * Usage: scc(graph, [\&](vector<int>\& v) { ... }) visits all
 * components in reverse topological order. comp[i] holds the
 * component index of a node (a component only has edges to components
 * with lower index). ncomps will contain the number of components.
 * Everything 0-indexed.
 */
 
vector<int> val, comp, z, cont;
int Time, ncomps;
template <class F>
int dfs(int j, vector<vector<int>> &g, F &f) {
  int low = val[j] = ++Time, x;
  z.push_back(j);
  for (auto e : g[j]) {
    if (comp[e] < 0) {
      low = min(low, val[e] ?: dfs(e, g, f));
    }
  }
 
  if (low == val[j]) {
    do {
      x = z.back();
      z.pop_back();
      comp[x] = ncomps;
      cont.push_back(x);
    } while (x != j);
    f(cont);
    cont.clear();
    ncomps++;
  }
  return val[j] = low;
}
template <class F>
void scc(vector<vector<int>> &g, F f) {
  int n = (int)g.size();
  val.assign(n, 0);
  comp.assign(n, -1);
  Time = ncomps = 0;
  for (int i = 0; i < n; i++) {
    if (comp[i] < 0) dfs(i, g, f);
  }
}
 
void test_case() {
  int n, m;
  cin >> n >> m;
 
  vector<vector<int>> g(n);
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    g[u].push_back(v);
  }
  
  vector<int> comps;
  scc(g, [&](vector<int> comp) { comps.push_back(comp.size()); });
 
  sort(comps.begin(), comps.end(), greater<int>());
  int ans = comps.size() == 1 ? comps[0] : comps[0] + comps[1];
 
  cout << ans << "\n";
}
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
 
  int t;
  cin >> t;
 
  for (int cs = 1; cs <= t; cs++) {
    test_case();
  }
 
  return 0;
}

• Amazing Problem
• Good Problem
• Bad Problem
• Didn't Solve

Editorial by adibhossain

Implementation by DrSwad

#include <bits/stdc++.h>
using namespace std;
 
const int C = 26;
 
void test_case() {
  int n;
  cin >> n;
 
  vector<string> ss(n);
  for (string &s : ss) cin >> s;
 
  string S;
  cin >> S;
 
  vector<int> char_s(C, -1);
  for (int i = 0; i < n; i++) {
    for (char c : ss[i]) {
      char_s[c - 'a'] = i;
    }
  }
 
  stack<pair<int, int>> st;
  int ans = 1;
 
  for (char c : S) {
    int si = char_s[c - 'a'];
    if (si == -1) {
      ans = -1;
      break;
    }
    const string& s = ss[si];
 
    if (c == s[0]) {
      ans++;
      if (s.length() > 1) {
        st.emplace(si, 1);
      }
    }
    else {
      if (st.empty() or si != st.top().first) {
        ans = -1;
        break;
      }
 
      int &at = st.top().second;
      if (c != s[at]) {
        ans = -1;
        break;
      }
 
      at++;
      if (at == s.length()) st.pop();
    }
  }
 
  if (!st.empty()) ans = -1;
 
  if (ans == -1) cout << "No\n";
  else cout << "Yes\n" << ans << "\n";
}
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
 
  int t;
  cin >> t;
 
  for (int cs = 1; cs <= t; cs++) {
    test_case();
  }
 
  return 0;
}

• Amazing Problem
• Good Problem
• Bad Problem
• Didn't Solve