### chokudai's blog

By chokudai, history, 6 days ago,

We will hold HHKB Programming Contest 2022（AtCoder Beginner Contest 235）.

The point values will be 100-200-300-400-500-500-600-600.

We are looking forward to your participation!

• +57

 » 6 days ago, # |   +74 Once again, why is problem H called Ex?
•  » » 6 days ago, # ^ |   -39 Probably means extra, you dumbass.
•  » » » 6 days ago, # ^ | ← Rev. 2 →   +1 What's better? A B C D E F G H A B C D E F G Ex
•  » » 6 days ago, # ^ | ← Rev. 3 →   +15 A friend (jokingly) told me it probably stood for, "Extra Garbage Data Structure"
•  » » » 6 days ago, # ^ |   +6 Problem Ex is not garbage imo, it's usually very educational. I learned a lot from problems Ex.
•  » » » » 6 days ago, # ^ | ← Rev. 2 →   0 That's fair! The problems do seem nice, if a bit beyond my abilities
•  » » 4 days ago, # ^ | ← Rev. 6 →   0 Extra Example Exercise External Extended Excellent Exhausting Extraordinary
 » 6 days ago, # |   0 How to solve E efficiently?
•  » » 6 days ago, # ^ | ← Rev. 2 →   +9 Solve offline. Apply normal MST algo for graph with all m normal edges and q query edges combined. The difference is to not actually add the edge if its a query edge. Solution
•  » » 6 days ago, # ^ |   0 Store the edges given, in set with ind=-1Store the edges of queries, in set with index of query.Now apply Kruskal or Prim's and whenever you encounter a query edge check if this edge would have been added or not and store the answer for that index by using vector of strings.Finally print that vector.Submission
•  » » 6 days ago, # ^ |   0 Think of kruskal algorithm used to compute the MST of a graph:You sort edges by increasing order of weights and you use an edge if and only if it unites two nodes that are not already connected. So you can put all the edges in the same vector, sort them and keep uniting like if you were computing the MST of the graph.At any time when the current edge is a "query edge" you just check if it unites two nodes that are not already connected or not.See my code for more details: https://atcoder.jp/contests/abc235/submissions/28547346
•  » » 6 days ago, # ^ |   +6 My solution:Build the MST of the original graph, then the answer for a query $(u, v, w)$ is Yes if and only if the maximum weight of an edge in the path from $u$ to $v$ on this MST is greater than $w$. So, now our problem has changed to: Given a tree and multiple queries $(u_i, v_i)$, report for each of them the maximum weight of an edge in the path from $u _i$ to $v_i$, which is easily solvable by Binary Lifting.
•  » » » 6 days ago, # ^ |   0 This idea struck me at the very end, but couldn't implement it in time
 » 6 days ago, # |   0 What's the solution to problem F? I've come up with some sort of dp, and I guess it should work, but could someone point out the mistake?The idea I used is that we can calculate the count of number such that first $i$ digits match and $(i+1)_{th}$ one is lower than the one in $N$. So I've precomputed the number of sequences of length $K$ for each set of digits using bitmask DP, as well as their sums and later use them in calculations. Here's the code and it's obviously got one issue which is discarding the elements with leading zeros. E. g. 01 is not a valid number for set of digits {0,1}. Can anyone help? Code#include using namespace std; const int MOD=998244353; int a[10]; int seen[10]; int pw[(int)1e4+5]; int dp[(int)1e4+5][(1<<10)+5]; int cnt[(int)1e4+5][(1<<10)+5]; int mul(int a,int b){ int ret=(1LL*a*b)%MOD; if(ret<0)ret+=MOD; return ret; } int add(int a,int b){ int ret=(a+b)%MOD; if(ret<0)ret+=MOD; return ret; } signed main(){ ios_base::sync_with_stdio(0);cin.tie(0); string s;cin>>s; int n;cin>>n; int mask=0; for(int i=0;i>a[i],seen[a[i]]=1,mask|=(1<=0;i--)pw[i]=mul(pw[i+1],10); for(int i=0;i<(int)s.length();i++){ for(int j=0;j
