### chokudai's blog

By chokudai, history, 12 months ago, We will hold AISing Programming Contest 2021（AtCoder Beginner Contest 202）.

We are looking forward to your participation! Comments (39)
 » The upcoming ARC , i.e. on this Sunday , clashes with Google Kickstart , Can't it be preponed or postponed?
 » First time I was able to solve more than 3 questions!!
 » How to solve D? Thanks.
•  » » Suppose you're at i'th character and you have used z number of a's. You count the total number of combinations possible from (n-i) characters and z-1 a's. Let's call this c. If this count is more than k, that means you can afford to put 'a' at the current position, else you have to put 'b'. When you put 'b', reduce k by c.
•  » » 12 months ago, # ^ | ← Rev. 8 →   Here is what I believed to be a straightforward approach:Understand that kth lexicographically shortest string means that there will be $total — k$ strings that will be lexicographically greater than it. An alternate way of saying that is that you have to leave $total — k$ strings behind. Let us call this number $remaining$. It is not difficult to compute that, $total = nCr(a+b, a) = nCr(a+b, b)$ $remaining = total - k$Now iterate over every position from 0 to n-1, and keep track of the remaining number of a and b. In every position, we have 2 possibilities. Putting either a, or b. Now if we put an 'a' in the current position, how many strings are we immediately getting ahead of? Those many in which there would be a 'b' in the current position, right? That number is, $nCr(a+b-1, b-1)$Now, if it is OK to leave behind those many strings, we put an 'a' here, and accordingly update the remaining Else, we put a 'b'. How do we understand if it is OK to put an 'a'? The condition is, $remaining >= nCr(a+b-1, b-1)$What if once remaining becomes 0? Well, that means we have no more strings to leave behind. We can then simply create the lexicographically shortest string possible from that position. That is by printing all b's first and then the a's. But it is also fine to go with the flow and check manually as I did. Here is my submission following this approach.
•  » » » Thank you, very detailed and understandable explanation.
•  » » » Thanks you for the explanation. This one is really helpful.
 » 12 months ago, # | ← Rev. 3 →   this is my depth first search for E. I am maintaining a map for every node in which I have kept a count of number of having a distance x from the node.But I am getting tle on few test cases to help me how to optimize it.submission link : https://atcoder.jp/contests/abc202/submissions/22827434  vector> l(nax); void dfss(int u , int p = -1){ for(auto x : edges[u]){ if(x != p){ dfss(x,u); } } l[u] = 1; for(auto x : edges[u]){ if(x != p){ for(auto y : l[x]){ l[u][y.first+1] += y.second; } } } }
•  » » 12 months ago, # ^ | ← Rev. 2 →   You can use a count array and solve the queries offline. All you need is the euler tour of the tree. The entire problem will be solved in linear time. code
 » Wow, I feel so lucky to get the first place! I recently came across a problem very similar to F, which I think might be the reason.
•  » » 12 months ago, # ^ | ← Rev. 2 →   could you explain your thought process for F, I got that we have to use DP somehow with triangle decompositions and the fact that triangle area*2 is integer, but what was the main cracking hint for you for this question.
•  » » can you please explain your solution and share the link to a similar problem?
 » 12 months ago, # | ← Rev. 3 →   Interesting technique for E in the editorial!I wonder if anyone else answered the queries offline using small-to-large merging (https://codeforces.com/blog/entry/67696). For each node u, we can track the multiset of depths of descendents of u, and use this to answer the queries involving u. Then the multiset for u is the union of the multisets of its children, plus a singleton set with the depth of u. In fact this is almost exactly the same as the linked problem, where the colour of a node is its depth.
•  » » I did it offline with small to large merging — https://atcoder.jp/contests/abc202/submissions/22827419 Codemap> queries; for (int i = 0; i < q; i++) { int u, d; re(u, d); u--; queries[u].push_back({i, d}); } vector> depth(n); vi ans(q); for (int u : reversed(tr.preorder)) { depth[u][tr.depth[u]]++; if (queries.count(u)) { for (auto &[i, d] : queries[u]) ans[i] = depth[u][d]; } if (tr.parent[u] != -1) { int p = tr.parent[u]; if (sz(depth[p]) < sz(depth[u])) swap(depth[p], depth[u]); for (auto &[k, v] : depth[u]) depth[p][k] += v; } } for (int i : ans) ps(i); 
•  » » 12 months ago, # ^ | ← Rev. 2 →   I did the same. Luckily, I had solved a problem with the same technique today itself. I think it can be done with Euler tour+ binary search as well but this way seemed much more easier to code.PS.-Just saw that the editorial has much more cleanly implemented the Euler tour method, contrary to my expectations.
 » Wow, there's already a detailed official English editorial (https://atcoder.jp/contests/abc202/editorial). Is that going to be the case for ABCs going forward?
