#include <bits/stdc++.h>
using namespace std;

struct node {
  int a, b, c;
  node() {}
  node(int a, int b, int c):
    a(a), b(b), c(c) {}
  bool operator < (const node & n) const {
    return a < n.a;
  }
};

int const N = 1e5 + 10;
int t, n, x;
long long cs[N];
node a[N];

int main() {
  scanf("%d", & t);
  while (t-- != 0) {
    scanf("%d %d", & n, & x);
    for (int i = 1; i <= n; ++i)
      scanf("%d %d %d", & a[i].a, & a[i].b, & a[i].c);
    ++n;
    a[n] = node(-1, -1, 0);
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; ++i)
      cs[i] = 1ll * (a[i].b - a[i].a + 1) * a[i].c + cs[i - 1];
    long long best = 0;
    for (int i = 1, nw; i <= n; ++i) {
      nw = a[i].a + x - 1;
      int idx = upper_bound(a + 1, a + n + 1, node(nw, 2e9, 2e9)) - a;
      --idx;
      if (nw >= a[idx].b)
        best = max(best, cs[idx] - cs[i - 1]);
      else
        best = max(best, cs[idx - 1] - cs[i - 1] + 1ll * (nw - a[idx].a + 1) * a[idx].c);
    }
    for (int i = n, nw; i > 0; --i) {
      nw = max(0, a[i].b - x + 1);
      int idx = upper_bound(a + 1, a + n + 1, node(nw, 2e9, 2e9)) - a;
      --idx;
      if (nw <= a[idx].a)
        best = max(best, cs[i] - cs[idx - 1]);
      else
        best = max(best, cs[i] - cs[idx] + 1ll * (a[idx].b - nw + 1) * a[idx].c);
    }
    printf("%lld\n", best);
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define se second
#define fi first
#define pb push_back
const int N = 1001;
ll fans[N];

int main() {
  int t, n;
  ll x;
  scanf("%d", &t);
  while (t--) {
    scanf("%lld%d", &x, &n);
    memset(fans, 0, sizeof fans);
    if (n == 1) {
      cout << x << endl;
      continue;
    }
    for (int i = 1; i <= n && x; i++, x--)
      fans[i]++;
    if (x > 0) {
      ll temp = x / (n - 1), rem = x % (n - 1);
      if (temp & 1) {
        fans[1] += temp / 2 + 1, fans[n] += temp / 2;
        for (int i = 2; i < n; i++)
          fans[i] += temp;
        for (int i = 2; i <= n && rem; i++, rem--)
          fans[i]++;
      }
      else {
        fans[1] += temp / 2, fans[n] += temp / 2;
        for (int i = 2; i < n; i++)
          fans[i] += temp;
        for (int i = n - 1; i >= 0 && rem; i--, rem--)
          fans[i]++;
      }
    }
    for (int i = 1; i <= n; i++) {
      printf("%lld", fans[i]);
      if (i != n)
        printf(" ");
    }
    puts("");
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n;
int main(int argc, char* argv[]) {
  int t;
  scanf("%d", &t);
  while (t--) {
    scanf("%d", &n);
    printf("%d\n", __builtin_popcount(n ^ (n - 1)));
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

long long n, m, tmp, ans;
int T;

int main(int argc, char** argv) {
  cin >> T;
  while (T--) {
    cin >> n >> m;
    if (n > m)
      swap(n, m);
    tmp = m / 2 + 1;
    ans = tmp * (n / 2) + (m + 1 - tmp) * ((n + 1) / 2);
    cout << ans << endl;
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define se second
#define fi first
#define pb push_back
const int N = 1e5 + 5, M = 1e9 + 7;
ll v[N], L[N], R[N];

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    scanf("%d", &n);
    long long fans = 0, sum = 1;
    for (int i = 1; i <= n; i++) {
      scanf("%lld", &v[i]);
      sum = (sum * v[i]) % M;
    }
    fans = (sum * n) % M;
    L[0] = R[n + 1] = 1;
    for (int i = 1; i <= n; i++) {
      L[i] = (L[i - 1] * v[i]) % M;
    }
    for (int i = n; i > 0; i--) {
      R[i] = (R[i + 1] * v[i]) % M;
    }
    for (int i = 1; i <= n; i++) {
      long long temp = (L[i - 1] * R[i + 1]) % M;
      fans = (fans - temp + M) % M;
    }
    printf("%lld\n", fans);
  }
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

int const N = 1e6 + 100;
int const sz = 1e5 + 100;
int t, n, a[sz], freq[N], vis[N];

long long summation() {
  long long sum = 0;
  for (int i = 1; i < N; ++i) {
    if (freq[i]) {
      for (int j = i; j < N; j += i)
        if (freq[j] && !vis[j])
          sum += 1ll * freq[j] * i, vis[j] = 1;
    }
  }
  return sum;
}

int main() {
  scanf("%d", &t);
  while (t--) {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
      scanf("%d", &a[i]);
      ++freq[a[i]];
    }

    printf("%lld\n", summation());
    for (int i = 0; i < n; ++i)
      freq[a[i]] = vis[a[i]] = 0;
  }
  return 0;
}

Let's say we increased the frequency of two characters ch₁ and ch₂, and let's say we increased the frequency of ch₁ by a and ch₂ by b, let's define W₁(i) =  weight of adding i instances of ch₁ and W₂(i) similarly.
Now let's say we want to add one instance of c1 and remove one instance of c2, if W₁(a + 1) - W₁(a) > W₂(b) - W₂(b - 1) then our operation will increase the total weight, also since W₁(a + 2) - W₁(a + 1) > W₁(a + 1) - W₁(a) > W₂(b) - W₂(b - 1) > W₂(b - 1) - W₂(b - 2), we can keep adding a single instance of c1 and removing a single instance of c2, increasing the weight each time until b = 0.
Now if W₁(a + 1) - W₁(a) < W₂(b) - W₂(b - 1) then similarly W₂(b + 1) - W₂(b) > W₁(a) - W₁(a - 1), so we add instances of ch₂ and remove instances of ch₁ instead.
That proofs that it's always optimal to increase the frequency of only a single character, and similarly assume that we have taken a of ch₁ and b of ch₂ such that there are still characters left of both ch₁ and ch₂, then from above we can see that it's optimal to either take all ch₁ or all ch₂ instead of some of both proofing that we should decrease the frequency of some characters to 0 expect for at most one character where we don’t have enough k to take all of it.
Written by Motarack

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5000 + 5, M = 26;
int freq[M], n, k, from, to;
ll dp[N][M], res;
char st[100000 + 5];

ll find(int f, int ch) {
  return f * (f - 1LL) / 2 * (ch + 'a');
}

ll calc(int ch, int rem) {
  if (ch == from || ch == to)
    return calc(ch + 1, rem);
  if (ch == 26) {
    int t = min(rem, freq[from]);
    rem -= t;
    return find(freq[from] - t, from) + find(freq[to] + (k - rem), to);
  }
  ll& ret = dp[rem][ch];
  if (ret != -1)
    return ret;
  ret = find(freq[ch], ch) + calc(ch + 1, rem);
  if (rem - freq[ch] >= 0)
    ret = max(ret, calc(ch + 1, rem - freq[ch]));
  return ret;
}

int main(int argc, char* argv[]) {
  int t;
  scanf("%d", &t);
  while (t--) {
    scanf("%d%d%s", &n, &k, st);
    memset(freq, 0, sizeof freq);
    for (int i = 0; i < n; ++i)
      ++freq[st[i] - 'a'];
    res = 0;
    for (int c1 = 'a'; c1 <= 'z'; ++c1)
      for (int c2 = 'a'; c2 <= 'z'; ++c2) {
        if (c1 == c2)
          continue;
        memset(dp, -1, sizeof dp);
        to = c1 - 'a';
        from = c2 - 'a';
        res = max(res, calc(0, k));
      }
    printf("%lld\n", res);
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1000;
int n, h[N + N], res;
int main(int argc, char* argv[]) {
  int t;
  scanf("%d", &t);
  while (t--) {
    scanf("%d", &n);
    n += n;
    for (int i = 0; i < n; ++i)
      scanf("%d", h + i);
    res = 0;
    for (int i = 0; i < n; ++i)
      res = max(res, h[i] + h[n - i - 1]);
    printf("%d\n", res);
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
int T, x, n, d, mod;

int main(int argc, char** argv) {
  cin >> T;
  while (T--) {
    scanf("%d %d", &x, &n);
    d = x / n;
    if (d == 0) {
      puts("-1");
      continue;
    }
    mod = x % n;
    printf("%d", d);
    for (int i = 1; i + mod < n; ++i)
      printf(" %d", d);
    for (int i = 0; i < mod; ++i)
      printf(" %d", d + 1);
    puts("");
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll go(ll a, ll b, ll v, int i = 59) {
  if (i == -1)
    return 1;
  bool ai = a >> i & 1, bi = b >> i & 1, vi = v >> i & 1;
  if (vi && !ai && !bi)
    return b - a + 1;
  if (!vi && ai && bi)
    return 0;
  if (!vi && !ai && !bi)
    return go(a, b, v, i - 1);
  if (vi && ai && bi)
    return go(a & ~(1ll << i), b & ~(1ll << i), v & ~(1ll << i), i - 1);
  if (!vi && !ai && bi)
    return go(a, (1ll << i) - 1, v, i - 1);
  if (v == (1ll << (i + 1)) - 1)
    return b - a + 1;
  ll c = (1ll << i) - 1;
  return max(c - a + 1, go((c + 1) & ~(1ll << i), b & ~(1ll << i), v & ~(1ll << i), i - 1));
}

int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    ll a, b, v;
    scanf("%lld%lld%lld", &a, &b, &v);
    printf("%lld\n", go(a, b, v));
  }
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f(i, x, n) for (int i = x; i < (int)(n); ++i)

int const N = 1000;
double const eps = 1e-7;

struct V {
  double x, y;
  V() {}
  void sc() { scanf("%lf%lf", &x, &y); }
  V(double a, double b) : x(a), y(b) { }
  V operator+(V o) { return V(x + o.x, y + o.y); }
  V operator-(V o) { return V(x - o.x, y - o.y); }
  double L() { return sqrt(x * x + y * y); }
  V N() {
    double l = L();
    return V(x / l, y / l);
  }
  V rot(double th) { return V(x * cos(th) - y * sin(th), x * sin(th) + y * cos(th)); }
  V operator*(double z) { return V(x * z, y * z); }
  double operator*(V o) { return x * o.x + y * o.y; }
  double operator|(V o) { return x * o.y - o.x * y; }
  void pr() { printf("%lf %lf\n", x, y); }
} p[N];

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

int main() {
  int t;
  cin >> t;
  while (t--) {
    bool dn = false;
    int n, m;
    double z;
    scanf("%d%d%lf", &n, &m, &z);
    z /= 2.0;
    f(i, 0, n) p[i].sc();
    f(i, 0, n) {
      V dv = p[i];
      double l = dv.L();
      V c;
      if (l <= z)
        c = dv.N();
      else {
        double th = acos(z / l);
        c = dv.rot(th).N();
      }
      int ins = 1;
      f(j, 0, n) if (i != j) {
        V d = p[j];
        double t = abs(d * c);
        if (t - eps <= z && (d | c) > -eps)
          ++ins;
      }
      if (ins >= m) {
        printf("Yes\n");
        dn = true;
        break;
      }
    }
    if (!dn)
      printf("No\n");
  }
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 10000 + 1, M = 5 + 1, MOD = 1000000007;
int dp[M][N][2][3][4][5];
int n, m, k, lim;

int p[5], vl[6];
void fix() {
  memset(vl, 0, sizeof vl);
  for (int i = 0, idx = 1; i < 5; ++i) {
    if (vl[p[i]] != 0)
      p[i] = vl[p[i]] - 1;
    else
      vl[p[i]] = idx, p[i] = idx++ - 1;
  }
}

int calc(int i, int j, int p2, int p3, int p4, int p5) {
  if (i == n)
    return calc(0, j + 1, p2, p3, p4, p5);
  if (j == m)
    return 1;
  int& ret = dp[i][j][p2][p3][p4][p5];
  if (ret != -1)
    return ret;
  ret = 0;
  int lft = (n == 5 ? 0 : (n == 4 ? p2 : (n == 3 ? p3 : (n == 2 ? p4 : p5))));
  for (int val = 0; val < lim; ++val) {
    if (val == lft && j != 0)
      continue;
    if (val == p5 && i != 0)
      continue;
    p[0] = p2, p[1] = p3, p[2] = p4, p[3] = p5, p[4] = val;
    fix();
    ret = (ret + (val == 5 ? k - 5LL : 1LL) * calc(i + 1, j, p[1], p[2], p[3], p[4])) % MOD;
  }
  return ret;
}

int main(int argc, char* argv[]) {
  int t;
  scanf("%d", &t);
  while (t--) {
    scanf("%d%d%d", &n, &m, &k);
    lim = min(k, 6);
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < m; ++j)
        memset(dp[i][j], -1, sizeof dp[i][j]);
    printf("%d\n", calc(0, 0, 0, 0, 0, 0));
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pp;
int const N = 1e5 + 10, oo = 1e9;
int mod = oo + 7;
ll const OO = 1e18;
int t, n, q;
vector<vector<int> > from_root, dp;
vector<int> dep;
vector<vector<pair<int, pp> > > adj;

void dfs(int u, int p = 0, ll cs1 = 0, ll cs2 = 0) {
  from_root[0][u] = cs1;
  from_root[1][u] = cs2;
  dp[u][0] = p;
  for (auto v : adj[u]) {
    if (v.first == p)
      continue;
    int a = v.second.first, b = v.second.second;
    dep[v.first] = dep[u] + 1;
    dfs(v.first, u, cs1 + a, cs2 + b);
  }
}

int lca(int a, int b) {
  if (dep[a] > dep[b])
    swap(a, b);
  for (int i = 18; i > -1; i--)
    if (dep[b] - (1 << i) >= dep[a])
      b = dp[b][i];
  if (b == a)
    return a;
  for (int i = 18; i > -1; i--) {
    if (dp[a][i] != dp[b][i]) {
      a = dp[a][i];
      b = dp[b][i];
    }
  }
  return dp[a][0];
}

int main() {
  scanf("%d", &t);
  while (t--) {
    scanf("%d", &n);
    dp = vector<vector<int> >(n + 1, vector<int>(19));
    from_root = vector<vector<int> >(2, vector<int>(n + 1));
    dep = vector<int>(n + 1);
    adj = vector<vector<pair<int, pp> > >(n + 1);
    ll sumAll = 0;
    for (int i = 0; i < n - 1; i++) {
      int u, v, a, b;
      scanf("%d%d%d%d", &u, &v, &a, &b);
      adj[u].push_back({ v, { a, b } });
      adj[v].push_back({ u, { b, a } });
      sumAll += a + b;
    }
    dfs(1);
    scanf("%d", &q);
    for (int j = 1; j < 19; j++)
      for (int i = 1; i <= n; i++)
        if (dp[i][j - 1])
          dp[i][j] = dp[dp[i][j - 1]][j - 1];
    while (q--) {
      int u, v;
      scanf("%d%d", &u, &v);
      int lc = lca(u, v);
      printf("%lld\n", sumAll - from_root[1][v] + from_root[1][lc] - from_root[0][u] + from_root[0][lc]);
    }
  }
  return 0;
}

Due to symmetry, the answer of n m is equal to the answer of -n m, so work with the absolute value of n.

We are looking for the probability of starting at position 0 and ending at n positions to the right, using m moves.

A move goes to Right with probability and Left with probability , we can imagine we have a binary string of instructions of length m (executed one by one), where 0 means go left and 1 means go right. because of this discrete uniform distribution, every unique binary string of length m will have a probability of as we have 2^m different strings.

So the answer will be the number of such strings that x - y = n where x is the number of 1's and y is the number of 0's, with some work on paper you can find that . Now the probability will be where mCx means m Choose x. You can handle the output format using the multiplicative inverse.

If m - n is odd or negative then the answer is 0.

We need n numbers that sums up to n × a so that their average is equal to a.

To choose the numbers to be the most distinct, we want to include as many smaller distinct number as possible so we will take numbers: 1, 2, 3 ..., x so that their summation is n × a, we can find x using Binary Search.
Why is it better to choose smaller numbers? because if we replace a small number with a bigger number, then we get closer to n × a thus less chances to use more distinct numbers.

A problem arise when there is no summation from 1 to x that is equal to n × a, so we choose a summation less than n × a, and what's left will be equal to which will be distributed on n - x unused numbers (because we already used x numbers).
So at least we can give each of the n - x numbers a value of 1 since values must be positive, so must be at least equal to n - x which will be our Binary Search condition which makes x a valid answer.

The answer is the number of possible values for a multiplied by the number of possible values for b.

We can see that we can use any value for b from 1 to m - 1, thus m - 1 possible values for b, as for a, we can only use a value x that has a multiplicative inverse in respect to the module m which means x and m are co-primes, and the number of positive numbers co-primes with m less than m are calculated using the totient function. so the final answer is (m - 1) × Totient(m).

Since the number of nodes are so low, you can work on all different subsets of nodes.

One solution is a minimization Dynamic Programming, with state holding only a mask telling which nodes are already included in the spanning tree, and try to include any un-included node that can connect directly to one of the included nodes until all the important nodes are in the tree.

Another slower solution is to find all the subsets of nodes that include all the important nodes, and do an MST for each of them and take the minimum.

Minimize when the condition mentioned in the statement applies :)

Since values are small, as well as the grid size, we can make a frequency array for every cell in a grid and make a 2D cumulative summation on every frequency array, this way we can get the frequency of a number in the sub-rectangle in O(1).

For every query, loop over each number from 1 to 500 and find its frequency in that sub-rectangle, as we count the sum of the frequencies we know the median is at the element that makes the sum exceed half the size of the rectangle.

The solution above gets AC, but to make the solution faster, we can do a cumulative summation on the frequency arrays so then we can binary search the point where the sum exceeds half the size of the sub-rectangle instead of looping over them.

Notice that abcd is a cyclic quadrilateral, which means its vertices all lie on a single circle.

A property for cyclic quadrilateral is that its opposite angles are supplementary. https://en.wikipedia.org/wiki/Cyclic_quadrilateral#Characterizations

With some work on paper we can find that the 2 triangles which areas are given are similar, thus the similarity ratio can be calculated using the areas: , from which we can find and then x and y.

Keep track of the number of different opposite characters, and at the end of each query add 1 to the answer if the number of different opposite characters is zero.

Read problem statement carefully to handle the cases where both teams have the same number of goals overall.

You can solve this problem by brute forcing on the numbers from b down to a until you find a solution, this solution is valid and won't cause a Time Limit Exceeded.

Why no TLE? because the biggest gap between any 2 consecutive 9 digits primes (half of the given number) is less than 320, so at most you will loop 320 times and find the second half of the number to be a prime and the GCD between a prime and any other number is 1, unless the other number is a multiple of that prime. but even if it is, the next prime number below that will work because if the first half is a multiple of both primes then it can't only be 9 digits (must be 18 digits if both primes are 9 digits). https://en.wikipedia.org/wiki/Prime_gap#Numerical_results

Show me your implementation powers :P

Consider each bit on its own since the AND operation is bit-wise.

For each bit, notice that any sub-array that has a zero bit will add nothing to the answer.

For each bit, A sub-array of only ones of length X has sub-array of only ones, and each of them will add 2^W where W is the Weight of the bit to the answer.

You can construct the array from only one known element.

All numbers are less than 10⁹ + 7, so the summation of any 2 numbers is either less than 10⁹ + 7 or less than 2 × (10⁹ + 7).

Sort the elements and for each element use binary search to handle each of the cases above to find the best answer.

To make things easier, use the following concept: Let's make a function F(N) that finds the answer of range [0, N], then the answer of range [L, R] would be: F(R) - F(L - 1).

Make a frequency array of the original string then find how many times the string was repeated from 0 to N, the number of times is where |S| is the length of the original string.

If is not zero then we have extra characters that doesn't make a full string, we can make 26 frequency arrays for each letter in alphabet and do a prefix sum to get the number of times a specific letter was repeated in the first letters of the original string.

Meet in the middle, divide the dice into 2 groups of equal sizes and brute force each part on it's own and store the in 2 vectors V₁, V₂.

For each element in V₁, we must find how many elements in V₂ satisfies the equality: .

Let's call the element from V₁ as A and the element from V₂ as B and we want to find the value of B:
.
multiply both sides by :
.
where is the inverse of A respective to the mod 10⁹ + 7.
Since all values of V₂ are below 10⁹ + 7, then there's only one value for B in V₂ that satisfies the equality (because all values B + K(10⁹ + 7) satisfies the equality for any natural number K).
So we will calculate the value of B and check how many times was it repeated in V₂.

Find the number of palindrome sub-strings for each string, using an algorithm that runs worse than O(L²) gives TLE where L is the length of the string.

The problem is now reduces to RMQ (Range Max Query), we can now use data structures like Sparse Table, Segment Tree ... but Sparse Table is preferred as it runs faster than Segment Tree.

We still have a problem that the queries are given as strings not indices, to solve this we can map the strings to their indices, but using a map of strings will give TLE as the factor for comparing strings isn't small, to solve this was can use Hashing or Trie to get the index of the string fast.
Hashing will take O(L + log(N)) per query to hash and look for the hash value in a map of hash values.
Trie will take only O(L) per query to track the string in the Trie, but Trie needs pre-construction of O(LN).

Construct 2 arrays, MX and MN where MX_i is the maximum value in the range [1, i] and MN_i is the minimum value in range [i, N].

For each element X, if the max value before it is less than X and the min value after it is more than X then add one to the answer.

Count the number of ones on the border, let's call it Y.

There are total of X = N + N + M + M - 4 border cells, the answer is X - Y.

There is no solution when the total number of ones in the whole image is less than X, then we can't cover the whole border with ones.

Construct a graph, add edge from cell i to cell i + 1 and from cell i to cell j where cell j has same color of cell i and there are no cells between i and j that also have the same color.

Using dynamic programming dp_i = 1 + min(dp_i + 1, dp_nexti), try to jump to the next cell or to the first call that has the same color.

To be able to find this solution, you need to work on a paper, let's suppose we want to find the answer for 3 numbers, A B and C.
The terms of those 3 will be:
A + B + C + AB + AC + BC + ABC
Take C as a common factor from the terms that has C:
A + B + AB + C(1 + A + B + AB)
Notice that if X = A + B + AB then:
X + C(1 + X)
Now take B as a common factor as well:
A + B(1 + A) + C(1 + A + B(1 + A))
Suppose the answer for the problem is X, we can notice that if we add a new number Y, the answer will be X + Y(1 + X).

Using dynamic programming, dp_i = dp_i + 1 + A_i × dp_i + 1, the DP tries to either take the element or not, we will have to subtract 1 from the answer as the DP will consider the empty sub-set as valid sub-set which will add one to the wanted answer.

If there are more than one letter with odd frequency then we can't make any palindromes.

Since the limits are too small, we can brute force and build all the palindromes, since the first half of the palindrome is the same as the second half but reversed, we can only generate all the palindromes by generating the first half only, make a string containing half of the frequency for each letter in the original string and use next_permutation to check how many different permutations you can get.

There's also another faster solution if the constraints were bigger, to know how many different ways we form a string using half of the letters to make the first half of the palindrome, the answer will be: , to eliminate the repeated permutations we divide by the factorial of half of the frequencies for each letter, basic counting math.