chokudai's blog

AtCoder Beginner Contest 199（Sponsored by Panasonic） Announcement
By chokudai, history, 4 years ago, In English

We will hold AtCoder Beginner Contest 199（Sponsored by Panasonic）.

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

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

Comments Comments (48)
| Write comment?
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

It felt like it was just the opposite of Last ABC198.

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

How to do D ?

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

    The Editorial is out.

    https://atcoder.jp/contests/abc199/editorial

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 6   Vote: I like it +6 Vote: I do not like it

    Create a topological sort(or just some ordering) for the different components. The First vertex in the sorting of the component has 3 options and the rest have 2 options, so you can bruteforce in $$$O($$$$$$N$$$$$$2^N$$$).

    Submission

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

      How will it work for this test case 20 0 ?

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

        There will be 20 separate components and just the first vertex will have 3 options, so 3^20.

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

        I dont know why my solution fails...I have used the following logic :

        If any of the vertices of a component have degree 3 or higher so our total answer is 0 as there will be atleast one edge having same colored vertices by PHP.

        So now our graph will be of a chain form.

        Now this chain can be of 2 types:

        Case-1 : Connected on the 2 ends so there is exactly one cycle.

        - Contribution of such a component would be 3*2^(Size of component-2).

        Case-2 : Or this chain is just a normal chain.

        - Contribution of such a component would be 3*2^(Size of component-1).

        Total answer would be multiplication of all such individual components.

        It passes on some 35 cases.

        Code :

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

      what was the use of topo sort? why cant we do direct dfs?

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

        Idk maybe you can use direct dfs but I used an ordering so I can represent the component as a list and assign the colors from left to right.

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

          by component, u mean disconnected component? or any thing else

          → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    We can fix a subset of vertexes that will be assigned a particular colour. After checking if that subset is valid, we can do bicoloring on the remaining vertexes, we can swap both the colours in the bicoloring, so if bicoloring is possible ,we have 2 ways to colour it, As we won't visit the nodes, whose colour has been already fixed, so we will get more than one components, we can multiply the result of each component. Overall Time Complexity will be O(N*2^N)

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

      To check for bipartiteness in $$$O(N)$$$, I converted the adjacency list of a vertex to bitmask and used bitwise operations. Did you do the same, and if not, how did you calculate bipartiteness in linear time of number of nodes (and not in linear time of number of edges)?

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

    simply take a array named marked and mark all the vertex you encounter during input.The dfs(1) in the dfs function their are three base cases 1. If your currentt vertex(now)==n+1 simply increment ans and return 2. if you find a unmarked array just go for dfs(now+1) and return 3. else just loop from 1 to 3 set te colour of current vertex as i and check if any child has same colour if not go for next dfs

    HOPE THIS HELPS! Link to my solution

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

      Your solution link is taking to the problem.

      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Why is the editorial solution for D not 2^n * n^2? I have a similar algorithm, where I start a DFS and perform a 2-coloring. But I would think the DFS requires O(N^2) time, since there are O(N^2) edges.

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

    But you wont visit all edges right ? Maximum visit is N ig cuz each dfs call takes you to a new vertex.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      well the complexity of dfs is O(N+M) so he is kind of right since u have a loop towards all the neighbours of a paticular vertex in dfs

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

    Can you elaborate a bit more on how to use the 2-colouring DFS method to solve this problem?

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

      My solution is almost the same as the editorial, except I implemented it a bit differently. One way to think about this problem is that if we fix the nodes of one color, you only have two other colors left to color with (which just corresponds to the number of two colorings of the graph).

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

    I guess you could check if a certain coloring is valid in O(3*n) by using mask (actually it would divide the complexity by 32, which is bigger then n, which means O(1)). In more detail: for a certain coloring, for every color x, get the mask of nodes with color x. Also represent the neighbors of a certain node as a mask too. If the mask of neighbors of a node with color x has any common bit set with the mask of all nodes with color x, then it is not valid.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to Solve D?

My failed solution:- for a connected component assign the all node as 3 and run a dfs if the current node points towards x already visited mode then subract x from 3(note minimum value for particular node is 0) then multiply value of all the nodes.

