### DarthKnight's blog

By DarthKnight, 6 years ago, ### Div.2 A — Cursed Query

You should make a sequence s1, s2, ..., sn such that si = a1 + a2 + ... + ai and use a binary search to find the first element that is greater than t % sn (or upper_bound function in C++ ).

Source code : Here

### Div.2 B — Troynacci Query

First of all, compute sequence f (0-based), then consider we have a sequence p (also 0-based) (partial sum), initially all members are 0.

For each query, if l < r, then do :

			p[l] = (p[l] + f) % mod;
p[l+1] = (p[l+1] + f) % mod;
p[l+1] = (1LL * p[l+1] + mod - 1LL * ((1LL * b * f) % mod)) % mod;
p[r + 1] = (1LL * p[r+1] + mod - f[r - l + 1]) % mod;
p[r + 2] = (1LL * p[r+2] + mod - 1LL * ((1LL * a * f[r-l]) % mod)) % mod;


otherwise, do this :

			p[l] = (p[l] + f)%mod;
p[r+1] = (1LL * p[r+1] + mod - ((1LL * b * f)%mod))%mod;
p[r+2] = (1LL * p[r+2] + mod - 1LL * ((1LL * a * f)%mod))%mod;


An the just run this : for every i, staring from 0, pi +  = a × pi - 2 + b × pi - 1 and ai +  = pi .

Source code : Here

### A — LCM Query

If we have an array x1, x2, ..., xm and for each i, 1 ≤ xi ≤ 60, the number of different element in the array y1, y2, ..., ym such that yj = lcm(x1, x2, ..., xj), is at most log(60!) .Because y1 ≤ y2 ≤ y3 ≤ ... ≤ ym and if yi < yi + 1, then yi ≤ 2 × yi + 1, and ym ≤ 60! .

Actually, it is even less, like 25.

So for each i, you can find all these members for array ai, ai + 1, ..., an using at most 25 binary searches and save them in an array.

And if x = p1b1 × ... × pkbk such that all pis are prime an k = the number of primes less than 60, then we assign sequence b to x. Using this, you can easily see that if x = p1b1 × ... × pkbk and y = p1c1 × ... × pkck, lcm(x, y) = p1max(b1, c1) × ... × pkmax(bk, ck). And for check if a number is less than another one using this sequence b, you can use log function and the fact that log(x) = log(p1b1) + ... + log(pkbk), so if log(x) < log(y) then, x < y, and this is how to calculate the minimum value.

By the way, you can calculate lcm(al, al + 1, ..., ar) in O(25) using Sparce Table.

Source code : Here

### B — ShortestPath Query

Consider, for each vertex v an each color c that there is at least one edge entering v with color c, we have the length of the shortest path from s to v such that it's last edge has color c (we call this dv, c). So, with this, you can make a graph with states (v, c) and run a Dijkstra on it and it's easy update.

But this will get TLE.

If you think about that, you don't need all states (v, c), among all these states, we just need the first two states with minimum value of d (for each vertex v).

Source code : Here

### C — Subrect Query

First of all, let's solve the 1-D version :

we have two sequences a1, a2, ..., an and b1, b2, ..., bn and for each i, we know that bi ≤ ai. Our goal is to calculate the number of pairs (l, r) in O(n) such that 1 ≤ l ≤ r ≤ n and max(al, al + 1, ..., ar) - min(bl, bl + 1, ..., br) ≤ k .

We use two double ended queues (deques) for this propose :

let mx, mn be two empty deques
l = 1
ans = 0
for r = 1 to n
while !mx.empty() and a[mx.back()] <= a[r]
mx.pop_back()
while !mn.empty() and b[mn.back()] >= b[r]
mn.pop_back()
mx.push_back(r)
mn.push_back(r)
while a[mx.front()] - b[mn.front()] > k
l ++
if mx.front() < l
mx.pop_front()
if mn.front() < l
mn.pop_front()
ans += r - l + 1


In this code, for each r we are finding the largest valid l, and by the way a[mx.front()] = max(al, al + 1, ..., ar) and b[mn.front()] = min(bl, bl + 1, ..., br) .

