Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### atcoder_official's blog

By atcoder_official, history, 3 weeks ago,

We will hold Toyota Programming Contest 2023#7（AtCoder Beginner Contest 328）.

We are looking forward to your participation!

• +49

 » 3 weeks ago, # |   +6 Hello!
•  » » 3 weeks ago, # ^ |   +3 Hello!
•  » » 3 weeks ago, # ^ |   +13 ?
 » 3 weeks ago, # |   +11 Hello everyone! Is everyone ready to contest? I wish luck to everyone! :)
 » 3 weeks ago, # |   +11 I wish everyone luck in the game
 » 3 weeks ago, # |   +5 Wish everyone luck!
 » 3 weeks ago, # |   +5 Hello!
 » 3 weeks ago, # |   +5 Good Luck everyone
 » 3 weeks ago, # |   +5 Good Luck！
 » 3 weeks ago, # |   +5 Good luck!
 » 3 weeks ago, # |   +5 Good luck!
 » 3 weeks ago, # |   -6 Is AtCoder down again? Why is it always failing during contests?
•  » » 3 weeks ago, # ^ |   +1 working fine for me
 » 3 weeks ago, # |   +5 Good luck!
 » 3 weeks ago, # |   -40 Problem F:
 » 3 weeks ago, # | ← Rev. 2 →   0 for problem E i did the black box strategy since i don't know the algorithm, I copied and pasted solution from GFG with some modification of course why does it give a wrong answer for testCase 3?
•  » » 3 weeks ago, # ^ |   +15 Kruskal's Algorithm wont return minimum cost spanning tree in this case. As its modulo sum.
•  » » 3 weeks ago, # ^ |   +15 becoz, it asked min modulo of answer, not min answer modulo.
•  » » 3 weeks ago, # ^ |   0 You can actually try out all possible parent arrays (these arrays will correspond to single predecessor graphs) with vertex 1 as your root. We will have atmost 7 ^ 8 = 6 * 10 ^ 6 such arrays of which some won't correspond to trees. We can eliminate those by a simple dfs. My solution : link
•  » » » 3 weeks ago, # ^ |   0 what does the function test stand for ?
•  » » » » 3 weeks ago, # ^ |   0 It is where you check whether all vertices are reachable in a single dfs run from vertex 1.
•  » » » » » 3 weeks ago, # ^ |   0 Got it , thanks man
 » 3 weeks ago, # |   +6 Nice problems, I liked solving D, E and F today.
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Was too close in F. missed by 4 mins.
 » 3 weeks ago, # |   +39 In problem G, were $O(2^n \cdot n^2)$ solutions intended to pass if optimized well?
