TOYOTA MOTOR CORPORATION Programming Contest 2023#2 (ABC302) Announcement

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

• 3 days ago, # ^ | I did it by BFS. Here's my submission- Code

• 2 days ago, # ^ | The idea was very similar to the one mentioned in this problem's editorial

• 2 days ago, # ^ | It's multisource BFS.

• 2 days ago, # ^ | ← Rev. 2 →   +3 you can practice this. it's quite similar.

• 2 days ago, # ^ | Why is it called Ex instead of H ? It isn't extended version of E or something...

  • 2 days ago, # ^ | It stands for "Excellent" as far as I know.

    • 34 hours ago, # ^ | It stands for "Extra" as far as I know.

• 2 days ago, # ^ | ajay_mnc Line 31 should be- string str=v[i].substr(j,5);

  • 2 days ago, # ^ | Thanks for the help

• 2 days ago, # ^ | can you share your approach to it, there's no editorial to refer to

  • 2 days ago, # ^ | 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.

• 2 days ago, # ^ | segtree not needed

  • 2 days ago, # ^ | 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.

    • 2 days ago, # ^ | 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) .

      • 2 days ago, # ^ | ← Rev. 2 →   0 Yup this the optimized thinking, unfortunately I chose a sad way of thinking in the solution and make it so hard.

• 2 days ago, # ^ | What made you think that segtree is involved somewhere in this problem? I think you should read this.

  • 2 days ago, # ^ | My first intuition, thanks for the blog I'll read it.

• 2 days ago, # ^ | Here is one of the example: Spoiler

• 2 days ago, # ^ | ← Rev. 2 →   -7 Modified version can be solved by BFS within the time limit.

  • 2 days ago, # ^ | 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 ?

• 2 days ago, # ^ | ← Rev. 2 →   +1 If we add number 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 to . So, it's NP-hard.

  • 2 days ago, # ^ | 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?

    • 2 days ago, # ^ | ← Rev. 2 →   +3 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 belongs to all sets is equivalent to Minimum Set Cover. Therefore the whole problem is also at least NP-hard.

      • 2 days ago, # ^ | Ah, I see your point now, makes sense. Thank you!

  • 2 days ago, # ^ | Hmm, can't we solve it greedily in a following way? Suppose currently we have set , then take set and merge it with , where: shares at least one element with . The number of elements that adds to is maximized. I think it can be proved in the way Prim's Algorithm is proven.

    • 2 days ago, # ^ | No, it is wrong. Contercase(consider start from ):

      • 2 days ago, # ^ | In the beginning we will start from the set with maximum length.

        • • 2 days ago, # ^ | Isn't answer 2? We start from , add or and then add .

            • 2 days ago, # ^ | 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 ratio where is the -th harmonic number, so maybe this is the reason why it is so hard to find a counter example with small . D:

              • 2 days ago, # ^ | ← Rev. 2 →   0 "and it said it is actually an approximate algorithm with ratio where is the -th harmonic number" Looks like I was preetty close :D Thank you!

              • 39 hours ago, # ^ | If I'm not mistaken the following is a much easier example. If you take and decide to take next, then you have to take all of the sets.

• 2 days ago, # ^ | can you share your approach?

  • 2 days ago, # ^ | 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]).

• 36 hours ago, # ^ | 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 swaps. Then we have to do at least swaps because we already counted all the swaps. And so on. But the lower bound also would work if we did it in any other order of . 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.

• 6 hours ago, # ^ | 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 , the first set is , then there is an arbitrary amount of sets , then there is one set and one .

  • 5 hours ago, # ^ | 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.

    • 5 hours ago, # ^ | Spoiler

  • 87 minutes ago, # ^ | Thank you!