chokudai's blog

TOYOTA MOTOR CORPORATION Programming Contest 2023#2 (ABC302) Announcement
By chokudai, history, 12 months ago, In English

We will hold TOYOTA MOTOR CORPORATION Programming Contest 2023#2 (AtCoder Beginner Contest 302).

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

  • Vote: I like it
  • +55
  • Vote: I do not like it

»
12 months ago, # |
  Vote: I like it +21 Vote: I do not like it

https://atcoder.jp/posts/1028 leads to 404 Page Not Found

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Yet another contest with adjusted difficulty:P

→ Reply
»
12 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

how to do merge set? is it a graph question ?

→ Reply
»
12 months ago, # |
← Rev. 2   Vote: I like it +22 Vote: I do not like it

problem Ex is a difficult version of this problem using rollback dsu

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why this submission for G is giving WA

https://ideone.com/SjMvtC

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there is any corner case left for my submission for problem B submission

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why the editorial is only in japanese , please provide english editorial as well

→ Reply
»
12 months ago, # |
  Vote: I like it +16 Vote: I do not like it

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!

→ Reply
»
12 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

UPD : solved

→ Reply
»
12 months ago, # |
  Vote: I like it +13 Vote: I do not like it

This contest was really good,i think G is much easier than previous contests.

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you share your approach to it, there's no editorial to refer to

    → Reply
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

      → Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can E be solved using segment tree? I've tried to solve it using seg tree, but it gave me TLE.

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    segtree not needed

    → Reply
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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) .

        → Reply
        • »
          »
          »
          »
          »
          12 months ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          Yup this the optimized thinking, unfortunately I chose a sad way of thinking in the solution and make it so hard.

          → Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What made you think that segtree is involved somewhere in this problem? I think you should read this.

    → Reply
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My first intuition, thanks for the blog I'll read it.

      → Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem F can answer be greater than 3?

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Yes.

    → Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    YES

    Here is one of the example:

    Spoiler
    → Reply
»
12 months ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

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?

→ Reply
  • »
    »
    12 months ago, # ^ |
    ← Rev. 2   Vote: I like it -7 Vote: I do not like it

    Modified version can be solved by BFS within the time limit.

    → Reply
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 ?

      → Reply
  • »
    »
    12 months ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        12 months ago, # ^ |
        ← Rev. 2   Vote: I like it +3 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          12 months ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          Ah, I see your point now, makes sense. Thank you!

          → Reply
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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:

      • $$$X$$$ shares at least one element with $$$S$$$.
      • The number of elements that $$$X$$$ adds to $$$S$$$ is maximized.

      I think it can be proved in the way Prim's Algorithm is proven.

      → Reply
      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        No, it is wrong.

        Contercase(consider start from $$$S_2$$$):

        $$$ n = 5, m = 7\\ S_1 = \{1, 6\}\\ S_2 = \{1\}\\ S_3 = \{1, 2, 3\}\\ S_4 = \{1, 4, 5\}\\ S_5 = \{2, 3, 4, 5, 6, 7\} $$$
        → Reply
        • »
          »
          »
          »
          »
          12 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          In the beginning we will start from the set with maximum length.

          → Reply
          • »
            »
            »
            »
            »
            »
            12 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            $$$ n = 5, m = 13\\ S_1 = \{1, 6\}\\ S_2 = \{1, 8, 9, 10, 11, 12, 13\}\\ S_3 = \{1, 2, 3\}\\ S_4 = \{1, 4, 5\}\\ S_5 = \{2, 3, 4, 5, 6, 7\} $$$
            → Reply
            • »
              »
              »
              »
              »
              »
              »
              12 months ago, # ^ |
                Vote: I like it +1 Vote: I do not like it

              Isn't answer 2?

              We start from $$$S_2$$$, add $$$S_3$$$ or $$$S_4$$$ and then add $$$S_5$$$.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                12 months ago, # ^ |
                  Vote: I like it +12 Vote: I do not like it

                My bad, let me try again

                $$$ n = 5, m = 15\\ S_1 = \{1, 2, 15\}\\ S_2 = \{3, 4, 5, 6, 15\}\\ S_3 = \{7, 8, 9, 10, 11, 12, 13, 14, 15\}\\ S_4 = \{1, 3, 4, 7, 8, 9, 10, 15\}\\ S_5 = \{2, 5, 6, 11, 12, 13, 14, 15\} $$$

                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:

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 months ago, # ^ |
                  ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                  "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!

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  11 months ago, # ^ |
                    Vote: I like it +16 Vote: I do not like it

                  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\}$$$

                  → Reply
»
12 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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?

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you share your approach?

    → Reply
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      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]).

      → Reply
»
11 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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\}$$$.

→ Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
11 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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\}$$$.

    → Reply
    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it
        Spoiler
        → Reply
    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you!

      → Reply