•  » » 3 weeks ago, # ^ | ← Rev. 4 →   0 No it will get MLE :(And the memory limit is intentionally set to $512\operatorname{MB}$, since you need long long it will cost $22\times2^{22}\times8\operatorname{B}=704\operatorname{MB}$.UPD: Ohhhhhhhhhhhh I optimized the space (halved it) and got AC
•  » » » 3 weeks ago, # ^ |   +34 You can reduce space complexity to O(2^n) by solving the dp in increasing order of popcount and only allocating space for current and next popcount.
•  » » » » 3 weeks ago, # ^ |   0 Alternatively, just maintain $dp_{mask}$ = min cost to take these elements from A and map them to a prefix of B. Then just take a consecutive subarray of elements without a split $[i, j]$ in one shot using an $O(n ^ 2)$ loop.
•  » » » 3 weeks ago, # ^ |   +13 That's because you're using $O(2^n \cdot n)$ memory. On the largest input this will use around 700 MB, but the memory limit is only 512 MB.But you can notice that some of the $2^n \cdot n$ states aren't valid, and the number of valid states is just small enough ($46137344$ on max test) to fit in the memory limit. In my code I only allocate memory for valid states and it gets AC. Submission
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   0 I don't think so.My $O(2^n \cdot n)$ soln took 0.9/2.8s time.$O(2^n \cdot n^2)$ should get TLE.
•  » » » 3 weeks ago, # ^ | ← Rev. 4 →   +12 Nevermind mine turned out to be O(n * 2^n)...
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   -8 My $O(2^n \cdot n^2)$ soln passed in 0.4s. The key part being that it only actually uses ~$8 \cdot 10^7$ ops in practice due to not all possible values of $1 \leq i \leq j \leq n$ being used in a mask.
•  » » » » 3 weeks ago, # ^ | ← Rev. 2 →   +60 The key part of your solution is that it's actually $O(2^n \cdot n)$, not $O(2^n \cdot n^2)$.For each of the $2^n$ bitmasks and for each subarray $[i, j]$, your solution does calculations for this subarray if all of the corresponding bits of this subarray are $0$.For a subarray of length $k$, there are $2^{n-k}$ bitmasks where all bits of this subarray are $0$. There are also $(n + 1 - k)$ subarrays of length $k$.This means that the number of operations your code does is on the order of $\displaystyle\sum_{k=1}^n 2^{n-k}(n+1-k)$$=\displaystyle\sum_{k=1}^n 2^{k-1}\cdot k$$\le \displaystyle\sum_{k=1}^n 2^{k-1}\cdot n$$= n\displaystyle\sum_{k=1}^n 2^{k-1}$$= n\displaystyle\sum_{k=0}^{n-1} 2^k$$= n(2^n-1)$$\subseteq O(2^n \cdot n)$
 » 3 weeks ago, # |   0 For problem E, I tried using a Dijkstra to find the MST. To my concern, the implementation is well written. Why didn't it work?
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Constraints were low,so you can also use backtracking. here is the code https://atcoder.jp/contests/abc328/submissions/47496864
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 -this comment does not exist, I made a mistake xdd-
•  » » » 3 weeks ago, # ^ |   +18 Well, I think you're in the right blog. But, classical MST algorithm will not work here since you have to print minimum "cost modulo k", and not "minimum cost" modulo k.
•  » » » » 3 weeks ago, # ^ |   0 Now I get it. Thanks mate!
 » 3 weeks ago, # |   0 Please can anyone explain how to solve G? my n*2^n method got WA, thanks a lot.
•  » » 3 weeks ago, # ^ |   0 from where can we learn such DSU tricks like problem f?
•  » » » 3 weeks ago, # ^ |   0 CP Algorithms website is particularly useful. This page contains all the ideas needed for F — link
 » 3 weeks ago, # |   0 E — Modulo MST and i choose kruskal to solve it. why it failed on case 3? please help me Your code here... #include #define cout3(a,b,c) cout<> n >> m >> k; for(int i=1;i <= n;i++) f[i]=i; for(int i=0;i < m;i++) cin >> e[i].u >> e[i].v >> e[i].w,e[i].w%=k; sort(e,e + m,cmp); for(int i=0;i < m;i++){ int fv=find(e[i].v),fu=find(e[i].u); if(fv == fu) continue; f[fv]=fu; // cout3(e[i].u,e[i].v,e[i].w); ans+=e[i].w; ans%=k; } cout << ans % k; return 0; } 
•  » » 3 weeks ago, # ^ |   0 oh no,i understand the reason,i misunderstood "the cost of T is defined as the sum, modulo K, of the weights of the edges in T.".And now,the problem has been solved.
 » 3 weeks ago, # |   +1 In editorial of E, how is he enumerating the spanning trees?
•  » » 3 weeks ago, # ^ |   +13 from what I understand, it sets last $n-1$ bits of $m$ bits and use next_permutation to enumerate
 » 3 weeks ago, # |   0 So, origin problems:Because of some problems, it isn't completed.May update.Very special things:In sometimes in the contest, I'd ever solved problem E and don't solve problem D!
 » 3 weeks ago, # |   0 Porblem F is very great, and I have seldom solved a problem which uses weighted dsu (this may be the second time). I learned a lot from this problem, thank you, atcoder team.