•  » » 6 days ago, # ^ |   0 I did some pretty similar DP.The states are: number of the digit, bitmask (to know which of the required digits have already been used) and a bool to know if my number if currently less or equal than n.Don't allow any leading zeroes (so in your base case don't use digit 0) and at any digit just add a new transition which is "creating" a newer digit already smaller than n:See my code for more details: https://atcoder.jp/contests/abc235/submissions/28560145Don't mind to tell me if anything is unclear :p
•  » » 6 days ago, # ^ |   0 My solution (although I couldn't submit it due to some bugs in my code) is the following:Let's say $sum(A)$ is the sum of all the elements in the set $A$. Let's also define $S_d$ as the set of numbers that don't have the digit $d$ on their decimal representation. Then, we're asked for $sum\left([1, n]- \displaystyle\bigcup_d{S_d}\right) = \frac{n(n+1)}{2} - sum\left(\displaystyle\bigcup_d{S_d}\right)$. The sum of that $union$ can be computed by inclusion-exclusion principle: We iterate through all the non-empty subsets of the given digits and for each of them, we can use digit-dp for computing the required sum.
 » 6 days ago, # |   0 Can D be solved with DP? If yes, can anyone share their code?
•  » » 6 days ago, # ^ |   0 +1
•  » » 6 days ago, # ^ | ← Rev. 2 →   0 D can be solved with something not that far from DP. Imagine a graph where each node is a number and you add an edge X->Y if you can reach number Y from number X. You start from number 1 and want the shortest path to get to node N. You have O(n) nodes and O(n) edges.Let me know if anything is not clear :)Here is my code: https://atcoder.jp/contests/abc235/submissions/28543245
•  » » 6 days ago, # ^ | ← Rev. 2 →   0 Yes, my very messy solution just uses recursive DP. With a little tweak to avoid infinite circular rotation (if we reach the same state, then bail out and return "infinity"): https://atcoder.jp/contests/abc235/submissions/28563863I initially tried to do rotations via integer arithmetic operations, but wasted a lot of time debugging it. Only at the last moment replaced this stuff with string manipulations and got an AC verdict. Premature optimization is the root of all evil...Edit: Now hacked by the "99_after_contest_00.txt" testcase :-)
 » 6 days ago, # |   0 Editorial of G:"(plant 1 or more seedlings to the 1-st garden) and (plant 1 or more seedlings to the 1-st garden) and (plant 1 or more seedlings to the 1-st garden) …"It this a typo, or what is the meaning of it?
 » 6 days ago, # |   0 Can someone help me with my code for E? It passes sample cases but gives WA verdict. I constructed the mst of the graph and for queries I did the following: if u is ancestor of v, compare w with parent edge of v and the child edge of u that contains v. if v is ancestor of u, same as above compare w with parent edges of u and v. Code#include using namespace std; struct Graph { typedef pair item; vector> adj; vector> mst; vector par; vector tin, tout; int V, E, timer; Graph(int v, int e) : V(v), E(e) { adj.resize(v); mst.resize(v); par.resize(v); tin.resize(v); tout.resize(v); for(int i = 0; i < e; i++) { int u, v, w; cin >> u >> v >> w; u--, v--; adj[u].emplace_back(w, v); adj[v].emplace_back(w, u); } } void euler_tour(int u) { tin[u] = ++timer; for(auto [c, w]: mst[u]) euler_tour(c); tout[u] = ++timer; } void solve() { priority_queue> pq; vector taken(V); taken[0] = 1; for(auto [w, v]: adj[0]) { pq.push({-w, v, 0}); } int cnt = 1; while(cnt < V) { auto [w, v, u] = pq.top(); pq.pop(); if(taken[v]) continue; taken[v] = 1; cnt++; mst[u].emplace_back(v, -w); par[v] = {u, -w}; for(auto [w1, v1]: adj[v]) if(!taken[v1]) pq.push({-w1, v1, v}); } timer = 0; euler_tour(0); } bool ancestor(int a, int u) { return tin[a] <= tin[u] and tout[a] >= tout[u]; } bool query(int u, int v, int w) { if(u == v) return false; if(ancestor(u, v)) swap(u, v); if(ancestor(v, u)) { if(w < par[u].second) return true; int beg = 0, end = (int) mst[v].size() - 1; while(beg <= end) { int mid = (beg + end) / 2; auto [c, wc] = mst[v][mid]; if(ancestor(c, u)) return w < wc; if(tout[c] < tin[u]) beg = mid + 1; else end = mid - 1; } } return w < par[u].second or w < par[v].second; } }; int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, m, q; cin >> n >> m >> q; Graph g(n, m); g.solve(); while(q--) { int u, v, w; cin >> u >> v >> w; u--, v--; g.query(u, v, w) ? cout << "Yes\n" : cout << "No\n"; } } 
