1957A - Stickogon
Idea: keyurchd_11
Problem Setting: shakr lezirtin
Editorial: shakr TheRaja
There were a few solutions which passes pre-tests with the assumption that $$$a_i \leq n$$$. We apologize for the pre-tests on A not including this case.
To create the most polygons, you should use as few sticks as possible per polygon. What polygon has the least number of sides?
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin >> t;
while(t--) {
int n;
cin >> n;
vector<int> a(101, 0);
for (int i = 0; i < n; i++) {
int x;
cin >> x;
a[x]++;
}
int sum = 0;
for (auto& s : a)
sum += s / 3;
cout << sum << "\n";
}
}
1957B - A BIT of a Construction
Idea: akcube
Problem Setting: Prakul_Agrawal
Editorial: Prakul_Agrawal TheRaja
Given that the sum is bounded, which bits could be set in the bitwise OR?
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin >> t;
while(t--) {
int n, k;
cin >> n >> k;
vector<int> a(n);
if (n == 1) {
a[0] = k;
}
else {
int msb = 0;
// find the msb of k
for (int i = 0; i < 31; i++) {
if (k & (1 << i)) {
msb = i;
}
}
a[0] = (1 << msb) - 1;
a[1] = k - a[0];
for (int i = 2; i < n; i++) {
a[i] = 0;
}
}
for (int i = 0; i < n; i++) {
cout << a[i] << " ";
}
cout << "\n";
}
return 0;
}
1957C - How Does the Rook Move?
Idea: SilverTongue1729
Problem Setting: ppt1524 GenghizKhan
Editorial: ppt1524 TheRaja
There are 2 ways to approach the problem. The combinatorics approach is slightly more involved and might be more difficult to come up with.
You can ignore the exact positions of the rooks in the initial configurations. Only the number of free rows and columns matter.
For each move you can make, how does the number of free rows/columns change?
Altenatively, we can iterate on the number of type $$$1$$$ moves we play. Let's term this to be $$$c$$$.
There are $$${m\choose c}$$$ ways to choose the $$$c$$$ type $$$1$$$ moves. Now, we have $$$m - c$$$ rows/columns left, and this must be even (type 2 moves cannot exhaust an odd number of rows/columns).
We can see that each of the $$$(m - c)!$$$ permutations of the remaining columns correspond to a set of moves we can play. For example, if we have the columns $$$(1, 4, 5, 6)$$$ remaining, a permutation $$$(4, 5, 6, 1)$$$ corresponds to playing the moves $$$(4, 5), (6, 1)$$$. However, if we simply count the number of permutations, we would also be counting the permutation $$$(6, 1, 4, 5)$$$, which corresponds to the same set of moves.
To remove overcounting, we can just divide $$$(m - c)!$$$ by $$$((m - c)/2)!$$$ (removing the permutations of the pairs chosen).
Hence, the answer becomes
$$$\sum\limits_{c = 0}^m [(m - c) \bmod 2 = 0] {m \choose c} \frac{(m - c)!}{\left(\frac{m - c}{2}\right)!}$$$
#include <bits/stdc++.h>
using namespace std;
int dp[(int) 3e5+5];
const int MOD = 1e9 + 7;
int main() {
cin.tie(0), cout.tie(0)->sync_with_stdio(0);
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
int used = 0;
for (int i = 0; i < k; i++) {
int r, c; cin >> r >> c;
used += 2 - (r == c);
}
int m = n - used;
dp[0] = dp[1] = 1;
for (int i = 2; i <= m; i++)
dp[i] = (dp[i-1] + 2ll * (i-1) * dp[i-2] % MOD) % MOD;
cout << dp[m] << "\n";
}
}
1957D - A BIT of an Inequality
Idea: fangahawk
Problem Setting: fangahawk shiven
Editorial: JadeReaper TheRaja
How can you simplify the given inequality? Use the fact that the XOR of a number with itself is 0.
The inequality simplifies to $$$f(x, z) \oplus a_y > f(x, z)$$$. For a given $$$a_y$$$ what subarrays (that include $$$a_y$$$) would satisfy this?
First we may rewrite the inequality as $$$f(x, z) \oplus a_y > f(x, z)$$$. So, for each index $$$y$$$, we want to find the total number of subarrays that contain $$$y$$$ but whose $$$\text{xor}$$$ decreases when we include the contribution of $$$a_y$$$.
Including $$$a_y$$$ in some subarray $$$[x, z]$$$ (where $$$x \le y \le z$$$) can make the $$$\text{xor}$$$ lower only when some set bit of $$$a_y$$$ cancels out an existing set bit in $$$f(x, y - 1) \oplus f(y + 1, z)$$$. Consider the most signicant set bit in $$$a_y$$$. Call this bit $$$i$$$. Including $$$a_y$$$ would decrease the subarray $$$\text{xor}$$$ in subarrays where $$$f(x, y - 1)$$$ has $$$i$$$ set while $$$f(y+1, z)$$$ is unset or vice-versa.
Now, for the subarrays where both the prefix subarray ($$$[x \dots y - 1]$$$) as well as the suffix subarray ($$$[y + 1 \dots z]$$$) where either both have bit $$$i$$$ set or both have it unset, by including $$$a_y$$$, we increment the xor by at least $$$2^i$$$. Even if by including $$$a_y$$$, every other smaller bit gets unset (because of cancelling out with $$$a_y$$$), this sum of these decrements is still less than $$$2^i$$$ thereby resulting in an overall positive contribution by including $$$a_y$$$.
#include <bits/stdc++.h>
using namespace std;
const int Z = 30;
const int MAX_N = 1e5 + 3;
int pref[Z][MAX_N][2];
int suff[Z][MAX_N][2];
void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 0; i < Z; i++) suff[i][n + 1][0] = suff[i][n + 1][1] = 0;
for (int i = 0; i < Z; i++) {
for (int j = 1; j <= n; j++) {
int t = !!(a[j] & (1 << i));
for (int k = 0; k < 2; k++) pref[i][j][k] = (t == k) + pref[i][j - 1][k ^ t];
}
for (int j = n; j >= 1; j--) {
int t = !!(a[j] & (1 << i));
for (int k = 0; k < 2; k++) suff[i][j][k] = (t == k) + suff[i][j + 1][k ^ t];
}
}
long long ans = 0;
for (int i = 1; i <= n; i++) {
int z = 31 - __builtin_clz(a[i]);
ans += 1ll * pref[z][i - 1][1] * (1 + suff[z][i + 1][0]);
ans += 1ll * (1 + pref[z][i - 1][0]) * suff[z][i + 1][1];
}
cout << ans << "\n";
}
int main() {
int tc;
cin >> tc;
while (tc--)
solve();
return 0;
}
1957E - Carousel of Combinations
Idea: SilverTongue1729
Problem Setting: JadeReaper
Editorial: SilverTongue1729 JadeReaper TheRaja
For what values of $$$j$$$ is $$$C(i,j) \bmod j = 0$$$?
For all other values of $$$j$$$, how can you precompute the result?
To precompute, switch around the loop order.
The number of distinct ways you can select $$$k$$$ distinct numbers from the set {$$$1, 2, \ldots, i$$$} and arrange them in a line is $$$i(i-1)\cdots(i-k+1)$$$, and since arranging in a circle introduces rotational symmetry we have to divide by $$$k$$$, so we have $$$C(i,k) = \frac{i(i-1)\cdots(i-k+1)}{k}$$$.
Therefore $$$C(i,j) \bmod j = \frac{i(i-1)\cdots(i-j+1)}{j} \bmod j$$$. Now since the numerator is a product of $$$j$$$ consecutive integers, atleast one of them will be divisible by $$$j$$$. More precisely the exact integer which will be divisible by $$$j$$$ will be $$$ j \times \lfloor \frac{i}{j} \rfloor$$$. Hence we can simplify the fraction by removing the denominator and replacing the term $$$ j \times \lfloor \frac{i}{j} \rfloor$$$ with $$$\lfloor \frac{i}{j} \rfloor$$$ in the numerator. Each of the other $$$j-1$$$ integers in the numerator, after applying $$$\bmod j$$$ would cover all integers from $$$1$$$ to $$$j-1$$$. Hence
Here we can notice that all proper factors of $$$j$$$ will occur in $$$(j-1)!$$$, so based on this we can tell that $$$C(i,j) \bmod j = 0$$$ for all composite numbers $$$j$$$ except $$$j=4$$$.
We first can handle the case of $$$j$$$ being prime. Using Wilson's Theorem, we know that $$$(j-1)! \equiv -1 \bmod j$$$ when $$$j$$$ is prime. Hence
Now we can reverse the order of loops to sum over all primes, and to calculate the contribution of each prime we can maintain a update array called $$$delta$$$.
To calculate the contribution for a single prime $$$p$$$, we know that for all $$$n$$$ from $$$kp$$$ to $$$(k + 1)p - 1$$$ (for all $$$k$$$ such that $$$kp < 1e6$$$) the contribution would be $$$-k$$$. So, in the $$$delta$$$ array, we increment index $$$kp$$$ with $$$-k \bmod p$$$ and decrement index $$$(k + 1)p$$$ with $$$-k \mod p$$$. Now, when we perform a prefix sum on this $$$delta$$$ array, we obtain the correct contributions from all primes.
For the case of $$$j=4$$$, we just need to handle it as a prime.
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int MAX_N = 1e6 + 3;
bitset<MAX_N> isprime;
vector<int> primes;
vector<int> eratosthenesSieve(int lim) {
isprime.set();
isprime[0] = isprime[1] = false;
for (int i = 4; i < lim; i += 2) isprime[i] = false;
for (int i = 3; i * i < lim; i += 2)
if (isprime[i])
for (int j = i * i; j < lim; j += i * 2) isprime[j] = false;
vector<int> pr;
for (int i = 2; i < lim; i++)
if (isprime[i]) pr.push_back(i);
return pr;
}
vector<int> ans(MAX_N, 0);
signed main() {
primes = eratosthenesSieve(MAX_N);
vector<int> del(MAX_N, 0);
// Handle the contribution for all primes
for (auto &p: primes) {
for (int curr = p; curr < MAX_N; curr += p) {
int inc = (p - ((curr / p) % p)) % p;
del[curr] = (del[curr] + inc) % MOD;
if (curr + p < MAX_N) del[curr + p] = (del[curr + p] - inc + MOD) % MOD;
}
}
//Special case of 4
for (int curr = 4; curr < MAX_N; curr += 4) {
int inc = (2 * (curr / 4)) % 4;
del[curr] = (del[curr] + inc) % MOD;
if (curr + 4 < MAX_N) del[curr + 4] = (del[curr + 4] - inc + MOD) % MOD;
}
int pref = 0;
for (int i = 1; i < MAX_N; i++) {
pref = (pref + del[i]) % MOD;
ans[i] = (ans[i - 1] + pref) % MOD;
}
int tc;
cin >> tc;
while (tc--) {
int n;
cin >> n;
cout << ans[n] << "\n";
}
}
1957F1 - Frequency Mismatch (Easy Version)
Idea: fangahawk
Problem Setting: fangahawk
Editorial: akcube
Let's try answering a different question. Given two multisets of elements how can we check if they differ? Hashing? How to multiset hash efficiently?
Okay if we can now differentiate two multisets of unequal elements, can we try to answer queries by inserting into these hypothetical multisets and binary search the differing point to identify the element?
Let's discuss how to hash a multiset of elements $$$a$$$, $$$b$$$ and $$$c$$$. Here, I will link you to a famous blog by rng_58 Hashing and Probability of Collision. Quoting, let's take a random integer $$$r$$$ from the interval $$$[0, MOD)$$$, and compute the hash $$$(r+a_1)(r+a_2)\dots(r+a_n)$$$. This is a polynomial of $$$r$$$ of degree $$$n$$$, so again from Schwartz-Zippel lemma, the collision probability is at most $$$\frac{n}{MOD}$$$. The nice thing about this construction is that we can compute rolling hashes using this idea fast. To make implementation easier, this bound applies for summing the random numbers as well. You can check this for proof.
Let's try to answer a single query $$$(u_1, v_1, u_2, v_2)$$$ using binary search. We will solve this query in $$$nlog^2(n)$$$ using this idea. To check for some $$$mid$$$ in our binary search, we insert the values of all nodes which have values from $$$1$$$ to $$$mid$$$ into a data structure that we can query the path sum of $$$u$$$ to $$$v$$$ using. Querying path sum is a fairly standard problem that can be solved using BIT / Segment trees and ETT (Euler-Tour Trick). Now to solve this query, we only need to binary search and find the first vertex where the hashes differ for both the paths. This vertex is guaranteed to have mismatched frequency on the two paths since it's addition into the path multi-sets changed their hashes. So now we can solve a single query in $$$nlog^2(n)$$$ time using hashing + BIT / Segtree.
Now to solve this problem for all $$$Q$$$ queries. We can use the idea of parallel binary search here to improve our idea to answering all $$$Q$$$ queries efficiently. We can run the binary search for all queries in parallel. For each iteration, sort queries by the current position of their $$$mid$$$ values. Then insert values from $$$1$$$ to $$$mid$$$ of the first query into the BIT and query range sum to determine for that particular query how to adjust $$$mid$$$. You can then move the $$$mid$$$ pointer to that of the next query and so on. This solution will run in $$$O(nlog(n) + qlog^2(n))$$$.
Upd: Thanks to IceKnight1093 for pointing this out. If we just use a single int
hash with a field size of $$$\approx 10^9$$$, it gives us a probability of failure of $$$\frac{1}{10^9}$$$ per query. Since we're doing somewhere of the order $$$10^6$$$ comparisons per hash representation, this gives a rough $$$1 - \Big(1 - \frac{1}{10^9}\Big)^{10^6} \approx 10^{-3}$$$ chance of failure. This is not a great bound theoretically speaking, but from a practical standpoint, it is a loose bound and it is extremely unlikely that this solution can be hacked. That said, if we want better theoretical bounds we can just use a hash with field size $$$\approx 10^{18}$$$ or use double hashing. Even if we were to query all $$${n \choose 2}$$$ paths, the chance of collision is $$$\approx \frac{n^2}{10^{18}} \approx 10^{-8}$$$, which is more than good enough. TL's were set to allow double hashing solutions to pass comfortably.
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
using ll = long long;
using dbl = long double;
//#define int ll
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vii = vector<pii>;
using vvii = vector<vii>;
using vll = vector<ll>;
#define ff first
#define ss second
#define pb push_back
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define tc int t; cin>>t; while(t--)
#define fightFight cin.tie(0) -> sync_with_stdio(0)
template<class T>
struct RMQ {
vector<vector<T>> jmp;
RMQ(const vector<T>& V) : jmp(1, V) {
for (int pw = 1, k = 1; pw * 2 <= sz(V); pw *= 2, ++k) {
jmp.emplace_back(sz(V) - pw * 2 + 1);
rep(j,0,sz(jmp[k]))
jmp[k][j] = min(jmp[k - 1][j], jmp[k - 1][j + pw]);
}
}
T query(int a, int b) {
assert(a <= b); // tie(a, b) = minimax(a, b)
int dep = 31 - __builtin_clz(b-a+1);
return min(jmp[dep][a], jmp[dep][b - (1 << dep) + 1]);
}
};
struct LCA {
int T = 0;
vi st, path, ret; vi en, d;
RMQ<int> rmq;
LCA(vector<vi>& C) : st(sz(C)), en(sz(C)), d(sz(C)), rmq((dfs(C,0,-1), ret)) {}
void dfs(vvi &adj, int v, int par) {
st[v] = T++;
for (auto to : adj[v]) if (to != par) {
path.pb(v), ret.pb(st[v]);
d[to] = d[v] + 1;
dfs(adj, to, v);
}
en[v] = T-1;
}
bool anc(int p, int c) { return st[p] <= st[c] and en[p] >= en[c]; }
int lca(int a, int b) {
if (a == b) return a;
tie(a, b) = minmax(st[a], st[b]);
return path[rmq.query(a, b-1)];
}
int dist(int a, int b) { return d[a] + d[b] - 2*d[lca(a,b)]; }
};
template<const int mod>
struct mint {
constexpr mint(int x = 0) : val((x % mod + mod) % mod) {}
mint& operator+=(const mint &b) { val += b.val; val -= mod * (val >= mod); return *this; }
mint& operator-=(const mint &b) { val -= b.val; val += mod * (val < 0); return *this; }
mint& operator*=(const mint &b) { val = 1ll * val * b.val % mod; return *this; }
mint& operator/=(const mint &b) { return *this *= b.inv(); }
mint inv() const {
int x = 1, y = 0, t;
for(int a=val, b=mod; b; swap(a, b), swap(x, y))
t = a/b, a -= t * b, x -= t * y;
return mint(x);
}
mint pow(int b) const {
mint a = *this, res(1);
for(; b; a *= a, b /= 2) if(b&1) res *= a;
return res;
}
friend mint operator+(const mint &a, const mint &b) {return mint(a) += b;}
friend mint operator-(const mint &a, const mint &b) {return mint(a) -= b;}
friend mint operator*(const mint &a, const mint &b) {return mint(a) *= b;}
friend mint operator/(const mint &a, const mint &b) {return mint(a) /= b;}
friend bool operator==(const mint &a, const mint &b) {return a.val == b.val;}
friend bool operator!=(const mint &a, const mint &b) {return a.val != b.val;}
friend bool operator<(const mint &a, const mint &b) {return a.val < b.val;}
friend ostream& operator<<(ostream &os, const mint &a) {return os << a.val;}
int val;
};
using Mint = mint<MOD>;
template<typename... Ts, size_t... Is, typename F>
void __op(index_sequence<Is...>, tuple<Ts...>& a, const tuple<Ts...>& b, F op) { ((get<Is>(a) = op(get<Is>(a), get<Is>(b))), ...); }
#define OVERLOAD(OP, F) \
template<typename... Ts> auto& operator OP##=(tuple<Ts...> &a, const tuple<Ts...> &b) { __op(index_sequence_for<Ts...>(), a, b, F<>{}); return a; } \
template<typename... Ts> auto operator OP(const tuple<Ts...> &a, const tuple<Ts...> &b) { auto c = a; c OP##= b; return c; }
OVERLOAD(+, plus) OVERLOAD(-, minus) OVERLOAD(*, multiplies) OVERLOAD(/, divides)
constexpr int NUM_HASHES = 2; // *
constexpr array<int, NUM_HASHES> mods = {127657753, 987654319}; // *
template <size_t N = NUM_HASHES>
constexpr auto mint_ntuple(const int &v) {
return [&]<size_t... Is>(index_sequence<Is...>) { return make_tuple(mint<mods[Is]>(v)...); }(make_index_sequence<N>{}); }
using HT = decltype(mint_ntuple(0));
template<typename T>
struct FT {
vector<T> s;
T def;
FT(int n, T def) : s(n, def), def(def) {}
void update(int pos, T dif) { // a[pos] += dif
for (; pos < sz(s); pos |= pos + 1) s[pos] += dif;
}
T query(int pos) { // sum of values in [0, pos)
pos++;
T res = def;
for (; pos > 0; pos &= pos - 1) res += s[pos-1];
return res;
}
};
struct Query {
int u1, v1, u2, v2, k;
int l, r, ans, i;
int mid(){ return l + (r-l)/2; }
};
auto rng = std::mt19937(std::random_device()());
constexpr const int MXN = 1e5+5;
void solve(){
int n; cin >> n;
vi a(n); for(auto &x : a) cin >> x, x--;
vvi adj(n);
for(int i=0; i < n-1; i++){
int u, v; cin >> u >> v; u--, v--;
adj[u].pb(v); adj[v].pb(u);
}
int q; cin >> q;
vector<Query> queries(q);
int idx=0;
for(auto &[u1, v1, u2, v2, k, l, r, ans, i] : queries) cin >> u1 >> v1 >> u2 >> v2 >> k, u1--, v1--, u2--, v2--, l=0, ans=-1, i=idx++;
LCA lca(adj);
vi uni(a); sort(all(uni)); uni.resize(unique(all(uni)) - uni.begin());
vvi cnode(MXN);
for(int v=0; v < n; v++) cnode[a[v]].pb(v);
vector<HT> hash(MXN);
for(auto &c : uni) hash[c] = {rng(), rng()};
auto get_ett = [&](vvi &adj){
vi tin(n), tout(n);
int timer = 0;
function<void(int,int)> dfs = [&](int v, int p){
tin[v] = timer++;
for(auto &to : adj[v]) if(to != p) dfs(to, v);
tout[v] = timer++;
};
dfs(0, -1);
return make_pair(tin, tout);
};
auto [tin, tout] = get_ett(adj);
for(auto &q : queries) q.r = sz(uni)-1;
vi vis(MXN);
for(int _=0; _<20; _++){
FT<HT> st(2*n, mint_ntuple(0));
sort(all(queries), [&](Query &a, Query &b) { return a.mid() < b.mid(); });
for(int qq=0, cptr=0; qq < q; qq++) if(queries[qq].l <= queries[qq].r) {
auto &[u1, v1, u2, v2, k, l, r, ans, i] = queries[qq];
for(; cptr < sz(uni) and cptr <= queries[qq].mid(); cptr++){
for(auto &v : cnode[uni[cptr]])
st.update(tin[v], hash[uni[cptr]]), st.update(tout[v], mint_ntuple(0)-hash[uni[cptr]]);
vis[uni[cptr]] = true;
}
int lca1 = lca.lca(u1, v1), lca2 = lca.lca(u2, v2);
HT r1 = st.query(tin[lca1]), r2 = st.query(tin[lca2]);
HT hash1 = (st.query(tin[u1]) + st.query(tin[v1]) - (r1 + r1));
if(vis[a[lca1]]) hash1 += hash[a[lca1]];
HT hash2 = (st.query(tin[u2]) + st.query(tin[v2]) - (r2 + r2));
if(vis[a[lca2]]) hash2 += hash[a[lca2]];
if(hash1 != hash2){
ans = queries[qq].mid();
r = queries[qq].mid()-1;
}
else l = queries[qq].mid()+1;
}
for(auto &c : uni) vis[c] = false;
}
sort(all(queries), [&](Query &a, Query &b) { return a.i < b.i; });
for(auto &[u1, v1, u2, v2, k, l, r, ans, i] : queries){
if(ans == -1) cout << 0 << '\n';
else cout << 1 << ' ' << uni[ans]+1 << '\n';
}
}
signed main(){
fightFight;
solve();
}
1957F2 - Frequency Mismatch (Hard Version)
Idea: fangahawk
Problem Setting: fangahawk
Editorial: fangahawk TheRaja
How would you find the smallest element with different frequencies in two static arrays using a segment tree? Consider hashing.
Try extending this idea to finding the smallest element with different frequencies in two different paths on a tree. Think persistent data structures.
Once you solve that, you can be extend it to finding the k smallest elements.
You can also use an idea similar to the hashing technique used in F1 to hash the segment tree nodes.
#include <bits/stdc++.h>
using namespace std;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
using ll = long long;
using dbl = long double;
//#define int ll
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vii = vector<pii>;
using vvii = vector<vii>;
using vll = vector<ll>;
#define ff first
#define ss second
#define pb push_back
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define tc int t; cin>>t; while(t--)
#define fightFight cin.tie(0) -> sync_with_stdio(0)
template<class T>
struct RMQ {
vector<vector<T>> jmp;
RMQ(const vector<T>& V) : jmp(1, V) {
for (int pw = 1, k = 1; pw * 2 <= sz(V); pw *= 2, ++k) {
jmp.emplace_back(sz(V) - pw * 2 + 1);
rep(j,0,sz(jmp[k]))
jmp[k][j] = min(jmp[k - 1][j], jmp[k - 1][j + pw]);
}
}
T query(int a, int b) {
assert(a <= b); // tie(a, b) = minimax(a, b)
int dep = 31 - __builtin_clz(b-a+1);
return min(jmp[dep][a], jmp[dep][b - (1 << dep) + 1]);
}
};
struct LCA {
int T = 0;
vi st, path, ret; vi en, d;
RMQ<int> rmq;
LCA(vector<vi>& C) : st(sz(C)), en(sz(C)), d(sz(C)), rmq((dfs(C,1,-1), ret)) {}
void dfs(vvi &adj, int v, int par) {
st[v] = T++;
for (auto to : adj[v]) if (to != par) {
path.pb(v), ret.pb(st[v]);
d[to] = d[v] + 1;
dfs(adj, to, v);
}
en[v] = T-1;
}
bool anc(int p, int c) { return st[p] <= st[c] and en[p] >= en[c]; }
int lca(int a, int b) {
if (a == b) return a;
tie(a, b) = minmax(st[a], st[b]);
return path[rmq.query(a, b-1)];
}
int dist(int a, int b) { return d[a] + d[b] - 2*d[lca(a,b)]; }
};
template<const int mod>
struct mint {
constexpr mint(int x = 0) : val((x % mod + mod) % mod) {}
mint& operator+=(const mint &b) { val += b.val; val -= mod * (val >= mod); return *this; }
mint& operator-=(const mint &b) { val -= b.val; val += mod * (val < 0); return *this; }
mint& operator*=(const mint &b) { val = 1ll * val * b.val % mod; return *this; }
mint& operator/=(const mint &b) { return *this *= b.inv(); }
mint inv() const {
int x = 1, y = 0, t;
for(int a=val, b=mod; b; swap(a, b), swap(x, y))
t = a/b, a -= t * b, x -= t * y;
return mint(x);
}
mint pow(int b) const {
mint a = *this, res(1);
for(; b; a *= a, b /= 2) if(b&1) res *= a;
return res;
}
friend mint operator+(const mint &a, const mint &b) { return mint(a) += b; }
friend mint operator-(const mint &a, const mint &b) { return mint(a) -= b; }
friend mint operator*(const mint &a, const mint &b) { return mint(a) *= b; }
friend mint operator/(const mint &a, const mint &b) { return mint(a) /= b; }
friend bool operator==(const mint &a, const mint &b) { return a.val == b.val; }
friend bool operator!=(const mint &a, const mint &b) { return a.val != b.val; }
friend bool operator<(const mint &a, const mint &b) { return a.val < b.val; }
friend ostream& operator<<(ostream &os, const mint &a) { return os << a.val; }
int val;
};
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<ll> rnd(20,10000);
using Mint1 = mint<MOD1>;
using Mint2 = mint<MOD2>;
using Mint = pair<Mint1,Mint2>;
const int N = 3e5 + 10, LOGN = 20;
int p1, p2;
int blen = 0;
int L[N * LOGN], R[N * LOGN];
Mint ST[N * LOGN], p_pow[N];
void prec() {
p1 = rnd(rng);
p2 = p1;
while (p2 == p1) p2 = rnd(rng);
p_pow[0].ff = 1;
p_pow[0].ss = 1;
for (int i = 1; i < N; i++) {
p_pow[i].ff = p_pow[i - 1].ff * p1;
p_pow[i].ss = p_pow[i - 1].ss * p2;
}
}
int update(int pos, int l, int r, int id) {
if (pos < l || pos > r) return id;
int ID = ++blen, m = (l + r) / 2;
if (l == r) return (ST[ID] = {ST[id].ff + 1, ST[id].ss + 1}, ID);
L[ID] = update(pos, l, m, L[id]);
R[ID] = update(pos, m + 1, r, R[id]);
return (ST[ID] = {ST[L[ID]].ff + p_pow[m - l + 1].ff * ST[R[ID]].ff, ST[L[ID]].ss + p_pow[m - l + 1].ss * ST[R[ID]].ss}, ID);
}
vi vals;
using a4 = array<int,4>;
void descent(int l, int r, const array<int, 4>& a, const array<int, 4>& b, int k) {
if (l == r) return void(vals.push_back(l));
int m = (l + r) / 2;
#define stm(X, y) {ST[X[y[0]]].ff + ST[X[y[1]]].ff - ST[X[y[2]]].ff - ST[X[y[3]]].ff, ST[X[y[0]]].ss + ST[X[y[1]]].ss - ST[X[y[2]]].ss - ST[X[y[3]]].ss}
#define arr(X, y) (a4{X[y[0]], X[y[1]], X[y[2]], X[y[3]]})
Mint l1 = stm(L, a), l2 = stm(L, b), r1 = stm(R, a), r2 = stm(R, b);
if (sz(vals) < k && l1 != l2) descent(l, m, arr(L, a), arr(L, b), k);
if (sz(vals) < k && r1 != r2) descent(m + 1, r, arr(R, a), arr(R, b), k);
}
vvi adj;
vi a, roots, par;
void dfs(int x, int p) {
par[x] = p;
roots[x] = update(a[x], 0, N, roots[par[x]]);
for (auto& s : adj[x]) if (s != p) {
dfs(s, x);
}
}
void solve(){
int n; cin >> n;
adj = vvi(n + 1);
a = roots = par = vi(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 0; i < n - 1; i++) {
int a, b; cin >> a >> b;
adj[a].pb(b), adj[b].pb(a);
}
dfs(1, 0);
LCA lca(adj);
int q; cin >> q;
while (q--) {
vals.clear();
int u1, v1, u2, v2, k; cin >> u1 >> v1 >> u2 >> v2 >> k;
int l1 = lca.lca(u1, v1), l2 = lca.lca(u2, v2);
a4 a{roots[u1], roots[v1], roots[l1], roots[par[l1]]};
a4 b{roots[u2], roots[v2], roots[l2], roots[par[l2]]};
descent(0, N, a, b, k);
cout << sz(vals) << " ";
for (auto& s : vals) cout << s << " ";
cout << "\n";
}
}
signed main(){
fightFight;
prec();
solve();
}
Find any differences
Round 700 D
Round 837 F2 (easy version of the previous one)
F2
257613633 Hey everyone im currently a beginner at cp , I'm asking if anyone can tell me why i got a runtime error in my submission for the first problem Thanks
$$$a \le 100$$$, not $$$a \le n$$$
Thank you, i didnt notice that :( Fixed it 257651745
My official reaction to the 3rd question
I think the complexity of E1 must be $$$O((n+q)log^2n)$$$, since we have to insert and query $$$(n+q)logn$$$ times.
My bad. Updated editorial, thanks!
In the Solution of 1957F1 — Frequency Mismatch (Easy Version), the article Hashing and Probability of Collision is written by rng_58, not rng68.
Oops :P Fixed, thanks.
can anybody explain why (i-1) is multiplied in dp code of problem C ?
There are 2*n-2 possible places where the rook can be placed for reducing the size of the chessboard without worrying about overcounting.
How the count comes 2*n-2 I find there are 2*n place u can place rooks to reduce states by 2 can please explain
Consider the i'th row/col pair. There are $$$ 2\cdot (i-1) $$$ squares on it. One of them is the diagonal square, $$$(i, i)$$$, and the rest $$$2\cdot(i-1)$$$ are normal. Diagonal square removes 1 row/col pair, the rest remove 2. Thus, $$$dp_i = dp_{i-1} + 2\cdot(i-1) \cdot dp_{i-2}$$$.
I was thinking about $$$dp$$$ in this way. Take the grid of free $$$n \times n$$$ squares. There are $$$n$$$ ways to choose a diagonal square and $$$n \times n - n$$$ ways to choose non-diagonal sqaure. If we choose a diagonal square, the number of free squares would decrease by $$$1$$$ and by $$$2$$$, if we choose a non-diagonal square. So, $$$dp[n] = (n \times n - n) \times dp[n-2] + n \times dp[n-1]$$$. I know it is over counting somewhere, but cannot figure out where.
There are i rows and columns left.
Now you take the i element and to pair it, you need a j. You can choose any of the other i-1 elements as j.
The pairing matters as choosing a different j for the i makes the board look different.
Also, you get the factor of 2 when you swap i and j.
thanks bro got it
The intuition here is that when you have
i*i
matrix left, you fixate on one of the columns (and the corresponding row) and calculate for remaining matrix.Let's say we are only selecting the column and row on the boundary of the matrix, we will have
2*(i-1)
cells to select from and then we can continue usingdp[i-2]
. This guarantees the we don't overlap the formation we get fromdp[i-2]
.For example, if i=4, we decide to select one of the cells marked with X. Obviously, we ignore the corner cell as it is counted in
dp[i-1]
.https://codeforces.net/contest/1957/submission/257592898 Does someone see why I'm getting a runtime error in test case 2 of problem C ? I'm not getting any error while testing the same thing on my side and it also passed the pretests during the contest so I'm a bit confused. I shouldn't get outside the bounds of the array either I think.
If $$$n = 1$$$, you are accessing $$$dp[2]$$$ which isn't defined.
omg I feel so dumb. I dropped more than 100 rating points because of that line XD. Thanks for the help.
In the solution of D shouldn't it be "where $$$f(x,y−1)$$$ has $$$i$$$ set" instead of "where $$$f(x,y−1)$$$ has $$$x$$$ set".
Fixed this mistake, thanks for pointing this out.
1957C is OEIS-A047974. Can be solved by dfs-brute force for small n, then search for formula.
Could someone send me some problems like D please.
Search by math in the problemset, then filter out those that have XOR in the name
Could someone explain the idea behind the D solution please? What do the params in
pref[Z][MAX_N][2]
represent? I'm assuming Z is bits, MAXN is array elements, what is the final dimension there for?pref[i][j][k] gives the number of possibilities for choosing a suffix from |a1..aj| such that the xor of the suffix for bit i is k.
Thanks. I felt so weird reading the solution: I've realized everything that's written there during the contest but couldn't figure a way to count ranges efficiently (which is not explained in the solution itself).
me too, could someone detail their intuition behind their sol
We want to have $$$f(x,z)⊕y>f(x,z)$$$ where $$$x<=y<=z$$$. This will happen if $$$MSB$$$ of $$$y$$$ in $$$f(x,z)$$$ is unset, therefore on doing $$$f(x,z)⊕y$$$, it will become set and the value will increase. We are only considering the $$$MSB$$$ because sum of all the rest of the set bits is smaller than $$$MSB$$$ so unsetting $$$MSB$$$ and setting all other bits will still be reducing the value so the deciding factor is only $$$MSB$$$. For $$$f(x,z)$$$ to have unset bit at $$$MSB$$$, $$$f(x,y-1)$$$ and $$$f(y+1,z)$$$ should have different parity of set bits at $$$MSB$$$. Picking all pairs of $$$(x,z)$$$ satisfying the condition above can be fastened to $$$O(1)$$$ for every $$$1<=y<=N$$$ using prefix and suffix arrays. Overall TC will be $$$O(32*N)$$$. I myself was unable to implement the logic I mentioned in the contest. :(
Code Link :- 257668182
I'm sorry what I meant is I got all these observations in contest but could you specifically explain your code here.
could you explain this
For f(x,z) to have unset bit at MSB , f(x,y−1) and f(y+1,z) should have different parity of set bits at MSB
they must be odd odd or even even to make the MSB bit unset when xoring yes , with that it becomes same parity not different ?
in the editorial it says that it shouled be both set or both unset in ( f (x , y-1 ) and f ( y+1 , z)
$$$odd + even + 2*odd = odd$$$
Here, $$$f(x,y-1)$$$ and $$$f(y+1,z)$$$ have different parity resembling the first 2 values of $$$LHS$$$ and as $$$y$$$ already has set bit at $$$MSB$$$, it gives the third part as it is counted twice in xor operation. Finally, we have odd value at $$$MSB$$$ so set bit at $$$MSB$$$.
Bro can u explain this conidition and why the value of even and odd has been swapped if(right[msb][i]!=right[msb][i-1]){ re=val+1; ro=n-i-val; } else{ ro=val; re=n-i-val+1; }
Repsaj21o gave a great answer. For each element
a_i
, you need to find a combimation of prefix[l,i]
and suffix[i+1,r]
such that adding it decreases the xor. As outlined in the solution, this can be done by checking the most significant bit ina_i
and comparing it to the ones in the prefix and suffix.So essentially, we can a formulate the problem like that: for each element
a_i
and its 'msb(a_i)', find all the combinations of prefixes and suffixes where this bit is set in prefix/unset in suffix or the other way around — unset in prefix/set in suffix, and multiple those.Do do that, we'll keep array
pref[bt][index][value]
(same with suffix), which represents the amount of suffixes of prefix [0..index], wherebt
bit is set tovalue
. It's easy to recalculate it: supposei
-th element hasbt
bit0
. Then,pref[bt][i][0]=pref[bt][i-1][0] + 1
andpref[bt][i][1]=pref[bt][i-1][1]
. If the bit is set to1
, thenpref[bt][i][1]=pref[bt][i-1][0]+1
andpref[bt][i][0]=pref[bt][i-1][1]
. Same idea with suffixes.Then we just iterate through the elements and multiply the amounts.
Thank you, your explanation is crystal clear. I completely trolled this.
deleted
deleted
question on C
We place a rook (i,i), resulting in the deletion of only the last row and column leaving an (i−1)×(i−1) grid. The number of final configurations in this case are given by dp[i−1]. and so on
but there are i positions on i x i grid, why we shouldn't add i * dp[i — 1]? Yes I know this will lead overcount but don't get exactly why, similarly why we shouldn't add (i * i — i) * dp[i — 2]
i have same question
Let's say you are left with $$$x$$$ unused rows/columns. For any unused row, you have 2 options-
1. Place white rook on $$$(r,r)$$$, which is a single pair, in which case you are left with $$$x-1$$$ unused rows/columns.
2. Place white rook on any $$$(r,c)$$$ such that $$$r$$$ $$$!=c$$$, which has $$$x-1$$$ pairs possible, in which case you are left with $$$x-2$$$ unused rows/columns, and as colour of rook matters, this case itself got 2 options as $$$(r,c)$$$ and $$$(c,r)$$$ generate equivalent solutions. So, finally our formula for any state, we will get-
$$$dp[i]=dp[i-1]+2*(i-1)*dp[i-2]$$$ where base case being $$$dp[0]=1$$$ and for $$$i<0$$$, $$$dp[i]=0$$$.
How are you getting $$$dp[i]=i*dp[i-1]+(i^2-i)*dp[i-2]?$$$
Place white rook on (r,r),... since there are i # of single pairs where r = 1,...,i from i x i grid that's where i * dp[n — 1] came from and similarly for i — 2 unused rows/columns case.
Why are you putting rook in $$$(r+i,r+i)$$$ when it's time for the $$$r^t$$$$$$^h$$$ row to get filled? We are not filling all the combinations at one go, we are going row by row and our $$$dp$$$ is taking care for the same. By your case, you are also giving preference to the order in which the rooks are getting placed which is overcalculation.
Let's say if we want to place white rooks at $$$(1,1)$$$,$$$(2,2)$$$ and $$$(3,3)$$$, your code gives $$$3! = 6$$$ by giving preference to the order of filling of rooks while in reality this should give answer $$$1$$$ as only three squares with three filling positions are there.
why base case dp[0]=1 ? i couldn't undestand that
dp[i] represents no of configuration's you can get by making valid moves upon having i rows and columns.
When building the recursion tree using all valid i rows and columns you will reach a state where you will not have any valid positions to place rooks i.e All rows/columns are restricted. That particular arrangement of rooks is only one valid configuration at that state.
How can we solve B if we change the condition to
a_i>0
I think the solution remains similar. Find such 2^x-2, so that you don't exceed sum of k if you fill 1s in the array(2^x-1+n <= k). e.g. n=4 and k=10, max x meeting the condition is 3, the answer code returns is 6, 1, 1, 2. However the solution is different for n=2. (I think it's 2^x-1 instead of 2^x-2)
I'm afraid your solution is wrong.For n=8 and k=19,you will get [6,1,1,1,1,1,1,7],whose bitcount is 3.But we can construct [1,2,4,8,1,1,1,1] with bitcount = 4
In this case $$$x=4$$$, so you put $$$2^x-2=14$$$, then fill the array with 1s. $$$14_{10}=1110_2$$$. I think I messed up the condition, it's $$$2^x-3+n\le k$$$ rather than $$$2^x-1+n\le k$$$. Apologies :)
Seriously?[14,1,1,1,1,1,1,1] is invalid since its sum is 21 and > 19. Besides,the max $$$x$$$ that satisfes $$$2^x-3+n\leq k$$$ is $$$3$$$ rather $$$4$$$ for $$$n=8,k=19$$$.Maybe you misread my case.
By the way,apparently the problem is unsolvable when $$$n>k$$$.And when $$$n=k$$$,you will get $$$x=1$$$ and put $$$2^1-2=0$$$,invalid too.Seems that there are quite a lot to consider.
Best div ever , even if you disagree B-)
I was criminally close to solving C. Just couldn't make correct dp. Good contest
Idk if this is another alternate solution but for Problem C I got the following:
where
x
runs over all even numbers between2
andn
. At the end, we addans=ans+1
to account for the case where all the rooks are on the diagonal.This is similar to the alternative solution in the editorial, you would obtain it by decomposing the $$$(m-c)!$$$ in odd and even terms, then use the even ones to simplify the $$$(\frac{m-c}{2})!$$$, leaving you with a power of two and the product of odd terms.
I think there is a mistake in the solution of D: The last sentence of para.2 "where $$$f(x,y−1)$$$ has $$$x$$$ set while $$$f(y+1,z)$$$ is unset." The $$$x$$$ should be replaced with $$$i$$$.
Or maybe I'm understanding the whole sentence wrongly?:) Plz tell me
Yup you're right, just fixed this typo in the editorial.
For problem C, my combinatorics approach was a bit different.
Assume that $$$c$$$ type-1 moves were played. Then we're left with an $$$(m - c) \times (m - c)$$$ grid where only type-2 moves are allowed. Since the order of the moves doesn't matter assume that he plays from left to right and always selects the left most column available. For his first move on the first selected column he has $$$m - c - 1$$$ available squares (-1 because the main diagonal is not allowed), for his second move, there are 2 fewer squares left. 1 because the row he played move 1 is unavailable and 1 because the row where the computer mirrored the first move is unavailable.
In total, the player will make $$$\frac{c - d}{2}$$$ moves and there are $$$(m - c - 1) (m - c - 3) (m - c - 5) ... = (m - c - 1)!!$$$ choices.
Now, for every move, the computer plays the mirror image. From the $$$\frac{m - c}{2}$$$ white-black rook pairs, the player could have selected either the position of the white rook or the black rook so to account for that we multiply by $$$2^{\frac{m-c}{2}}$$$.
The $$$+1$$$ is to account for the case where every rook is on the main diagonal.
This helped a lott!!!! by the way, i'm just curious to know if
(m−c−1)(m−c−3)(m−c−5)...=(m−c−1)!!
is just your notation or if at all there is a concept resembling with that of factorialsIt's called the double factorial
deleted
257439291 ez
257439291[submission:257439291]
Here: f(x,z)⊕ay>f(x,z) Doesn't this just mean that ay > 0 ?
No.$$$f(x,z) \operatorname{xor} a_y$$$ is not always greater than $$$f(x,z)$$$. Example:$$$f(x,z)=6$$$ and $$$a_y=2$$$.so that $$$f(x,z) \operatorname{xor} a_y = 4 \leq f(x,z) = 6$$$
Yes yes I get that, but I mean mathematically, why's taking the xor for both parts of the inequality is wrong?
I guess you mean that: if $$$a \geq b$$$, then $$$(a \operatorname{xor} c) \geq (b \operatorname{xor} c)$$$. It is obvious thar $$$(1 \operatorname{xor} 1) \lt (0 \operatorname{xor} 1)$$$ but $$$1 \geq 0$$$. Generally, the operator $$$\operatorname{xor}$$$ does not have associative laws as addition or subtraction. $$$(a+b) \operatorname{xor} c$$$ is not always equal to $$$a \operatorname{xor} c + b \operatorname{xor} c$$$. Hope to solve it. :D
Oh okay, Thanks.
can someone please explain the second part of dp transition in problem c?
Edit: Doubt cleared.
If we place a rook at $$$(i,j)$$$ and $$$i \neq j$$$,the computer will place a rook at $$$(j,i)$$$. The $$$i$$$-th row and the $$$j$$$-th row cannot be placed any rook now and the $$$i$$$-th column and the $$$j$$$-th column cannot be placed any rook as well. It just like the $$$i$$$-th row, the $$$j$$$-th row, the $$$i$$$-th column and the $$$j$$$-th column disappear from the board. So we will only consider the condition of $$$(n-2)\times (n-2)$$$ board (if the board is $$$(n \times n)$$$ now)
thank you for your response. i have understood it.
interesting problem D
Am I the only person to find D a lot easier than C ?
If I went to D before C maybe I would be a master now
I found logic easily for D but couldn't implement the solution (T_T).
what would be the approach of B if the question would have asked to maximize 1 using XOR operator?
Wow. Obviously I cannot solve E within the contest, but I managed to get the correct approach after 1 hour of thinking yesterday and 30 more minutes today. It's at least 3 twists. I didn't know Wilson's Theorem.
But I did it without the editorial!
Ayy, that's great! Discovering all the twists when coming up with the problem was soo fun, it honestly the best part about this problem imo. Hope you enjoyed solving it!
Roadmap:
--
once every j elements, cyclic-wise. (Twist 2) I was confident enough that I can code it and went to sleep.C的题解似乎出错了,没有考虑重点的情况
看错了sorry
hey guys! can u explain why I can ignore the exact positions of the rooks in the initial configurations and that only the number of free rows and columns matter.
initially we have rook on some squares. it will block entire row and col. after that we can't put rook on that row and col. now if we want put rook ,our new position will only depend on which row-col are currently available, not on the position of on initial rooks are placed on, so if we are ignoring them then why not resize board to (n-initial_row) size.
you can try to draw 4*4 picture,thinking about how to take two position,and then remove the rows and columns of two position,drawing any possiblity,I think you will find the law.
I am a pupil, and after I thought about the C for three hours, I did it using the combinations, and I feel good because I'm improving
what does the most significant bit in k mean?
MSB mean the last bit to the left who is 1 in binary representation
thank you for the problem E, for the first time I felt that I was not studying mathematics for nothing, when I realized that Wilson's theorem was applied there, sorry I didn't think of two difference arrays, but still thank you very much for the problem
Has anyone solved F without hashing?
A similar problem with only one path can be solved with MO's but I don't think it's possible in this scenario.
I also thought of persistent data structure for k-smallest elements but didn't figure out the hashing part, I still don't quite understand it well. What happens in the case where on the same path there are multiple nodes with the same value, do they contribute to the hash all in the same amount? and doesn't that increase the collision?
I'm not very strong in hashing, until now I thought in hashing the order of the values always matters to lower collision or is this wrong?
Whether the order of the hashed values matter depends on the hashing function, the XOR hashing or sum hashing mentioned in the article linked in the editorial are actually independent of the order. For the sum hashing (which is the one used in the editorial's solution) in particular the hash will be different if a particular element repeats a different number of times in both multisets.
Oh good to know. Thanks.
What was the difficulty rating of Problem A and B
Damn, really great problems. Its a shame i didnt know modularni inverse at the time but lnow i do.
Can anyone please refer more problems like C & D
in problem B ; my idea in contest was loop from zero to k and count each number number of 1 in binary representation and stock in a vector of pair and after sort it , i don't know what is wrong in my idea my sub : https://codeforces.net/contest/1957/submission/257638050
Can someone help me know what's going wrong in my solution for F1 and F2? 258029636
So basically my idea is very similar to the one in the tutorial, but I build a persistent segment tree on the Euler tour of the tree saving the entry of the node as (R + ar[node]) and the exit as inverse(R + ar[node])
In the queries it's kinda messy but I basically cut the the path into two parts for both u1,v1 and u2,v2 where the first path is: u -> LCA(u,v)
second path is: LCA(u,v) -> v
I also need to include the LCA into the answer separately.
I believe the complexity of this should be O(N * log^2(N)) but it's getting TLE.
Looks like really high constant factor. There are a lot of calls to
inv
. Changingpower
from recursive to iterative gives AC. Code Link. Also $$$log^2(n)$$$ is intended to fail F2. It is possible to modify the parallel binary search solution to also solve F2 in $$$knlog^2(n)$$$ by maintaining some deltas, but this will not be fast enough.Thanks a lot.
My solution is only log^2 due to calling inv and power in the query function, I just thought of precomputing some part of them.
The submission link isn't opening,
Sorry, not sure what the issue is, updated the link. Also for your implementation, I'm not sure but I believe it should be possible to store the inverse values for all the Segment tree nodes when building it. You would need to call
inv
only at the leaf nodes. Might also be possible to just use a double hash with a smaller modular field $$$\approx 10^6$$$ too. But all of these would increase the constant factor too, so not sure if it will AC even after removing the $$$log$$$.I changed
power
from recursive to iterative as you suggested to pass F1.I then changed the hashing type from
Hash = (R + val1)(R + val2)...
Which required me to use the inverse and power functions a lot.into
Hash = val1 * p[val1] + val2 * p[val2] + ...
Which allowed me to only add and subtract.Submission: 258066427. Thanks a lot.
In problem D's solution
cancels out an existing set bit in f(x,y−1)⊕f(y+1…r)
it should be
z
instead ofr
Fixed. Thank you
For Problem D,
ans += 1ll * pref[z][i - 1][1] * (1 + suff[z][i + 1][0]);
ans += 1ll * (1 + pref[z][i - 1][0]) * suff[z][i + 1][1];
Why are we adding 1 with the suffix and prefix?
What does these two line means ?
Can you explain?
adding 1, siginfies that we, dont take any suffix portion at all, just prefix and a[i] and similarly in 2nd equation , we just take a[i] and suffix (no prefix portion at all)
Can anyone explain what's wrong with my Solution
There is another solution for F in $$$O( n\sqrt n + q\frac{n}{b} + qkb )$$$ where $$$b$$$ is the block size which will be explained later. My implementation works in 3.5 seconds.258270314
Lets say that for every query we magically know $$$cnt_{1}$$$ and $$$cnt_{2}$$$ where $$$cnt_{1}[i]$$$ is number of nodes on path $$$u_{1}->v_{1}$$$ colored with color $$$i$$$, and $$$cnt_{2}$$$ is the same, but for $$$u_{2} -> v_{2}$$$. How could we find $$$k$$$ colors $$$i$$$ such that $$$cnt_{1}[i] \neq cnt_{2}[i]$$$?
Brute-force way would be to iterate $$$i$$$ from $$$1$$$ to $$$n$$$ and check for $$$cnt_{1}[i] \neq cnt_{2}[i]$$$. A bit faster way would be to split the colors from $$$1$$$ to $$$n$$$ into blocks of size $$$b$$$, and maintain xor-hash for each block(the things that are hashed are ordered pairs $$$(i,cnt[i])$$$, and we can do that by assigning a random integer for every such ordered pair, because there are $$$O(n)$$$ of them), and then we can traverse all the $$$\frac{n}{b}$$$ blocks and in $$$O(1)$$$ check if the pairs of blocks are identical, if a pair is not identical, we can iterate through that pair of blocks and straightforwardly check at which color they do not coincide, that will take $$$O(b)$$$ time per block and we will have to check at most $$$O(k)$$$ blocks per query. This would yield $$$O(\frac{n}{b} + kb)$$$ per query.
In order to do this, we need to somehow get rid of the "magically" part from the be second paragraph.
We can easily see that we can calculate the $$$cnt$$$ array along with the $$$hash$$$ array($$$hash[i]$$$ will be the xor-hash of $$$i$$$-th block of size $$$b$$$) for each $$$u->v$$$ that appears in the queries(2 per query) in $$$O(n\sqrt n)$$$ with MO. The problem with this is that we need to have the $$$cnt$$$ and the $$$hash$$$ array for $$$u_{1}->v_{1}$$$ and $$$u_{2}->v_{2}$$$ at the same time. We will try to solve that problem by running MO 2 times and memorizing some stuff in between those 2 runs.
We will run the first MO on all the $$$2q$$$ paths to find out for each query at most $$$k$$$ indices of blocks in the $$$cnt$$$ array which don't coincide, and we will memorize those block indices. To do this, for every query can have $$$hash_{i,1}$$$ and $$$hash_{i,2}$$$ which will be the state of the $$$hash$$$ array at the $$$i$$$-th query. This will take $$$O(q\frac{n}{b})$$$ memory to memorize(note: we can do it with $$$1$$$ array per query instead of $$$2$$$). After finishing the first MO we can easily recover, for each query, which blocks will have at least one non-coinciding color.
We will run the second MO on the same $$$2q$$$ paths, but now, instead of memorizing the $$$hash$$$ array, we will memorize, for each query, the $$$O(k)$$$ blocks whose indices we memorized in the first MO. This will take $$$O(kb)$$$ memory per query. After MO finishes, we can then check all the blocks that we memorized, and find the colors which do not coincide(this part can also be done with just $$$1$$$ array per query).
By setting the $$$b$$$ to $$$\sqrt \frac{n}{k}$$$, which in this case is $$$100$$$, we get a complexity that should barely pass.
Can everyone help me? 1957C - How Does the Rook Move? why we are supposed to let dp[0] = 1 according to the official solution?According to my solution 257649223,i let a[0] = 0,but it is wrong.However,in 257649430,i let a[0] = 1,and it is right.Why is that?
F1 can be possibly solved using 4 times Mo's Algorithm + Hashing on a euler path by first scanning the upper square root part and then the lower square root part reaching complexity of $$$O((N+Q) (\sqrt{N} + \sqrt{Q}))$$$. It is also possible to use two hashes to further more avoid collision and meeting time limit. But in my case I need to control the memory to fit the memory constraint because my solution's memory consumption will also be $$$O(Q \sqrt N)$$$. Also, I needed to use winlib's 64 bit GCC to pass the question. Using 32 bit environment will fail to pass.
For problem C,Can someone provide me the prove of the (m-c)!/((m-c)/2)! is the case number. It seems very interestring. Thanks
F1 can be solved by maintain frequency table's rolling hash of each path from a vertex to root using persistent segment tree, and use binary search on segment tree to find the first different frequency between two path, and the time complexity would be $$$O(n\lg C + q\lg C)$$$
here is my implementation
Is there an implementation for the alternative solution of problem C? This was my initial idea but I discarded it because I had no idea how to calculate that term in the required time complexity. We have to iterate $$$c$$$ over all values from $$$0$$$ to $$$m$$$ which needs $$$O(m)$$$. Since $$$m \le n \le 10^5$$$ that leaves us with $$$O(log(m))$$$ to calculate
. As far as I know, it takes $O(k)$ to calculate $$$k!$$$. Of course, we could prepare a lookup table for factorial values mod $$$10^9 + 7$$$ but then we will get problems with dividing. I would really appreciate to see a solution to this.
There exists something called modular inversion which enables to divide two numbers that are some modulo remainders. Here is my solution that you can check out.
Thank you!
Comment should be there in editorial, It gets unnecessarily difficult to figure out what the writer has coded
This is the solution for Question D... Please look at the editorial, then see my explaination you will surely get it easily
link of image, i wrote it in notebook
https://ibb.co/bgcCqXp
Look at my submission, i commented it out.
[submission:https://codeforces.net/contest/1957/submission/262824863]
262824863
code well and never give up :)
![ ]()
i am very sorry, that will be xor(x,y-1)^(y+1,z)=1
The dp solution to C is elegant. Nicely written ,W editorialists and authors.
Approach for D was great
Ok
Ok