Now let's get back to the original problem.

For each pair (i, j) such that 1 ≤ i ≤ j ≤ m, build arrays a1, a2, ..., an and b1, b2, ..., bn such that ak = max(ak, i, ..., ak, j) and bk = min(ak, i, ..., ak, j) and then run the code above.

Except that C++ deque is too slow,so you should write one.

Source code : Here

### D — TROY Query

For each row or column, it's not important how many times we run the operation on it, the only thing matters, is that it's odd or even.

So, assign a boolian to each row and each column, such that row number i's boolian is ri and column j's boolian is cj.

The other things are like 2-sat, except that the graph in this problem will be undirected.

For each query, if ax, y = bx, y so we know that so add an edge between rx and cy and one between ¬rx and ¬cy.

Otherwise, add an edge between ¬rx and cy and one between ¬cy and rx .

You can use a disjoint set with array or vector and in each step, check if a boolian like x and ¬x are in the same component, print "No" for the rest of the queries (Because when the answer to a query is No, the answer to the next queries will be also No).

Source code : Here

The other approach is to use binary search on the last step with answer "Yes" and check using a normal 2-sat (directed graph.)

Source code for this approach : Here

### E — Palindrome Query

Use Robin-Carp. Let's consider that hi ≡ s1 × p0 + s2 × p1 + ... + si × pi - 1(mod m) .

For a query of type 2 or 3, just use a simple binary search.

For a modify query, if y = x - sp, you should add y × p0 to hp, y × p1 to hp + 1 and so on. You can do all these using a segment tree or fenwick (BIT).

Source code : Here

### F — Tree Query

Use divide and conquer on the tree (centroid decomposition) and answer queries offline.

For conquer, imagine root is r. Run dfs on r and for each vertex, push it's distance to r in the vector e. Then sort e and for each vertex v in subtree of r and query o such that it's asking about v and number l, do this : ans[o] += the number of members of e like p such that p + d(r,v) <= l (using binary search).

But here, we counted some vertices for some queries more than once.

Then for each neighbor of r do this separately:

Run dfs on it's subtree and for each vertex, push it's distance to r in the vector z. Then sort z and for each vertex v in this subtree and query o such that it's asking about v and number l, do this : ans[o] -= the number of members of z like p such that p + d(r,v) <= l (using binary search).

Source code : Here Tutorial of Hello 2015 (Div.1) Tutorial of Hello 2015 (Div.1) Tutorial of ICPC Training Tutorial of Upsolving  Comments (36)
 » thank for nice problem :)
 » Really nice editorial and thanks for adding source codes :D
 » nice solution for problem B Div 2 :)
 » these problem isn't nice these are very nice :)
 » thanks !
 » 6 years ago, # | ← Rev. 3 →   Well...In problem C,I have't realized the Array can be so long...T_Tconst int N = 404;int mn[N][N]NI finished it by rmq.May be use rmq query the biggest and smallest is better .Thanks for solutions,and thanks for problem's tags before the solutions.(I solve all problems by tags and tags Allows me to be more independent thinking!) Nice problems and nice solutions! :D
 » Why can't i see the solutions of other contestants? I'm new.
•  » » Because this is a GYM contest. GYM submissions are not visible until you solve the problem.
 » 6 years ago, # | ← Rev. 3 →   Can you please explain problem B Troynacci Query more?I can not understand.
•  » » Read this (partial sum) before that.
•  » » » I have read this and understood but cannot find the logic of the solution of problem B. Can you explain more? :|
•  » » » » Same, please someone explain Div2 B.
 » In div2 A testcase 13 when I define maxn 100000+10 it gets WA but maxn 100000+100 gets AC How come??
 » Just a fun question, does the "Khikulish" sentence in Div2 problem A mean anything?