final ans = multiplication ans of each connected component

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can we solve D using bitmask DP?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what will be the complexity of DP with bitmask of E??

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

    It would be $$${O(N * (2 ^ N))}$$$ in the worst case.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

MY submission for c Can anyone tell me why my submission for c did not tle?? I was swapping two strings in type two..

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

    string.swap(string) actually does not copy the strings, but only pointers to them.

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

      OK, Thank you , didn't knew about this thing earlier :)

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

        It is same for other structures like vector, set and the like, they all support such a quick swap method.

        → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Editorial of E seems more complecated than the problem itself. Can somebody explain?

I have difficulties to understand any of the formulars.

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

    We can do it in O(N*M*2^N). We can try to put each possible value at current position if current value satisfies all the given inequalities. we can implement it using a DP of dp[N][1<<N]. https://atcoder.jp/contests/abc199/submissions/22031532

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +11 Vote: I do not like it

    What I did was the following —

    • For each $$$x$$$ store all the possible $$$(y, z)$$$ along with it.
    • Calculate the answer using bitmask DP where $$$dp[i][mask]$$$ denotes that we have placed elements till $$$i^{th}$$$ position and the numbers already placed are represented by $$$mask$$$
    • When I am on a certain $$$i$$$ check whether the all the stored $$$(y, z)$$$ for that particular index are satisfied or not.
    • If all are satisfied, transition into next state by setting one of the unset bit of $$$mask$$$ and increment $$$i$$$
    • Return 0 when $$$i = n$$$

    Link to submission — https://atcoder.jp/contests/abc199/submissions/22030060

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +8 Vote: I do not like it

      Note that you dont need dp[i][mask] cuz i == __builtin_popcount of the mask, therefore i is redundant, dp[mask] is enough

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

      Regarding:

      When I am on a certain $$$i$$$ check whether the all the stored $$$(y,z)$$$ for that particular index are satisfied or not.

      What about the order of the added elements? Isn't that important in the permutation?

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

problem C is solvable if we just implement the query naively and ignoring any 2 consecutive query of type 2
i am not sure why this pass the time limit though

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

    Yeah, it shouldn't because that's just $$$O(N^2)$$$ with an easy optimization. I guess the tests were just weak, but maybe that means someone can add a hack (not sure what it's called in Atcoder)

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me whether my approach to problem D is wrong? I assumed that the maximum number of nodes coloured with a particular colour can't exceed N/2. So, i distributed the colours in such a way that the count of red , blue of green always remain less than N/2. It is giving WA on exactly three test cases. Code for Reference

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

    Consider:

    5 4
1 2
1 3
1 4
1 5

    Nodes 1 through 5 form one component. We can color Node 1 with red and nodes 2 to 5 with blue.

    → Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can anyone tell me a testcase where my solution fails for D? I am using dfs and at every node mutiplying (3 — neighbours which are not visited) with the answer till now and if I reach a node with 3 or more visited numbers, it becomes 0. Doing that for every connected component and multiplying all of their answers. My submission: https://atcoder.jp/contests/abc199/submissions/22038878

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

    Try

    5 6
1 2
1 3
1 4
5 2
5 3
5 4

    gives 12, should be 30.

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

      Here's an smaller case:

      4 4
1 2
2 3
1 4
4 3

      If we DFS from 1, and end up visiting in this order: 1 -> 2 -> 3 -> 4, when we are at 4, your solution would count that 4 can only have one color choice (since 1 and 3 have been visited), but since there is no edge between 1 and 3, nothing forbids them from having the same color.

      If this DFS algorithm worked, then k-coloring would be solvable in polynomial time :)

      → Reply
»
4 years ago, # |
  Vote: I like it -40 Vote: I do not like it

https://www.youtube.com/watch?v=2y3stYERBAI

This is my screencast(rank 77) for the contest along with solutions for all problems, do check it out if you're interested.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

Hello, can someone explain how does this solution for E comfortably pass?

https://atcoder.jp/contests/abc199/submissions/22041985

Isn't the time complexity $$$O(mn2^n)$$$?

For each available bit in the current bitmask we test all m conditions, and if this bit doesn't violate any condition we add it to our mask. n is up to 18 m is up to 100

$$$O(mn2^n)$$$ would then mean about 2^29 operations...?

→ Reply