We will hold Toyota Programming Contest 2023#7（AtCoder Beginner Contest 328）.
- Contest URL: https://atcoder.jp/contests/abc328
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20231111T2100&p1=248
- Duration: 100 minutes
- Writer: leaf1415, MMNMM, evima, m_99
- Tester: kyopro_friends, physics0523
- Rated range: ~ 1999
- The point values: 100-200-300-425-475-525-575
We are looking forward to your participation!
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:
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.
becoz, it asked min modulo of answer, not min answer modulo.
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.
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?
No it will get MLE :(
And the memory limit is intentionally set to $$$512\operatorname{MB}$$$, since you need
long longit 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
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.
Nevermind mine turned out to be O(n * 2^n)...
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.
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?
Constraints were low,so you can also use backtracking. here is the code https://atcoder.jp/contests/abc328/submissions/47496864
-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
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:
D — abc307D Mismatched Parentheses
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.
Can you please explain your dsu approach?
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.
here is an article that explains the code idea , https://medium.com/@alphawizard/augmented-dsu-f2c974926cb2
Why does kruskal not work for problem E ?
Read this.
Good problems.
Problem E can be hardcoded :) submission
Problem F is good, worth solving.
Why in B they didn't take 12 December???
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/47497326
My 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!
HELP, 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.
Thanks. I think weights are stored from leader to node. Leaders will always have weight zero.