•  » » 6 days ago, # ^ |   +1 We could implement logic like "find max weight edge on path from u to v", and if that weight is bigger current query edge weight, then the query edge weight would have been used.But to find max weight edge on path from u to v in the MST, we need more that only compare the weight to the parent edge. It can be done in example with binary lifting.
•  » » » 6 days ago, # ^ |   0 right. thanks.
•  » » » 6 days ago, # ^ |   +1 yeah I implemented it and honestly it was not fun to do.. In my defense it was my first time implementing LCA with binary lifting and I wrote one line incorrectly.
 » 6 days ago, # | ← Rev. 4 →   0 Please help me in finding the mistake in E..Is my approach wrong? https://atcoder.jp/contests/abc235/submissions/28561004
 » 6 days ago, # |   0 Can someone please tell me why I am getting a runtime error on this solution for problem E? I made 6 tries during the contest but wasn't able to find my mistake.https://atcoder.jp/contests/abc235/submissions/28555671
•  » » 6 days ago, # ^ |   0 Maybe it is actually a memory error, caused by using several gig for all the dsu.
•  » » » 6 days ago, # ^ |   0 Yes, I also think so. MLE would be a better verdict though.Thank you!
 » 6 days ago, # |   +8 Problem E and F are all classic.Also E and Link (in chinese) are the same.Sorry to my poor English.
•  » » 6 days ago, # ^ |   0 ABC is educational it is normal to have classic problems.
 » 5 days ago, # | ← Rev. 2 →   0 In Question D, I used recursion and it seemed to pass ALL test cases except one. Can anybody guess which test case it would be. Here is my code. Thanks for the help in advance.Also, There is no TLE or MLE in that test case.
•  » » 5 days ago, # ^ |   0 3 621 Your solution gives 9. My solution gives 6.
•  » » » 5 days ago, # ^ |   0 Thanks a lot!! There was a problem with putting unordered_set in the wrong line which prevented updation of final answer. I corrected it and its working correctly.Here is the code for reference : CODE
 » 5 days ago, # |   +12 My solution for problem E:Build an MST of the original graph.Remove all other edges.Use LCA with doubling technique.Record the maximum weight of edges on paths of length 1,2,4,8,.....Process each query independently.Test if the path on the tree from u to v contains an edge longer than w.If so answer Yes.Otherwise,answer No.Code
 » 5 days ago, # |   +5 https://atcoder.jp/contests/abc235/submissions/28584413Can anybody please help me in finding the mistake in my DP solution of problem D .It passed all the test cases except 99_after_contest_00.txt .Even if anyone is able to find that probable case please help me out.
•  » » 5 days ago, # ^ |   +1 Looks like our solutions were hacked after the contest and mine fails it too (are problem setters reading comments here?). Now it would be indeed interesting to have a look at this 99_after_contest_00.txt testcase. I tried stress testing, but haven't found anything yet.
•  » » 4 days ago, # ^ |   +1 Now I have some testcases: "2 11327" (expected 40, but got 41) and "2 62153" (expected 17, but got 18).The bug is that the solution is effectively doing DFS to find a path from N to 1. But it isn't always the shortest path, so BFS is really needed instead. The original tests used during the contest were weak and didn't detect it. I wonder how many incorrect solutions got accepted?And even now, having just a single testcase (testcase 99_after_contest_00.txt) in the set makes it possible for some heuristically tuned or even randomized DFS to be incorrectly accepted.
•  » » » 4 days ago, # ^ |   +5 Nice,thanks
 » 4 days ago, # |   0 can someone provide testcases of problem e..i am getting runtime error on 2 testcases. i am trying to build a tree by first using the m edges(using dsu and then dfs) given and then for every query i find the max value on that path b/w those two nodes . if value of query is greater than max then i print no else yes..
 » 3 days ago, # | ← Rev. 2 →   0 In problem D it is simpler, and it runs faster, if we do BFS backwards — from $N$ to $1$. We just check that for the first operation $a$ divides $N$, and for the second operation $N$ has at least two digits, and the second digit is not 0.https://atcoder.jp/contests/abc235/submissions/28604711