•  » » For the last 10 contests I have seen that editorials are available as soon as contest ends.
 » 12 months ago, # | ← Rev. 5 →   Can somebody help me identify my mistake in E? My solution uses the same idea as the one from the editorial. https://atcoder.jp/contests/abc202/submissions/22829588Edit: I found the issue — I was binary searching for "out[u]" on the out time array... but have to do both binary searches (in[u] + out[u]) on the in time arrayhttps://atcoder.jp/contests/abc202/submissions/22839873
•  » » It's been six months. I'll share my approach for E. An easy observation is that we only have to count the # of nodes in subtree of U with depth D from the root. First, find the dfs_order & depths & subtree_size of the tree in one dfs. Then, we can perform offline queries with MO's algorithm to count # of nodes in range with depth D My submission
 » 12 months ago, # | ← Rev. 2 →   I solved E with the help of merge-sort tree. We can create a pair of entry time and distance for every node and sort them on the basis of entry time. Then after handling some cases (i.e when Di is less than distance of root from Ui.), we just have to count number of values equal to D in the range entry time[u] and exit time[u] for which I used merge sort tree.
•  » » Hermit can you please share you submission, Thanks!
•  » » » sure, (A bit ugly code though) Spoiler//#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector") #include #include #include #include #include using namespace std; #define ll long long #define endl '\n' #define mod 1000000007 #define pb push_back #define ff first #define ss second #define con continue #define ub upper_bound #define lb lower_bound #define si(x) int(x.size()) #define sum_all(a) ( accumulate ((a).begin(), (a).end(), 0ll)) #define mine(a) (*min_element((a).begin(), (a).end())) #define maxe(a) (*max_element((a).begin(), (a).end())) #define mini(a) ( min_element((a).begin(), (a).end()) - (a).begin()) #define maxi(a) ( max_element((a).begin(), (a).end()) - (a).begin()) #define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin()) #define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin()) const double pi = 2 * acos(0.0); const int dx[] = { -1, 0, 1, 0 }; const int dy[] = { 0, -1, 0, 1 }; const int dx8[] = { -1, 0, 1, 0,1,1,-1,-1 }; const int dy8[] = { 0, -1, 0, 1,1,-1,1,-1 }; ll min(ll a, ll b) { if (a < b)return a; return b; } ll max(ll a, ll b) { if (a > b)return a; return b; } ll ceil1(ll a, ll b) { return(a + b - 1) / b; } void read(vector & arr) { for (ll i = 0; i < si(arr); i++) cin >> arr[i]; } void read_graph(vector>& g, ll m) { while (m--) { ll x, y; cin >> x >> y; x--, y--; g[x].pb(y); g[y].pb(x); } } template struct segtree { private: int s, _n; vector st; void construct(int pos, int l, int r, vector& ind) { if (l == r) { st[pos] = ind[l]; return; } int mid = (l + r) / 2; construct(pos * 2 + 1, l, mid, ind); construct(pos * 2 + 2, mid + 1, r, ind); st[pos] = op(st[pos * 2 + 1], st[pos * 2 + 2]); } void update(int i, int j, int l, int r, S val, int pos) { if (l > r || l > j || r < i) return; if (l == r) { st[pos] = val; return; } int mid = (l + r) / 2; update(i, j, l, mid, val, 2 * pos + 1); update(i, j, mid + 1, r, val, 2 * pos + 2); st[pos] = op(st[pos * 2 + 1], st[pos * 2 + 2]); } void query(int i, int j, int l, int r, int pos, int D, ll &ans) { if (l > r || l > j || r < i) return; if (i <= l && j >= r) { auto &vec = st[pos].arr; ll l1 = lower_bound(vec.begin(), vec.end(), D) - vec.begin(); if ( l1==si(vec) or vec[l1] != D) return; ll r1 = upper_bound(vec.begin(), vec.end(), D) - vec.begin(); r1--; ans += r1 - l1 + 1; return; } int mid = (l + r) / 2; query(i, j, l, mid, pos * 2 + 1, D, ans); query(i, j, mid + 1, r, pos * 2 + 2, D, ans); } /* * bs() will function as follows:- * For a range (l,r) * we will consider following terms: * op(l,l), op(l,l+1), op(l,l+2).... op(l,l+r) * [True,True,False,False...False] * It will then return the index on which first false value occurs */ void bs(int i, int j, int l, int r, int pos, bool(*fun)(S), int &ans) { assert(l >= 0 && l < _n); assert(r >= 0 && r < _n); assert(r >= l); if (l > r || l > j || r < i) return; if (l == r) { if (fun(st[pos]) == false) ans = min(ans, r); return; } if (i <= l && j >= r) { if (fun(st[pos]) == false) { ans = min(ans, r); int mid = (l + r) / 2; if (fun(st[pos * 2 + 1]) == false) bs(i, j, l, mid, 2 * pos + 1, fun, ans); else if (fun(st[pos * 2 + 2]) == false) bs(i, j, mid + 1, r, 2 * pos + 2, fun, ans); } return; } int mid = (l + r) / 2; bs(i, j, l, mid, 2 * pos + 1, fun, ans); bs(i, j, mid + 1, r, 2 * pos + 2, fun, ans); return; } /* * rbs() will function as follows:- * For a range (l,r) * we will consider following terms: * op(l,r), op(l+1,r), op(l+3,r).... op(r,r) * [False,False,True,True,True] * It will then return the index on which last false value occurs */ void rbs(int i, int j, int l, int r, int pos, bool(*fun)(S), int& ans) { assert(l >= 0 && l < _n); assert(r >= 0 && r < _n); assert(r >= l); if (l > r || l > j || r < i) return; if (l == r) { if (fun(st[pos]) == false) ans = max(ans, l); return; } if (i <= l && j >= r) { if (fun(st[pos]) == false) { ans = max(ans, l); int mid = (l + r) / 2; if (fun(st[pos * 2 + 2]) == false) rbs(i, j, l, mid, 2 * pos + 2, fun, ans); else if (fun(st[pos * 2 + 1]) == false) rbs(i, j, mid + 1, r, 2 * pos + 1, fun, ans); } return; } int mid = (l + r) / 2; rbs(i, j, mid + 1, r, 2 * pos + 2, fun, ans); rbs(i, j, l, mid, 2 * pos + 1, fun, ans); return; } public: segtree() :segtree(0) {} segtree(int n) : segtree(vector(n, e())) {} segtree(vector& v) : _n(int(v.size())) { assert(_n > 0); int s = ceil(log2(_n)); s = pow(2, s + 1) - 1; st.clear(); st.resize(s, e()); construct(0, 0, _n - 1, v); } void set(int i, S val) { assert(i >= 0 && i < _n); update(i, i, 0, _n - 1, val, 0); } S query(int i) { assert(i >= 0 && i < _n); return query(i, i, 0, _n - 1, 0); } ll query(int i, int j, int D) { assert(i >= 0 && i < _n); assert(i <= j && j >= 0 && j < _n); ll ans = 0; query(i, j, 0, _n - 1, 0, D, ans); return ans; } templateint bs(int l, int r) { assert(l >= 0 && l < _n); assert(r >= l && r >= 0 && r < _n); assert(fun(e()) == true); int ans = r + 1; bs(l, r, 0, _n - 1, 0, fun, ans); return ans; } templateint rbs(int l, int r) { assert(l >= 0 && l < _n); assert(r >= l && r >= 0 && r < _n); assert(fun(e()) == true); int ans = l - 1; rbs(l, r, 0, _n - 1, 0, fun, ans); return ans; } }; struct S { vector arr; }; S op(S a, S b) { vector temp; auto A = a.arr; auto B = b.arr; int i = 0, j = 0, n = si(A), m = si(B); while (i < n or j < m) { if (i == n) { while (j < m) temp.pb(B[j++]); break; } if (j == m) { while (i < n) temp.pb(A[i++]); break; } if (A[i] < B[j]) temp.pb(A[i++]); else temp.pb(B[j++]); } return S{ temp }; } S e() { return S{ vector{} }; } vector node; vector d; vector it, ot; vector> g; ll t, n; void dfs(ll i) { it[i] = t++; for (auto v : g[i]) { d[v] = d[i] + 1; dfs(v); } ot[i] = t - 1; node[it[i]] = S{ {d[i]} }; } void solve() { cin >> n; g = vector>(n); it = vector(n); t = 0; ot = vector(n); node = vector(n, e()); d = vector(n); for (ll i = 1; i < n ; ++i) { ll x; cin >> x; g[x - 1].pb(i); } dfs(0); segtree seg(node); // cout << d << endl; ll q; cin >> q; while (q--) { ll U, D; cin >> U >> D; U--; if (d[U] >= D) { cout << (d[U]==D) << endl; continue; } ll l = it[U]; ll r = ot[U]; cout << seg.query(l, r, D) << endl; } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif //int t; cin >> t; while (t--) solve(); } 
•  » » » » Thanks!,It indeed is long, I will have to copy it in my editor to study :P
 » i Really dont understand D problem . Can anyone Elaborate more cleaarly . How can we put 'a' in ith place ?