•  » » 3 weeks ago, # ^ |   0 Can you please explain your dsu approach?
•  » » » 3 weeks ago, # ^ |   0 In fact, I didn't solve it during the contest, and I also learned this from the editorial. My dsu approach is just the same as the one mentioned in the editorial. Different from the simple dsu, which only records whether two nodes are "connected", this weighted dsu would maintain another variable which stores the "relation" from each node to its ancestor node. I think you can search this topic on the Internet, or, blogs at codeforces. I think there have been several blogs talking about this at codeforces.
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 here is an article that explains the code idea , https://medium.com/@alphawizard/augmented-dsu-f2c974926cb2
 » 3 weeks ago, # | ← Rev. 2 →   0 Why does kruskal not work for problem E ?
•  » » 3 weeks ago, # ^ |   0
 » 3 weeks ago, # | ← Rev. 2 →   -18 Good problems.
 » 3 weeks ago, # |   0 Problem E can be hardcoded :) submission
 » 3 weeks ago, # |   +5 Problem F is good, worth solving.
 » 3 weeks ago, # |   -8 Why in B they didn't take 12 December???
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   +18 Day j of month i is said to have a repdigit date if and only if one can represent both i and j using just one kind of digit in decimal notation. For example, December 12th is not a repdigit date, as i = 12 and j = 12, requiring two kinds of digit (1 and 2) to represent them.
 » 3 weeks ago, # |   0 Is there a solution for problem D without the use of stack?
•  » » 3 weeks ago, # ^ |   0 no because worst case will be $O(n^2)$ without it
•  » » 3 weeks ago, # ^ |   0 Mine didn't use a stack or recursion: https://atcoder.jp/contests/abc328/submissions/47493974 Just had the step back iterating over A indices after every reduction.
•  » » » 3 weeks ago, # ^ |   0 Hehe. Just read the editorial. Essentially I did the same, but in an overcomplicated convoluted way.
•  » » 3 weeks ago, # ^ |   0 I solved it without using a stack or something similar. https://atcoder.jp/contests/abc328/submissions/47497326My approach was to find each "ABC" and expand it to the left and right trying to find more prefixes and suffixes like "AB" with "C" and "A" with "BC". Then I remove the matched sub string [l, r] from S and continue the process from l.
•  » » » 3 weeks ago, # ^ |   0 The approach is nice, thanks!
 » 3 weeks ago, # |   -8 E = Brute Force. Do you see the $2<=n<=8$?
•  » » 3 weeks ago, # ^ |   -8 Yes.
 » 2 weeks ago, # |   0 Can someone tell me the data of the F HACK or modify my code? Thanks! #include using namespace std; inline int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*f; } inline void write(int x){ if(x<0){ putchar('-'); x=-x; } if(x>9)write(x/10); putchar(x%10+'0'); } int n,q; int fa[200001],g[200001]; inline int find(int x){ if(fa[x]==x)return x; int f=find(fa[x]); g[x]+=g[fa[x]]; return fa[x]=f; } inline bool merge(int x,int y,int c){ int fx=find(x),fy=find(y); if(fx==fy)return g[y]-g[x]==c; fa[fx]=fy; g[fx]=g[y]-g[x]-c; return true; } signed main(){ n=read();q=read(); for(int i=1;i<=n;i++)fa[i]=i; for(int i=1;i<=q;i++){ int a=read(),b=read(),c=read(); if(merge(a,b,c)){ write(i); putchar(' '); } } return 0; } 
 » 10 days ago, # |   0 Can anyone explain the F solution? Actually, What are we storing in the weight array?
•  » » 10 days ago, # ^ |   +3 It is the weight of the path from the node to the leader of that component.
•  » » » 10 days ago, # ^ | ← Rev. 2 →   0 Thanks. I think weights are stored from leader to node. Leaders will always have weight zero. Img