•  » » Khikuland is a very useful name for countries in problems of INOI (Iran Olympiad in Informatics).
 » Problem A — LCM Query, could anyone explain first part of solution:"If we have an array x1, x2, ..., xm and for each i, 1 ≤ xi ≤ 60, the number of different element in the array y1, y2, ..., ym such that yj = lcm(x1, x2, ..., xj), is at most log(60!) .Because y1 ≤ y2 ≤ y3 ≤ ... ≤ ym and if yi < yi + 1, then yi ≤ 2 × yi + 1, and ym ≤ 60! .Actually, it is even less, like 25.So for each i, you can find all these members for array ai, ai + 1, ..., an using at most 25 binary searches and save them in an array."Having sparse table, how do you quickly calculate mininum lcm of intervals of length x(x=1..n)?
 » Plz Anyone explain me solution for problem B.I also tried to understand partial sums from given link,but i could not.Plz help.
 » Problem F :It can also be solved by answering the queries online (using centroid decomposition). We decompose the given tree and for each node in the centroid tree , we maintain the following two vectors : ans[u] = sorted vector of d(x,u) for all x in the subtree of u in centroid tree, where d(x,u) represents the distance between node x and u in the original tree.cntbn[u] = sorted vector of d(x,par[u]) for all x in the subtree of u in centroid tree, where d(x,par[u]) represents the distance between node x and par[u] in the original tree. (par[u] is the parent of node u in centroid tree). Since, there are at-most logN levels in centroid tree, and at each level we are storing O(N) values of ans/cntbn, total memory required would be O(NlogN). Also, these vectors can easily be build in O(NlogN) or O(Nlog^2N) time by moving up node u (for all u) in centroid tree and adding the corresponding values in all the ancestors of u. Given this information, each query would now reduce to int query(int u,LL l) { int x = u; LL d = l; int ret = upper_bound(ALL(ans[x]),d)-ans[x].begin(); while(1) { if(x==par[x])break; LL dd = l-dist(u,par[x]); int add = upper_bound(ALL(ans[par[x]]),dd)-ans[par[x]].begin(); int subt = upper_bound(ALL(cntbn[x]),dd) - cntbn[x].begin(); ret+=add-subt; x = par[x]; } return ret; } http://codeforces.com/gym/100570/submission/12316350