•  » » You may follow this
•  » » » Bruh how toal is C(a+b,a) why not C(a+b,b). Also i didnt understand remaining>=nCr(a+b−1,b−1). How ?
•  » » » » Ncr(a+b,a)== Ncr(a+b,b)
•  » » » » 12 months ago, # ^ | ← Rev. 2 →   Number of remaining positions including the current one is $a+b$, if I put a 'b' in the current position, remaining position becomes $a+b-1$, and we will have to place $a$ number of 'a' and $b-1$ number of 'b' in the next positions. So, that makes it $nCr(a+b-1, b-1)$ If I have more strings than this to leave behind, why not do it by placing an 'a'?
 » Was D harder than usual???
•  » » No. The idea is similar to finding the kth permutation which is quite a standard question.
•  » » » The question is standard.But are the constraints?I don't know.Anyway that was solvable for sure.No doubt about that.
 » 12 months ago, # | ← Rev. 2 →   I was able to solve E, A, B when I started contest 1 hour late that's why I think E should have been placed before C and D for correct order of difficulty.For E I used euler tour then upper_bound-lower_bound in vectors of each depth which contains in_time of those node present at that depth.here's the link for my solution of E
•  » » cap
 » 12 months ago, # | ← Rev. 2 →   Is there any plan for atcoder rounds to be later in the morning (like 7). the usual times (4am, 5am, and at best 6am) are too early for me and presumably other west coasters.
