We will hold TOYOTA MOTOR CORPORATION Programming Contest 2023#2 (AtCoder Beginner Contest 302).
- Contest URL: https://atcoder.jp/contests/abc302
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20230520T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: [user:math957963], PCTprobability, Nyaan, YoshikaMiyafuji
- Tester: MMNMM, Nyaan
- Rated range: ~ 1999 The point values will be 100-250-250-400-425-500-625-625.
We are looking forward to your participation!
If you have difficulty accessing the contest, please refer to the problem statement distributed here. https://img.atcoder.jp/abc302/tasks.pdf
For measures to deal with difficult access situations, please click here. https://atcoder.jp/posts/1028
https://atcoder.jp/posts/1028 leads to 404 Page Not Found
how to do merge set? is it a graph question ?
I did it by BFS. Here's my submission- Code
The idea was very similar to the one mentioned in this problem's editorial
It's multisource BFS.
you can practice this. it's quite similar.
problem Ex is a difficult version of this problem using rollback dsu
Why is it called Ex instead of H ? It isn't extended version of E or something...
It stands for "Excellent" as far as I know.
It stands for "Extra" as far as I know.
why this submission for G is giving WA
https://ideone.com/SjMvtC
Is there is any corner case left for my submission for problem B submission
dheetCoder Line 31 should be- string str=v[i].substr(j,5);
Why the editorial is only in japanese , please provide english editorial as well
Damn, I managed to misread E and thought we needed to output the number of connected components. Spent 30 minutes trying to understand why removing all edges adjacent to some vertex makes Fully Dynamic Connectivity easier (I think it doesn't btw)...
Nice contest though, quite balanced!
This contest was really good,i think G is much easier than previous contests.
can you share your approach to it, there's no editorial to refer to
I used a greedy approach where i first swap any two values which are in each other's position, then take three as a group and finally four as a group. Here's my submission — Code. Go through the code and ask if there's any doubt.
very well done!
Can E be solved using segment tree? I've tried to solve it using seg tree, but it gave me TLE.
segtree not needed
I assumed that I could update each vertex by its number of Neighbours if op is 1, if op is 2 then I made a removal function to erase it from each Neighbour then erase all of its Neighbours.
You could store neighbour for each vertex in aa set and do the operations as you mentioned, since we are only removing the edges we add and they're limited(<1e5) .
What made you think that segtree is involved somewhere in this problem? I think you should read this.
In problem F can answer be greater than 3?
Yes.
YES
Here is one of the example:
input:
expected output:5
I misread problem F to be: find the minimum number of merge operations to get a union set that it contains all numbers from 1 to M :(.
I am curious if this modified version can be solved within the time limit. Does anybody know how to solve this version?
This version has become very close to the Minimum Set Cover problem, which is NP-hard. The only difference is that we can only merge two sets if they intersect. I feel like with this constraint, the problem is even harder to solve, so it should still be NP-hard?
Modified version can be solved by BFS within the time limit.
Can you provide some insight on how to solve the modified version? Like if we do BFS, which vertex should we pick as the starting vertex ?
If we add number $$$M$$$ in all sets, then constraint "we can only merge two sets if they intersect" is gone, and we are solving Minimum Set Cover on numbers from $$$1$$$ to $$$M - 1$$$. So, it's NP-hard.
If the goal is to use the minimum number of merge operations to get all numbers in [1, M], why can we add M to all sets? Doesn't this change what we want to achieve?
I mean, I described how to build an input for yours problem that makes it equivalent to Minimum Set Cover problem. So, the special case of your problem where $$$M$$$ belongs to all sets is equivalent to Minimum Set Cover. Therefore the whole problem is also at least NP-hard.
Ah, I see your point now, makes sense. Thank you!
Hmm, can't we solve it greedily in a following way?
Suppose currently we have set $$$S$$$, then take set $$$X$$$ and merge it with $$$S$$$, where:
I think it can be proved in the way Prim's Algorithm is proven.
No, it is wrong.
Contercase(consider start from $$$S_2$$$):
In the beginning we will start from the set with maximum length.
Isn't answer 2?
We start from $$$S_2$$$, add $$$S_3$$$ or $$$S_4$$$ and then add $$$S_5$$$.
My bad, let me try again
and I found out actually this algorithm is writen in the wiki of set cover problem, and it said it is actually an approximate algorithm with $$$H(n)$$$ ratio where $$$H(n)$$$ is the $$$n$$$-th harmonic number, so maybe this is the reason why it is so hard to find a counter example with small $$$n$$$. D:
"and it said it is actually an approximate algorithm with $$$H(n)$$$ ratio where $$$H(n)$$$ is the $$$n$$$-th harmonic number"
Looks like I was preetty close :D
Thank you!
If I'm not mistaken the following is a much easier example. If you take $$$S_1$$$ and decide to take $$$S_4$$$ next, then you have to take all of the sets. $$$S_1 = \{1, 2, 3, 4\}\newline S_2 = \{1, 5, 6\}\newline S_3 = \{1, 7, 8\}\newline S_4 = \{1, 5, 7\}$$$
Can someone tell me if this solution is actually correct for EX or not?
https://atcoder.jp/contests/abc302/submissions/41570525
I didn't proof the complexity but I thought that in a random alignment, the complexity should go to the average case instead of the worst case so it might pass.
Can anyone come up with a proof countercase?
can you share your approach?
I just use Khun in an iterative way and roll back the changes on my way out of the node.
If you think about it you can the problem is just max matching by adding edges (node, a[node]) and (node, b[node]).
Regarding the Japanese editorial of problem $$$G$$$, can someone explain why $$$Max_{p}(\sum_{i=1}^{i=3}\sum_{j=i+1}^{j=4}{C_{p_{i},p_{j}}})$$$* works?
*$$$C_{{i},{j}}$$$ is the number of occurrences of $$$j$$$ which are in a location where $$$i$$$ should be, and $$$Max_{p}$$$ is the maximum value through all permutations of $$$\{1,2,3,4\}$$$.
Is is a lower bound on the answer. First, let's try to do some simpler lower bound. We obviously have to do at least $$$C_{1, 2} + C_{1, 3} + C_{1, 4}$$$ swaps. Then we have to do at least $$$C_{2, 3} + C_{2, 4}$$$ swaps because we already counted all the $$$1 - 2$$$ swaps. And so on. But the lower bound also would work if we did it in any other order of $$${ 1, 2, 3, 4 } $$$. So this is a lower bound. But I don't really know how to prove it that we can always do it in this number of swaps.
Why did I TLE on the after-contest testcase for F? I did multi-source BFS starting from sets containing the elments 1, and then I keep going to the other sets to try to reach m. Is it constant factor?
Here is my submission: https://atcoder.jp/contests/abc302/submissions/41632920
Your bfs is quadratic in time, because on each iteration you take each set in the queue, and for each of its elements you put every set that has that element back in the queue. This amount of queue additions can be quadratic, since you can have a lot of sets with the same distance that share an element.
Take a case where $$$m = 4$$$, the first set is $$$\{1, 2\}$$$, then there is an arbitrary amount of sets $$$\{2\}$$$, then there is one set $$$\{2, 3\}$$$ and one $$$\{3, 4\}$$$.
Hi can you share the intended approach for this problem(problem F).I saw in japanese editorial like some super vertex kind of stuff but it's hard to properly understand from it even with google translate.
Notice that in the optimal answer you will always start with some set, and then merge it with some amount of others until you get both $$$1$$$ and $$$m$$$. You can treat it as if you want to start with a set that has $$$1$$$ and merge as little sets as possible with it until you get $$$m$$$ in the set.
Let's calculate $$$d_x$$$ — the minimum amount of operations to add $$$x$$$ to the set for each $$$x$$$. At first $$$d_x = 0$$$ for each $$$x$$$ such that there is a set containing both $$$1$$$ and $$$x$$$ (for $$$x = 1$$$ too). Then, $$$d_y = \min d_x + 1$$$ among $$$x$$$ such that there is a set with both $$$x$$$ and $$$y$$$. You can build that graph and run bfs on it, it will give the correct answer but it is quadratic in time because of the amount of edges (my previous comment is exactly about that).
To deal with that there is a trick: build a bipartite graph, where on the left you have vertices that stand for sets, and on the right you have vertices that stand for individual elements, and there should be an edge between $$$l_i$$$ and $$$r_j$$$ if set $$$i$$$ has element $$$j$$$. The shortest path now is twice as long, but the amount of edges is linear, so you can run bfs on this graph.
Thanks mate.
Thank you!