•  » » First of Thank you for the blog, Baba!this problem is so elegant to be solved using Centroid decomposition, that I cannot keep myself from appretiating. All the submissions for this prob are hidden. So I am posting my solution here for convenience.If anyone is not using windows and want to see what is going on use -DWIN32 as a flag and if someone on windows wants to remove all the excess messages -DWIN32 flag while compiling. //Optimise #include using namespace std; // #define multitest 1 #ifdef WIN32 #define db(...) ZZ(#__VA_ARGS__, __VA_ARGS__); #define pc(...) PC(#__VA_ARGS__, __VA_ARGS__); template ostream &operator<<(ostream &out, const pair &p) { out << '[' << p.first << ", " << p.second << ']'; return out; } template void PC(const char *name, Arg &&arg) { std::cerr << name << " { "; for (const auto &v : arg) cerr << v << ' '; cerr << " }\n"; } template void ZZ(const char *name, Arg1 &&arg1) { std::cerr << name << " = " << arg1 << endl; } template void ZZ(const char *names, Arg1 &&arg1, Args &&... args) { const char *comma = strchr(names + 1, ','); std::cerr.write(names, comma - names) << " = " << arg1; ZZ(comma, args...); } #else #define db(...) #define pc(...) #endif using ll = long long; #define f first #define s second #define pb push_back const long long mod = 1000000007; auto TimeStart = chrono::steady_clock::now(); const int nax = 2e5 + 10, Log = 19; vector> Adj[nax]; int dp[Log][nax], Level[nax]; bool vis[nax]; ll Dist[nax]; void Lca(int n) { memset(dp, -1, sizeof(dp)); queue Q; Q.push(0); vis = true; while (!Q.empty()) { auto top = Q.front(); Q.pop(); for (auto child : Adj[top]) if (!vis[child.f]) { Level[child.f] = 1 + Level[top]; Dist[child.f] = Dist[top] + child.s; dp[child.f] = top; vis[child.f] = true; Q.push(child.f); } } for (int i = 1; i < Log; ++i) for (int j = 0; j < n; ++j) if (dp[i - 1][j] != -1) dp[i][j] = dp[i - 1][dp[i - 1][j]]; } int lca(int a, int b) { if (Level[a] > Level[b]) swap(a, b); int d = Level[b] - Level[a]; for (int i = Log - 1; i >= 0; --i) if (d & (1 << i)) b = dp[i][b]; if (a == b) return a; for (int i = Log - 1; i >= 0; --i) if (dp[i][a] != dp[i][b]) { a = dp[i][a]; b = dp[i][b]; } return dp[a]; } ll dist(int a, int b) { return Dist[a] + Dist[b] - 2 * Dist[lca(a, b)]; } int currentSize, subTreeSize[nax], parCentroid[nax]; bool Computed[nax]; void dfs1(int node, int par) { currentSize++; subTreeSize[node] = 1; for (auto child : Adj[node]) if (child.f != par && !Computed[child.f]) { dfs1(child.f, node); subTreeSize[node] += subTreeSize[child.f]; } } int getCentroid(int node, int par) { for (auto child : Adj[node]) if (child.f != par && !Computed[child.f]) if (subTreeSize[child.f] > currentSize / 2) return getCentroid(child.f, node); return node; } vector Ct[nax]; int root = -1; vector distancesToChildren[nax], distancesToChildrenfromParent[nax], inChildTree[nax]; void decompose(int node, int par) { if (Computed[node]) return; currentSize = 0; dfs1(node, par); int centroid = getCentroid(node, par); if (par == -1) { root = centroid; parCentroid[centroid] = centroid; } else { Ct[centroid].pb(par); Ct[par].pb(centroid); parCentroid[centroid] = par; } Computed[centroid] = 1; for (auto child : Adj[centroid]) if (child.f != par && !Computed[child.f]) decompose(child.f, centroid); } int query(int node, ll len) { int ret = 0, curr = node, prev = -1; ret += upper_bound(distancesToChildren[node].begin(), distancesToChildren[node].end(), len) - distancesToChildren[node].begin(); while (true) { if (parCentroid[curr] == curr) break; ll d = len - dist(node, parCentroid[curr]); int sub = upper_bound(distancesToChildrenfromParent[curr].begin(), distancesToChildrenfromParent[curr].end(), d) - distancesToChildrenfromParent[curr].begin(); curr = parCentroid[curr]; int add = upper_bound(distancesToChildren[curr].begin(), distancesToChildren[curr].end(), d) - distancesToChildren[curr].begin(); ret += add - sub; } return ret; } void prepareForQueries(int node, int par) { inChildTree[node].pb(node); distancesToChildren[node].pb(0); if (par != -1) distancesToChildrenfromParent[node].pb(dist(par, node)); for (auto child : Ct[node]) if (child != par) { prepareForQueries(child, node); for (auto grandChild : inChildTree[child]) { inChildTree[node].pb(grandChild); distancesToChildren[node].pb(dist(node, grandChild)); if (par != -1) distancesToChildrenfromParent[node].pb(dist(par, grandChild)); } } sort(distancesToChildren[node].begin(), distancesToChildren[node].end()); sort(distancesToChildrenfromParent[node].begin(), distancesToChildrenfromParent[node].end()); db(node, par); pc(Ct[node]); pc(inChildTree[node]); pc(distancesToChildren[node]); pc(distancesToChildrenfromParent[node]); } void solve() { int n, q, u, v, w; cin >> n >> q; for (int i = 1; i < n; ++i) { cin >> u >> v >> w; --u, --v; Adj[u].pb({v, w}); Adj[v].pb({u, w}); } db("Lca Start"); Lca(n); db("Lca End Decompose Start"); decompose(0, -1); db("Decompose End prepareforqueries Start"); prepareForQueries(root, -1); db("prepareforqueries end"); ll len; while (q--) { cin >> u >> len; --u; cout << query(u, len) << '\n'; // flush(cout); } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; #ifdef multitest cin >> t; #endif while (t--) solve(); #ifdef WIN32 cerr << "\n\nTime elapsed: " << chrono::duration(chrono::steady_clock::now() - TimeStart).count() << " seconds.\n"; #endif return 0; } 
•  » » 11 months ago, # ^ | ← Rev. 3 →   Found It :| , I used cnt[u] instead of cnt[cur]Getting WA on test case 3...Can you check this solution, https://ideone.com/yIUf9t
 » In the code of the Problem F, can you please tell me why you have written w-h[u] in line 70 and 71?