•  » » probably set as per Japanese Standard Time. It's around evening for them.
 » 12 months ago, # | ← Rev. 2 →   Can anyone explain the solution of problem F based on Graham Scan? The editorial Atcoder provided says almost nothing detail about it.
•  » » This is my solution on F, hopefully it will be clear enough :)Sort the points from the top-most one to the bottom-most one (in case of same y, sort from the right-most to the left-most). Afterwards, apply a "custom convex hull" for each prefix of points in the sorted array (the last point in the prefix is the lowest point in the convex hull). Before convex hull, mind Pick’s theorem. This tells us that we are actually interested in the parity of the number of integer points on polygon’s perimeter.Sort the points according to Graham Scan. Afterwards, store dp[i][j][k] — the number of partial polygons starting from the lowest point and ending with the j-i segment, having k = (number of integer coordinates on the perimeter) % 2. In fact, there will be no Graham Scan, but a dp building which can be understood easier if you refer to Graham Scan.For building this dp, we will iterate 0 <= k < j < i < n, and update dp[j][i][nr % 2] += power(2, interior[i][j]) * dp[k][j] and dp[j][i][(1+nr)%2] += power(2, interior[i][j]) * dp[k][j], where nr is the parity of the number of integer coordinates on the j-i segment. Also, interior[i][j] is a coefficient which denotes the number of points which can be taken in the answer set without altering the convex hull containing the i-j segment. This can be precomputed at the beginning of the convex hull. Basically, any k such that i < k < j which is interior to the polygon should be counted.Finally, any dp[k][j] (0 < k < j < n), such that k-j-0 is a valid ending of the Graham Scan, can be considered in the final answer. The final complexity for this solution is O(N^4) with proper precomuputation.
•  » » » Wow, this is great! Thanks a lot bro ^v^~
 » How to solve F？