chokudai's blog

By chokudai, history, 2 months 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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

5 hours to go! ALL THE BEST Everyone !

»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

How to do D ?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
  • »
    »
    2 months 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

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

      How will it work for this test case 20 0 ?

      • »
        »
        »
        »
        2 months 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.

      • »
        »
        »
        »
        2 months 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
        • »
          »
          »
          »
          »
          2 months ago, # ^ |
          Rev. 3   Vote: I like it 0 Vote: I do not like it

          how about this

          4 3
          1 2
          1 3
          1 4
          
        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          That is incorrect. Solution would still exist if degree>=3. According to me solution wouldn't exist if and only if any node has at least three neighbours which are connected to each other.

    • »
      »
      »
      2 months 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?

      • »
        »
        »
        »
        2 months 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.

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

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

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

      What exactly you mean by topological sort here ? thee given graph is an undirected one

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

      Can you explain why are you returning 1 in your brute function when we reach the end of a list? Should we not return 0 there?

  • »
    »
    2 months 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)

    • »
      »
      »
      2 months 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)?

  • »
    »
    2 months 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

»
2 months 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.

  • »
    »
    2 months 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.

    • »
      »
      »
      2 months 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

  • »
    »
    2 months 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?

    • »
      »
      »
      2 months 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).

  • »
    »
    2 months 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.

»
2 months 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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can we solve D using bitmask DP?

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

    Maybe, but since it is a graph with cycles it is hard to come up with states for the dp because of not a strict topological ordering of states.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

»
2 months 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..

  • »
    »
    2 months 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.

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

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

      • »
        »
        »
        »
        2 months 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.

»
2 months 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.

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

    +1

  • »
    »
    2 months 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

  • »
    »
    2 months 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

    • »
      »
      »
      2 months 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

»
2 months 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

  • »
    »
    2 months 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)

»
2 months 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

  • »
    »
    2 months 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.

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

      O ya, thanks for your countertest. I removed now this condition and got accepted!

»
2 months 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

  • »
    »
    2 months 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.

    • »
      »
      »
      2 months 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 :)

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

        Thanks a lot man! This had been bugging me a lot. Now it makes sense.

»
2 months 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.

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    what was the use of dfs tree in problem D?

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it -33 Vote: I do not like it

      My solution is same as this https://codeforces.com/blog/entry/89979?mobile=false#comment-784021

      The dfs tree just automatically defines a toposort, which is something i realised after the contest.

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

        why can't we solve this without using a dfs tree? Can we simply use backtrack in dfs like you did just without defining that level thing?

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        Dfs tree approach is a nice one. Earlier I thought of a approach that had something to do with the cycles in the graph but wasn't able to conclude something with that. If you have any ideas that may help with such a approach it would be helpful to know. Peace

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain what problem E asked to do?

»
2 months 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...?