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!  Comments (69)
 » Hello!
•  » » Hello!
•  » » ?
 » Hello everyone! Is everyone ready to contest? I wish luck to everyone! :)
 » I wish everyone luck in the game
 » Wish everyone luck!
 » Hello!
 » Good Luck everyone
 » Good Luck！
 » Good luck!
 » Good luck!
 » Is AtCoder down again? Why is it always failing during contests?
•  » » working fine for me
 » Good luck!
 » Problem F: » 3 weeks ago, # | ← Rev. 2 →   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?
•  » » Kruskal's Algorithm wont return minimum cost spanning tree in this case. As its modulo sum.
•  » » 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
•  » » » what does the function test stand for ?
•  » » » » It is where you check whether all vertices are reachable in a single dfs run from vertex 1.
•  » » » » » Got it , thanks man
 » Nice problems, I liked solving D, E and F today.
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   Was too close in F. missed by 4 mins.
 » In problem G, were $O(2^n \cdot n^2)$ solutions intended to pass if optimized well?
•  » » 3 weeks ago, # ^ | ← Rev. 4 →   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
•  » » » 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.
•  » » » » 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.
•  » » » 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 →   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 →   Nevermind mine turned out to be O(n * 2^n)...
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   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 →   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)$
 » 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 →   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 →   -this comment does not exist, I made a mistake xdd-
•  » » » 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.
•  » » » » Now I get it. Thanks mate!
 » Please can anyone explain how to solve G? my n*2^n method got WA, thanks a lot.
•  » » from where can we learn such DSU tricks like problem f?
•  » » » CP Algorithms website is particularly useful. This page contains all the ideas needed for F — link
 » 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; } 
•  » » 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.
 » In editorial of E, how is he enumerating the spanning trees?
•  » » from what I understand, it sets last $n-1$ bits of $m$ bits and use next_permutation to enumerate
 » 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!
 » 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.
•  » » » 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 →   here is an article that explains the code idea , https://medium.com/@alphawizard/augmented-dsu-f2c974926cb2
 » 3 weeks ago, # | ← Rev. 2 →   Why does kruskal not work for problem E ?
•  » »
 » 3 weeks ago, # | ← Rev. 2 →   Good problems.
 » Problem E can be hardcoded :) submission
 » Problem F is good, worth solving.
 » Why in B they didn't take 12 December???
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   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.
 » Is there a solution for problem D without the use of stack?
•  » » no because worst case will be $O(n^2)$ without it
•  » » 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.
•  » » » Hehe. Just read the editorial. Essentially I did the same, but in an overcomplicated convoluted way.
•  » » 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.
•  » » » The approach is nice, thanks!
 » E = Brute Force. Do you see the $2<=n<=8$?
•  » » Yes.
 » 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,g; 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; } 
 » Can anyone explain the F solution? Actually, What are we storing in the weight array?
•  » » It is the weight of the path from the node to the leader of that component.
•  » » » 10 days ago, # ^ | ← Rev. 2 →   Thanks. I think weights are stored from leader to node. Leaders will always have weight zero. Img 