Блог пользователя chokudai

Автор chokudai, история, 6 лет назад, По-английски

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!

  • Проголосовать: нравится
  • +41
  • Проголосовать: не нравится

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

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

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

How to do D ?

  • »
    »
    6 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
  • »
    »
    6 лет назад, скрыть # ^ |
    ← Rev. 6  
    Проголосовать: нравится +6 Проголосовать: не нравится

    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

    • »
      »
      »
      6 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

      How will it work for this test case 20 0 ?

      • »
        »
        »
        »
        6 лет назад, скрыть # ^ |
        ← Rev. 2  
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        6 лет назад, скрыть # ^ |
        ← Rev. 4  
        Проголосовать: нравится 0 Проголосовать: не нравится

        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
    • »
      »
      »
      6 лет назад, скрыть # ^ |
      ← Rev. 2  
      Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, скрыть # ^ |
    ← Rev. 2  
    Проголосовать: нравится +8 Проголосовать: не нравится

    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)

    • »
      »
      »
      6 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
6 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +1 Проголосовать: не нравится

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.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Can we solve D using bitmask DP?

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

I have difficulties to understand any of the formulars.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    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)

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +3 Проголосовать: не нравится

    Try

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

    gives 12, should be 30.

    • »
      »
      »
      6 лет назад, скрыть # ^ |
      ← Rev. 3  
      Проголосовать: нравится +4 Проголосовать: не нравится

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

»
6 лет назад, скрыть # |
 
Проголосовать: нравится -40 Проголосовать: не нравится

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.

»
6 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится -8 Проголосовать: не нравится

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