•  » » reason : we only calculate the node which one not connected further when we remove centroid.
 » Can you please prove problem B solution.
•  » » 5 years ago, # ^ | ← Rev. 2 →   An explanation for the first approach: when you get a query {l, r}, you need the following change: a[l] += f a[l+1] += f .. .. a[r-1] += f[r-l] a[r] += f[r-l+1] Suppose you keep an array p[], initially all zero, and do this: p[l] += f ...(1) p[l+1] += f - b*f ...(2) p[r+1] += -f[r-l+2] ...(3) p[r+2] += -a*f[r-l+1] ...(4) And now if you apply the recursion p[i] += a*p[i-2] + b*p[i-1] for all i, you get the corresponding update. I'll try to show this too:See that once you start applying the recursion on array p[], this is the result: p[l-k] = 0, k > 0, since we have assigned nothing here. p[l] += a*p[l-2] + b*p[l-1] = a*0 + b*0 = 0 i.e., p[l] -> (f[l]) + 0 = f p[l+1] += a*p[l-1] + b*p[l] = a*0 + b*p[l] = b*f i.e., p[l+1] -> (f - b*f) + b*f = f now that you have successfully got p[l] and p[l+1] as f and f respectively, you'll get f[i] correctly up to p[r] because of the formula you are applying constantly.Beware, you don't want these values to affect further. Hence we need to keep some values at p[r+1] and p[r+2] already so that their net values after this recursion turns out to be zero, if we do this correctly, no further effects will be observed starting from p[r+3], since previous 2 values will be 0 then.This is why we've got (3) and (4): p[r+1] += a*p[r-1] + b*p[r] = a*f[r-l] + b*f[r-l+1] = f[r-l+2] i.e., p[r+1] -> (-f[r-l+2]) + f[r-l+2] = 0 p[r+2] += a*p[r] + b*p[r+1] = a*f[r-l+1] + 0 = a*f[r-l+1] i.e., p[r+2] -> (-a*f[r-l+1]) + a*f[r-l+1] = 0 Hence, once you make the changes (1), (2), (3), and (4) to array p[], you have assured that the corresponding query will be handled as soon as we do the recursive additions in p[].And hence you may as well do this recursive addition at the very end, to result in O(n+q) solution.Check it yourself that the author has provided exactly these 4 updates for each query {l, r}.
•  » » » Thank you so much!
•  » » » Thank you very much. Finally I can understand the solution.
•  » » » » He was waiting for 9 months to get this reply from you. Thanks for making his long desired wish true :P
•  » » » » » xD. I read the problem long time ago. But I din't read the editorial before. It help me a lot. (Sorry for my poor English)
 » Can someone explain problem LCM QUERY of div 1 A I am facing difficulty in understanding these lines of editorialIf we have an array x1, x2, ..., xm and for each i, 1 ≤ xi ≤ 60, the number of different element in the array y1, y2, ..., ym such that yj = lcm(x1, x2, ..., xj), is at most log(60!) .Because y1 ≤ y2 ≤ y3 ≤ ... ≤ ym and if yi < yi + 1, then yi ≤ 2 × yi + 1, and ym ≤ 60! . Actually, it is even less, like 25Thanks!
 » Nice editorial, really helped me, like the sources codes that you've added.
 » Can someone explain why we add MOD value in the middle of expression when the answer is asked to be mod? Isn't it enough to just calculate all values and take their mod?
