Welcome to the Editorial of CodelPlus Long 2025.
CodePlus Long Contest is a 2-day coding competition featuring a mix of educational and challenging problems. It allows participants to learn, practice, and compete to enhance their problem-solving skills.
You can attempt the contest here. (Many Original and Challenging problems, you can give it a try :) )
The problems were authored and prepared by pranavsingh0111,Sarvesh0955,Ragnar21,rndascode,ankitgarg2105,utk_09.
We would also like to thank, Rishabh_king for testing.
Author : Sarvesh0955
This problem can be solved in several ways; one approach is as follows:
Graph Construction
Construct a new graph ( nodes n+1 to 2n ) where all edge weights are multiplied by k.
Connect the two graphs such that:
- For each edge u → v with weight w, add an edge u → v+n with weight w × k
or - For every node u, add an edge u → u+n with weight 0
Algorithm
Run the Bellman–Ford algorithm
→ either modify to find max instead of min,
→ or make edge weights negative and then use the standard Bellman–Ford algorithm.
This will help find the maximum score from node 1 to either n or 2n
(since using the operation at most once also includes not using it).
Case for -1
Case for -1 will be when we detect a positive cycle,
but will it be always wrong??
Observation
No, in case the positive cycle does not lie in the path from 1 to n/2n,
we will not print -1 —
i.e., there exists a positive cycle but if we go in that path,
we cannot reach n/2n.
I have used SPFA algo which is modification of Bellman-Ford algo, works in average O(n) worst O(n^2) and in cnt array if value > n it means it was part of the cycle
Author : Sarvesh0955
This is a constructive problem.
Let’s analyze all possible combinations of consecutive bits and how their OR and AND behave.
| Ans[i] | Ans[i+1] | OR (A[i]) | AND (B[i]) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 |
Key Observations
Invalid Combination:
For(OR, AND) = (0, 1)there is no valid configuration.
Hence, if this case appears in the input, the answer is immediately-1.Fixed Configurations:
(OR, AND) = (0, 0)→ Only possible as(0, 0)(OR, AND) = (1, 1)→ Only possible as(1, 1)
So these positions are fixed during construction.
- Flexible Configurations:
For(OR, AND) = (1, 0), there are two valid possibilities:
(0, 1)or(1, 0)
These will be the free bits to be filled later between fixed ones.
- Continuity Constraint:
You cannot have consecutive fixed pairs like:
(00)followed by(11)directly, or(11)followed by(00)
because they contradict continuity in construction.
- Parity Observation:
Between any two fixed configurations:
(00 → 00)or(11 → 11)⇒ only even number of(OR, AND) = (1,0)configurations allowed(00 → 11)or(11 → 00)⇒ only odd number of(OR, AND) = (1,0)configurations allowed
If this parity condition is not met, the answer is -1.
Construction Approach
Check invalid pairs:
If any(OR, AND) = (0, 1)→ print-1.Fix known bits:
Mark all positions where(OR, AND)is(0,0)or(1,1).Check for conflicts:
If any contradiction appears between fixed bits → print-1.Fill middle parts:
- Between two fixed blocks, fill alternately using the parity rule.
- If no fixed blocks exist at all, fill arbitrarily as:
010101...or101010...
- Verification:
After construction, verify that the generated array indeed satisfies all(OR, AND)pairs.
If yes, add the corresponding bit to the final answer.
Mutliple answer can be possible.
Author : ankitgarg2105
- Euler Tour (Tree Flattening)
We perform a DFS and record for each node u:
in[u]: the time we enter u
out[u]: the time we exit u
During the traversal, we build a array by adding each node’s value when entered and again when exited. All nodes in u’s subtree appear in the range [in[u], out[u]], and since each value appears twice, this range’s sum equals twice the subtree sum.
- Segment Tree with Lazy Propagation
We build a Segment Tree over array to handle range operations efficiently:
Type 1 (Sum Query): Query the Segment Tree for [in[a], out[a]] and divide the result by 2.
Type 2 (Flip Query): Flip all values in [in[a], out[a]].
Lazy propagation allows us to handle range updates efficiently. Instead of immediately updating every element in a range, we mark that range with a lazy flag indicating it needs to be flipped later. When the range is accessed, the flip is applied, and the flag is passed down to its children.
Each flip acts as a toggle — flipping twice restores the original values. This approach ensures that both updates and queries on the Segment Tree take only O(log N) time.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define f(i, a, b) for (int i = a; i < b; i++)
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL);
void build(int ind, int lo, int hi, vector<int> &seg, vector<int> &a)
{
if (lo == hi)
{
seg[ind] = a[lo];
return;
}
int mid = lo + (hi - lo) / 2;
build(2 * ind + 1, lo, mid, seg, a);
build(2 * ind + 2, mid + 1, hi, seg, a);
seg[ind] = seg[2 * ind + 1] + seg[2 * ind + 2];
}
void sumrangeupdate(vector<int> &seg, vector<int> &lazy, int ind, int lo, int hi, int l, int r)
{
if (lazy[ind] != 0)
{
seg[ind] = (-seg[ind]);
if (lo != hi)
{
lazy[2 * ind + 1] = 1 - lazy[2 * ind + 1];
lazy[2 * ind + 2] = 1 - lazy[2 * ind + 2];
}
lazy[ind] = 0;
}
if (lo > r || hi < l || lo > hi)
return;
if (l <= lo && hi <= r)
{
seg[ind] = (-seg[ind]);
if (lo != hi)
{
lazy[2 * ind + 1] = 1 - lazy[2 * ind + 1];
lazy[2 * ind + 2] = 1 - lazy[2 * ind + 2];
}
return;
}
int mid = lo + (hi - lo) / 2;
sumrangeupdate(seg, lazy, 2 * ind + 1, lo, mid, l, r);
sumrangeupdate(seg, lazy, 2 * ind + 2, mid + 1, hi, l, r);
seg[ind] = seg[2 * ind + 1] + seg[2 * ind + 2];
}
int querysumlazy(vector<int> &seg, vector<int> &lazy, int ind, int lo, int hi, int l, int r)
{
if (lazy[ind] != 0)
{
seg[ind] = (-seg[ind]);
if (lo != hi)
{
lazy[2 * ind + 1] = 1 - lazy[2 * ind + 1];
lazy[2 * ind + 2] = 1 - lazy[2 * ind + 2];
}
lazy[ind] = 0;
}
if (lo > r || hi < l || lo > hi)
return 0;
if (l <= lo && hi <= r)
{
return seg[ind];
}
int mid = lo + (hi - lo) / 2;
return querysumlazy(seg, lazy, 2 * ind + 1, lo, mid, l, r) + querysumlazy(seg, lazy, 2 * ind + 2, 1 + mid, hi, l, r);
}
void dfs(int node, int par, vector<int> g[], vector<int> &v, vector<int> &a, vector<int> &in, vector<int> &out, int &t)
{
in[node] = t++;
v.pb(a[node]);
for (auto &child : g[node])
{
if (par == child)
continue;
dfs(child, node, g, v, a, in, out, t);
}
out[node] = t++;
v.pb(a[node]);
}
void solve()
{
int n, q;
cin >> n >> q;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
vector<int> g[n];
f(i, 0, n - 1)
{
int u, v;
cin >> u >> v;
u--;
v--;
g[u].pb(v);
g[v].pb(u);
}
vector<int> v;
vector<int> in(n);
vector<int> out(n);
int t = 0;
dfs(0, -1, g, v, a, in, out, t);
vector<int> seg(8 * n);
vector<int> lazy(8 * n, 0);
build(0, 0, 2 * n - 1, seg, v);
while (q--)
{
int type, a;
cin >> type >> a;
a--;
if (type == 1)
{
cout << querysumlazy(seg, lazy, 0, 0, 2 * n - 1, in[a], out[a]) / 2 << endl;
}
else
{
sumrangeupdate(seg, lazy, 0, 0, 2 * n - 1, in[a], out[a]);
}
}
}
signed main()
{
fastio
int T;
cin >> T;
while (T--)
{
solve();
}
return 0;
}
Author : pranavsingh0111
The core idea is that a number x can be formed if and only if the bitwise AND of all numbers in the input array that are bitwise supersets of x is exactly equal to x.
A number y is a superset of x if (x & y) == x. A naive check for each query would be too slow ($$$O(N \times Q)$$$). We can optimize by precomputing the answers using Dynamic Programming.
We define dp[mask] as the bitwise AND of all input numbers that are supersets of mask.
Initialization: For each number a in our input array, we set dp[a] = a.
DP Transition: We iterate downwards from the maximum possible value. For each mask, we update it by taking the AND with its immediate supersets (masks with one additional bit set): dp[mask] &= dp[mask | (1 << i)].
Why this works: By iterating downwards, we ensure that when we process dp[mask], the value for any of its supersets (like dp[mask | (1 << i)]) has already been finalized. This transition correctly incorporates the AND result from those supersets, because any number that is a superset of mask | (1 << i) is also a superset of mask.
Answering Queries: After precomputation, we can answer any query for x in $$$O(1)$$$ time by simply checking if dp[x] == x. If they are equal, the answer is YES.
The precomputation complexity is $$$O(\text{MAX_VAL} \times \text{BITS})$$$ .
#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;
#define int long long
#define endl '\n'
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
// *find_by_order, order_of_key
void solve(){
int n , q ;
cin >> n >> q ;
vector<int> arr(n) ;
for(int i=0 ; i < n ; i++){
cin >> arr[i] ;
}
int mx = (1<<20) ;
vector<int> dp(mx , -1) ;
for(int i=0 ; i<n ; i++){
dp[arr[i]] = arr[i] ;
}
for(int i=mx-1 ; i>=0 ; i--){
for(int bit = 0 ; bit<20 ; bit++){
if(i & (1<<bit)){
dp[i ^ (1<<bit)] &= dp[i] ;
}
}
}
while(q--){
int x ;
cin >> x ;
if(dp[x] == x){
cout<<"Yes"<<endl;
}else{
cout<<"No"<<endl;
}
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t = 1 ;
cin >> t ;
while(t--){
solve();
}
}
Author : Ragnar21
#include <algorithm>
#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;
// #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// order_of_key(k) : no. of elements < k
// *find_by_order(i) : value at index i (0-based)
#define int long long
#define vi vector<ll>
#define vvi vector<vi>
#define pll pair<ll, ll>
#define vp vector<pll>
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define M 1000000007
// #define M 998244353
#define INF 1e18
#define endl "\n"
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define ff first
#define ss second
#define fr(i,s,e) for(ll i = s; i < e; i++)
#define forrr(i,s,e) for(ll i = s; i >= e; i--)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define yn(f) f?cout<<"YES\n":cout<<"NO\n"
#define syn(f) f?cout<<"Yes\n":cout<<"No\n"
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
#ifdef ONLINE_JUDGE
#define debug(x)
#else
#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
#endif
void _print(ll t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(lld t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
int binpow(int x,int n) {x%=M;if(n==0) return 1; else if(n==1) return x; int p = binpow(x*x, n/2);if(n%2) return p*x%M; else return p;}
int random(int s, int e){return s + rand() % (e - s + 1);}
ll gcd(ll a, ll b){if(b == 0) return a; return gcd(b, a%b);}
ll lcm(ll a, ll b){return a*b/gcd(a,b);}
vi factors(ll n){ vi fac; for (ll i = 1; i * i <= n; i++){ if (n % i == 0){ fac.pb(i); if (i * i != n)fac.pb(n / i); } } return fac; }
int mod_div(int p, int q) { return p%M * binpow(q,M-2) % M;}
vi fact, ifact;
void factCompute(int N=1e6) {fact.assign(N+1, 1);ifact.assign(N+1, 1);fr(i,1,N+1) fact[i] = fact[i-1] * i % M;ifact[N] = mod_div(1, fact[N]); forrr(i,N-1,0) ifact[i] = ifact[i+1] * (i+1) % M; }
int ncr(int n, int r) {if(r > n) return 0; return fact[n] * ifact[n-r] % M * ifact[r] % M;}
vi spf, primes;
void sieve(int N=1e7){spf.assign(N+1,0); fr(i,0,N+1) spf[i]=i;for(int i=2; i*i<=N; i++) if(spf[i]==i) for(int j=i*i; j<=N; j+=i) spf[j]=min(spf[j],i);fr(i,2,N+1) if(spf[i]==i) primes.pb(i);}
vvi graph;
vi vec, par;
void dfs(int node, int parent, vector<map<int, multiset<int>>> &p){
int curr = vec[node];
par[node] = parent;
map<int, int> pf;
while(curr != 1){
int prime = spf[curr];
pf[prime]++;
curr /= prime;
}
vp temp;
for(auto it: pf){
temp.pb(mp(it.ff, it.ss));
}
for(auto it: temp){
p[node][it.ff].insert(it.ss);
if(parent != -1)
p[parent][it.ff].insert(it.ss);
}
for(auto &nbr: graph[node]){
if(nbr != parent)
dfs(nbr, node, p);
}
}
void solve(int tc){
int n;cin>>n;
vec.assign(n+1, 0);
par.assign(n+1, 0);
fr(i,0,n) cin>>vec[i+1];
graph.assign(n+1, {});
for(int i=1;i<n;i++){
int u, v;cin>>u>>v;
graph[u].pb(v);
graph[v].pb(u);
}
vector<map<int, multiset<int>>> p(n+1);
vi gcd1(n+1);
dfs(1, -1, p);
int ans = 0;
for(int i=1;i<=n;i++){
int currsz = graph[i].size();
if(i == 1) currsz++;
int g = 1;
for(auto it: p[i]){
if(it.ss.size() == currsz){
g *= pow(it.ff, *it.ss.begin());
}
}
gcd1[i] = g;
ans += g;
}
// debug(gcd1);
int q;cin>>q;
while(q--){
int t;cin>>t;
if(t == 1){
int node, val;cin>>node>>val;
int curr = vec[node], parent = par[node];
map<int, int> pf;
ans -= gcd1[node];
if(parent != -1)
ans -= gcd1[parent];
curr = vec[node];
while(curr != 1){
int prime = spf[curr];
pf[prime]++;
curr /= prime;
}
vp temp;
for(auto it: pf){
temp.pb(mp(it.ff, it.ss));
}
for(auto it: temp){
p[node][it.ff].erase(p[node][it.ff].find(it.ss));
if(parent != -1)
p[parent][it.ff].erase(p[parent][it.ff].find(it.ss));
}
vec[node] = val;
pf.clear();
curr = vec[node];
while(curr != 1){
int prime = spf[curr];
pf[prime]++;
curr /= prime;
}
temp.clear();
for(auto it: pf){
temp.pb(mp(it.ff, it.ss));
}
int currszn = graph[node].size();int currszp = 0;
if(parent!= -1) currszp = graph[parent].size();
if(node == 1) currszn++;
if(parent == 1) currszp++;
int gc = 1, gp = 1;
for(auto it: temp){
p[node][it.ff].insert(it.ss);
if(parent != -1)
p[parent][it.ff].insert(it.ss);
// debug(p[node][it.ff]);
// debug(p[parent][it.ff]);
if(currszn == p[node][it.ff].size()) {
gc *= pow(it.ff, *p[node][it.ff].begin());
}
if(parent != -1){
if(currszp == p[parent][it.ff].size()) {
gp *= pow(it.ff, *p[parent][it.ff].begin());
}
}
}
gcd1[node] = gc;
if(parent != -1)
gcd1[parent] = gp;
if(parent != -1)
ans += gc + gp;
else
ans += gc;
// debug(gcd1);
}else{
cout<<ans<<endl;
}
}
}
signed main() {
fastio();
// factCompute(1e6);
sieve(1e6);
ll t = 1;
// cin>>t;
fr(i,0,t) solve(i);
return 0;
}
Author : Sarvesh0955
1) Dynamic Programming (DP)
Idea: Let dp[i] represent the number of ways to tile a board of length i.
Base cases:
dp[0] = 1(empty board)
dp[1] = 1(only one 1×1 tile)Recurrence:
Fori ≥ 2, we can either:
- Place a 1×1 tile at the end → contributes
dp[i-1]ways - Place a 2×1 domino (2 colors) → contributes
2 * dp[i-2]ways
Hence, the recurrence is:
dp[i] = dp[i-1] + 2 * dp[i-2]
2) Matrix Exponentiation
Author : rndascode
Count of elements from $$$a+1$$$ to $$$b$$$ divisible by $$$k$$$
= Count of elements from $$$1$$$ to $$$b$$$ divisible by $$$k$$$ — Count of elements from $$$1$$$ to $$$a$$$ divisible by $$$k$$$
= $$$\lfloor b/k \rfloor - \lfloor a/k \rfloor$$$.
Does Modular Division work like arithmetic division, even when $$$a$$$ is not exactly divisible by $$$k$$$? No, it doesn't.
Let us consider the problem simply without the constraints first. Let us assume $$$a$$$ and $$$b$$$ are both give in integer form.
Count of elements from $$$a+1$$$ to $$$b$$$ divisible by $$$k$$$
= Count of elements from $$$1$$$ to $$$b$$$ divisible by $$$k$$$ — Count of elements from $$$1$$$ to $$$a$$$ divisible by $$$k$$$
= $$$\lfloor b/k \rfloor - \lfloor a/k \rfloor$$$.
Our entire solution focusses on implementing this formula for very large numbers.
As the numbers are very big, it is not possible to directly implement this formula. We need the answer mod $$$6991$$$. Using modular arithmetic the equation can be changed to
$$$((b\pmod{6991}*k^{-1}) - (a\pmod{6991}*k^{-1}) + (6991)) \mod{6991}$$$ where $$$k^{-1}$$$ is the modular multiplicative inverse of $$$k$$$ wrt $$$6991$$$.
To efficiently compute $$$b\pmod{6991}$$$ and $$$a\pmod{6991}$$$ we will use the following way:
Start with number $$$0$$$.
For every new digit, compute number = number * base + digit.
Take remainder at each step.
This gives us our required modulus result irrespective of the base of the number.
Our implementation has a problem however. Modular division does not work like arithmetic division. Eg: $$$(44/2)$$$ mod $$$6991$$$ = $$$22$$$, but $$$(45/2)$$$ mod $$$6991$$$ = $$$3518$$$. We need to ensure floor at both computations.
Thus our modified equation becomes:
$$$((b - (b \mod k))/k) - ((a - (a \mod k))/k)$$$ .
Using modular arithmetic the required answer is:
$$$T1 = ((b\pmod{6991}-b\pmod{k}+6991) * k^{-1}) \mod{6991}$$$
$$$T2 = ((a\pmod{6991}-a\pmod{k}+6991) * k^{-1}) \mod{6991}$$$
$$$Ans = (T1 - T2 + 6991) \mod 6991$$$
#include<bits/stdc++.h>
using namespace std;
#define int long
const int MOD = 6991;
long long exp(long long x, long long n, long long m) {
x %= m;
long long res = 1;
while (n > 0) {
if (n % 2 == 1) { res = res * x % m; }
x = x * x % m;
n /= 2;}
return res;}
long long fun(string &a, int m, int base){
int res=0;
for(int i=0;i<a.size();i++){
res = (res*base + int(a[i]-'0'))%m;}
return res%m;}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin>>t;
while(t--){
int a1,b1,k;
cin>>a1>>b1>>k;
string a,b;
cin>>a>>b;
int k_inv = exp(k, MOD-2, MOD);
int term1 = (((fun(a,MOD,2) - fun(a,k,2) + MOD)%MOD) * (k_inv%MOD))%MOD;
int term2 = (((fun(b,MOD,10) - fun(b,k,10) + MOD)%MOD) * (k_inv%MOD))%MOD;
int res = (term2 - term1 + MOD)%MOD;
cout<<res<<endl;}
return 0;}
Author : rndascode
Can we use a DFS based approach to count the number of violations?
Can we use Small to Large Merging to optimize our solution?
To solve this problem efficiently, we can leverage appropriate data structures to store the Binary Tree and perform operations on it. Here's a step-by-step approach:
DFS for Counting Violations: We can use Depth-First Search (DFS) to count the number of nodes that violate the BST properties in each subtree. To check each node's validity in the BST, we compare its value with the maximum and minimum permissible values for that node as we move from the root down to the leaves.
Complexity Analysis: This approach allows us to check the entire tree in $$$O(N)$$$ time, where $$$N$$$ is the number of nodes, because each node is visited only once. At each node, we compare its value with the maximum and minimum bounds passed from its parent, updating these bounds as we recurse deeper.
Tracking Violating Nodes in Order: We can use sets to keep track of nodes that violate the BST property, storing them in ascending order by node number. To efficiently merge these sets as we move up the tree, we can use a technique called small to large merging.
Small to Large Merging Strategy: Starting from the leaf nodes and moving up toward the root in DFS, we store query nodes in the required order (ascending by node number within each query). For each query, the required nodes are stored, allowing us to merge the child node sets with their respective parent sets efficiently.
This approach provides an efficient solution that respects the problem's constraints, ensuring that the operations required per query are minimized through effective data structure usage and ordered processing.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
vector<pair<int, char>> tree[MAXN];
int node_values[MAXN];
int violations_count[MAXN];
set<int> violations_set[MAXN];
set<int> query_nodes;
int level[MAXN];
vector<int> queries[MAXN];
vector<int> query_nodes_vec;
vector<int> result[MAXN];
bool is_violated[MAXN];
map<int, set<int>> violations;
void dfs(int node, int parent, int min_val, int max_val, int lvl) {
level[node] = lvl;
if (!(min_val < node_values[node] && node_values[node] < max_val)) {
is_violated[node] = true;
violations_set[node].insert(node);
violations_count[node] = 1;
} else {
violations_count[node] = 0;
}
for (auto &[child, direction] : tree[node]) {
if (child == parent) continue;
if (direction == 'l') {
dfs(child, node, min_val, min(max_val, node_values[node]), lvl + 1);
} else {
dfs(child, node, max(min_val, node_values[node]), max_val, lvl + 1);
}
if (violations_set[child].size() > violations_set[node].size()) {
swap(violations_set[node], violations_set[child]);
}
violations_set[node].insert(violations_set[child].begin(), violations_set[child].end());
violations_count[node] += violations_count[child];
}
if (query_nodes.find(node) != query_nodes.end()) {
violations[node] = violations_set[node];
}
}
int main() {
int N;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> node_values[i];
}
for (int i = 0; i < N - 1; i++) {
int u, v;
char dir;
cin >> u >> v >> dir;
u--; v--;
tree[u].emplace_back(v, dir);
tree[v].emplace_back(u, dir);
}
int Q;
cin>>Q;
for (int i = 0; i < Q; i++) {
int x; cin>>x; x--;
query_nodes.insert(x);
query_nodes_vec.push_back(x);
}
dfs(0, -1, INT_MIN, INT_MAX, 0);
for(auto node:query_nodes_vec){
cout<<node+1<<" ";
if (violations[node].empty()) {
cout << -1;
} else {
for (int v : violations[node]) {
cout << v + 1 << " ";
}
}
cout<<endl;
}
for (int i = 0; i < N; i++) {
cout << violations_count[i]<< " ";
}
cout << endl;
return 0;
}
Author : Ragnar21
#include<bits/stdc++.h>
using namespace std;
struct Node {
int count;
array<int,2>child;
Node() {
count = child[0] = child[1] = 0;
}
};
struct Trie {
vector<Node>tree;
Trie() {
tree.assign(1, Node());
}
void insert(int node, int index, array<int,32>&bits) {
if(index == 31) {
tree[node].count++;
return;
}
if(!tree[node].child[bits[index + 1]]) {
tree[node].child[bits[index + 1]] = tree.size();
tree.push_back(Node());
}
insert(tree[node].child[bits[index + 1]], index + 1, bits);
tree[node].count = (tree[node].child[0] ? tree[tree[node].child[0]].count : 0) +
(tree[node].child[1] ? tree[tree[node].child[1]].count : 0);
}
long long query(int node, vector<int>&intended, array<int, 32>&real, int matches = 1) {
int iterations = (intended.size()) / 2;
for(int i = 0; i < iterations; i++) {
int bitOne = (intended[i * 2 + 1] ^ real[i * 2 + 1]);
int bitTwo = (intended[i * 2] ^ real[i * 2]);
if(!tree[node].child[bitOne]) return 0;
node = tree[node].child[bitOne];
if(!tree[node].child[bitTwo]) return 0;
node = tree[node].child[bitTwo];
matches = (matches && (bitOne == real[i * 2]) && (bitTwo == real[i * 2 + 1]));
}
return tree[node].count - matches;
}
};
const pair<int,int>iter[] = {
{1, 1},
{1, 0},
{0, 1},
{0, 0},
};
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
auto create = [&](vector<int>&a) -> vector<array<int,32>> {
vector<array<int,32>>arr;
for(auto &x : a) {
array<int,32>temp; temp[31] = 0;
for(int i = 0; i <= 30; i++) {
temp[i] = (((1 << i) & x) != 0);
}
reverse(temp.begin(), temp.end());
arr.push_back(temp);
}
return arr;
};
int tt; cin >> tt;
while(tt--) {
long long n, k, cnt = 0, answer = 0; cin >> n >> k;
vector<int>a(n);
for(auto &i : a) cin >> i;
vector<array<int,32>>arr = create(a);
vector<int>current;
Trie trie = Trie();
for(auto &x : arr) trie.insert(0, -1, x);
for(int i = 0; i <= 30; i += 2) {
vector<long long>counter(4);
for(auto &x : arr) {
for(int itr = 0; itr < 4; itr++) {
current.push_back(iter[itr].first); current.push_back(iter[itr].second);
counter[itr] += trie.query(0, current, x);
current.pop_back(), current.pop_back();
}
}
for(int j = 3; j >= 0; j--) {
if(cnt + counter[j] >= k) {
current.push_back(iter[j].first);
current.push_back(iter[j].second);
answer = (answer << 2ll) + (iter[j].first * 2ll) + (iter[j].second);
break;
} else cnt += counter[j];
}
}
cout << answer << "\n";
}
}
Author : utk_09
Binary search will not work because there is no monotonicity.
Special case in which binary search works is when declaring High as INT_MAX because then it starts behaving as the intended solution. (i.e. takes in consideration one bit at a time and moves accordingly) in INT_MAX all bits are 111111... and mid does /2 ie removes one bit.
/*
we start from last bit
if we are able to achieve our goal by not setting that bit
and rest of its previous bits
i.e. for 4th bit we check for 0111
then there is no need to set i th bit
if not we add that bit to answer and move to next bit
and repeat the process.
*/
void solve()
{
ll n,k,x;
cin>>n>>k>>x;
vl a(n);
ll sum = 0;
for(ll i=0;i<n;i++){
cin>>a[i];
sum += a[i];
}
if(sum > x){
cout<<0<<endl;
return;
}
if(k==0){
cout<<-1<<endl;
return;
}
auto good = [&](ll m){
vpl v;
for(ll i=0;i<n;i++){
v.pb({(a[i]|m)-a[i],a[i]});
}
sort(all(v));
reverse(all(v));
ll sum = 0;
for(ll i=0;i<n;i++){
if(i<k) sum+=(v[i].ss|m);
else sum+=v[i].ss;
}
return sum > x;
};
ll y = 0;
for(ll i=31;i>=0;i--){
if(!good((y|(1ll<<i))-1)){
y += (1ll<<i);
}
}
cout<<y<<endl;
}
Author : utk_09
As in the problem statement, let $$$a_i$$$ be the $$$a_i$$$-th capital English letter.
Consider counting conforming strings for each number of occurrences of $$$z$$$, and finding the answer as their sum. (For convenience we take a letter $$$z$$$, but this is not essential; you can fix any letter and find the count for each number of its occurrences.)
Suppose that a length-$$$s$$$ string has $$$t$$$ occurrences of $$$z$$$. Then, there are $$$\binom{s}{t}$$$ ways to determine the positions of $$$z$$$. The characters at the other positions form a string of length $$$(s−t)$$$ without $$$z$$$ such that $$$a_i$$$ occurs between $$$0$$$ and $$$C_i$$$ times, which is understood by considering the string of length $$$(s−t)$$$ obtained by removing $$$z$$$, for each of the $$$\binom{s}{t}$$$ positions.
Therefore, the problem for $$$a, b, \ldots, z$$$ has been boiled down to that for $$$a, b, \ldots, y$$$.
Similarly, the problem for $$$a, b, \ldots, y$$$ can be boiled down to that for $$$a, b, \ldots, x$$$; repeating this procedure seems to solve the problem.
Once you boiled down the problem with a smaller one, employing DP (Dynamic Programming) is often effective.
Indeed, let $$$dp_{i,j}$$$ be the number of length-$$$j$$$ strings consisting of $$$a_1,a_2,\ldots,a_i$$$ such that $$$a_k$$$ occurs between $$$0$$$ and $$$C_k$$$ times for all $$$1\le k\le i$$$; then by the observation above it turns out that
(We find the sum over $$$k$$$, the number of occurrences of $$$a_{i+1}$$$.)
The answer is
Note that the DP only ranges in $$$j\le K$$$.
By finding the binomial coefficients according to precalculated factorials and its inverses, or by precomputing the binomial coefficients themselves in the manner of Pascal’s triangle, this DP can be solved in a total of
time, where $$$\sigma$$$ is the size of alphabet ($$$\sigma=26$$$ in our case), which is fast enough for the constraints for this problem.
const int MAXN = 1001;
const int MOD = 998244353;
int fac[MAXN + 1];
int inv[MAXN + 1];
int exp(int x,int n,int m){x%=m;int res = 1; while(n>0){if(n%2==1){res=res*x%m;}x=x*x%m;n/=2;}return res;}
void factorial(){fac[0]=1;for(int i = 1; i <= MAXN; i++) { fac[i] = fac[i - 1] * i % MOD; }}
void inverses() {inv[MAXN] = exp(fac[MAXN], MOD - 2, MOD);for (int i = MAXN; i >= 1; i--) { inv[i - 1] = inv[i] * i % MOD; }}
int choose(int n, int r) { if(r>n)return 0ll;return (fac[n] * inv[r] % MOD * inv[n - r] % MOD)%MOD;}
int div(int a,int b,int m){
return ((a%m)*(exp(b,m-2,m)%m))%m ;
}
int32_t main()
{
factorial();
inverses();
int k;cin>>k;
vi freq(27,0);
for(int i=1;i<=26;i++){
cin>>freq[i];
}
vector<vi>dp(27,vi(k+1,0));
for(int i=1;i<=26;i++){
dp[i][0]=1;
}
for(int j=1;j<=min(freq[1],k);j++){
dp[1][j]=1;
}
for(int i=2;i<=26;i++){
for(int j=1;j<=k;j++){
for(int prev=0;prev<=j;prev++){
int rem=j-prev;
if(freq[i]>=rem)
dp[i][j]=(dp[i][j]+(dp[i-1][prev]*choose(j,prev))%mod1)%mod1;
}
}
}
int sum=0;
for(int len=1;len<=k;len++){
sum=(sum+dp[26][len])%mod1;
}
cout<<sum<<endl;
return 0;
}
Author : pranavsingh0111
Try using ordered set with difference array approach.
For every element $$$a_i$$$ try to find the number of elements bigger than it on the right side of the array and the number of elements smaller than it on the left side of the array.
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update> pbds; // find_by_order, order_of_key
#define endl "\n"
#define int long long
int32_t main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n;cin>>n;
vector<int> a(n+1,0);
for(int i=1;i<=n;i++){
cin>>a[i];
}
int q;cin>>q;
map<int,int> diff;
pbds start,end;
for(int i=1;i<=n;i++){
int now=start.order_of_key(make_pair(a[i],i));
diff[a[i]+1]-=now;
start.insert(make_pair(a[i],i));
}
for(int i=n;i>=1;i--){
int now=end.order_of_key(make_pair(a[i],i));
int val=((int)end.size())-now;
diff[a[i]]+=val;
end.insert(make_pair(a[i],i));
}
auto it=diff.begin();
it++;
auto it1=diff.begin();
for(;it!=diff.end();it++){
it->second+=it1->second;
it1=it;
}
while(q--){
int x;cin>>x;
auto it2=diff.upper_bound(x);
if(it2==diff.begin()){
cout<<0<<endl;
continue;
}
else{
it2--;
cout<<(it2->second)<<endl;
}
}
return 0;
}
Auto comment: topic has been updated by Sarvesh0955 (previous revision, new revision, compare).
Auto comment: topic has been updated by Sarvesh0955 (previous revision, new revision, compare).
Auto comment: topic has been updated by Sarvesh0955 (previous revision, new revision, compare).
Sarvesh0955 can you make the hidden tests visible please.
Done.