•  » » In cpp % (**modular division**) operator may return negative values, whereas we don't want any negative values here. So, to ensure the remainder we get after using % operator is non-negative, we add mod to the expression. cout << (-7 % 3) ; output: -1In python there is no such issue, and we also get a non-negative result on using the % operator.
 » I was trying to solve B.Shortest path Query but I'm getting WA. the tryoic path means that no consecutive edges should have same color that's it, right? please help me!
 » In editorial TROY Query, Because when the answer to a query is No, the answer to the next queries will be also No. Can someone explain me why?
 » 7 months ago, # | ← Rev. 3 →   (Removed)
 » 5 weeks ago, # | ← Rev. 2 →   I know this comment a bit stupid.but i can't reason why this code is failing for F? i was practicing centroid decomposition this is the first problem i got stuck at. CodeInfo about code : The code is based on very same logic as written in tutorial.Data:tree (vector>) it store node and weight.d[N] it stores weight of path from a centroid from a certain level to node. e.g. dp[level[par]][node].sz[N] it store subtree size of node.dead[N] it store nodes as 1 if they are dead else 0.level[N] it stores level of a node in centroid tree.par[N] it stores parent of a node in centroid tree.list(N) it store the node that is a child of its parent in centroid tree.dist (vector>>) it stores required weights of path vectors for each node.functions : subtree() it calculates subtree sizes and return the size of mega node.OneCentroid() it returns centroid of tree.Decompose() it decomposes and main function for centroid decomposition. it also calculates the the required weight of paths vectors.caldist() it calculated weight of paths vectors.solution() just a fancy funtion to call decomposeans() it process query. #include #include #include #include #include using namespace std; #define MaxN 100000 vector>> dist; vector link; int sz[MaxN], level[MaxN], dead[MaxN], par[MaxN]; long long int d[MaxN]; int subtree(int now, int from, vector>>& tree) { sz[now]=1; for (auto& [to,w]:tree[now]) if (to!=from&&!dead[to]) sz[now]+=subtree(to,now,tree); return sz[now]; } int OneCentroid(int now, int from, int size, vector>>& tree) { for (auto& [to,w]:tree[now]) if (to!=from&&!dead[to]&&sz[to]>(size/2)) return OneCentroid(to,now,size,tree); return now; } void caldist(int now, int from, long long int x, int l, int sub, int cent, vector>>& tree) { d[l][now]=x; dist[cent][cent].push_back(x); dist[cent][sub].push_back(x); for (auto& [to,w]:tree[now]) if (to!=from&&!dead[to]) caldist(to,now,x+w,l,sub,cent,tree); } void decompose(int now, int from, int l, vector>>& tree) { int cent=OneCentroid(now,from,subtree(now,from,tree),tree); dead[cent]=1; level[cent]=l; par[cent]=from; d[l][cent]=0; link[cent]=now; dist[cent][cent].push_back(0); for (auto& [to,w]:tree[cent]) if (to!=from&&!dead[to]) caldist(to,cent,w,l,to,cent,tree); sort(dist[cent][cent].begin(), dist[cent][cent].end()); for (auto& [to,w]:tree[cent]) if (to!=from&&!dead[to]) sort(dist[cent][to].begin(), dist[cent][to].end()); for (auto& [to,w]:tree[cent]) if (to!=from&&!dead[to]) decompose(to,cent,l+1,tree); } void solution(vector>>& tree, int n) { dist.resize(n); link.resize(n); decompose(0,-1,0,tree); // cerr << "link[]={"; // for (int i=0; i& v, long long int val) { return upper_bound(v.begin(), v.end(), val)-v.begin(); } int ans(int id, long long int l) { int ret=index(dist[id][id],l); for (int u=id; ~par[u]; u=par[u]) { if (d[level[par[u]]][id]>l) break; ret+=index(dist[par[u]][par[u]],l-d[level[par[u]]][id])-index(dist[par[u]][link[u]],l-d[level[par[u]]][id]); } return ret; } ostream& operator<<(ostream& os, array& a) { return os << "(" << a << ", " << a << ")"; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, q; cin >> n >> q; vector>> tree(n); for (int i=1, u, v, w; i> u >> v >> w; --u, --v; tree[u].push_back({v,w}); tree[v].push_back({u,w}); } // cerr << "Tree :\n"; // for (int i=0; i> id >> l; cout << ans((int)id-1,l) << '\n'; } return 0; } Thankyou if you can help.