M-SOLUTIONS Programming Contest 2021(AtCoder Beginner Contest 232) Announcement

We will hold M-SOLUTIONS Programming Contest 2021(AtCoder Beginner Contest 232).

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

We are looking forward to your participation!

Comments (24)

• 16 hours ago, # ^ |

  ← Rev. 2 →  

  0

  lmao I did the same exact thing, I would like to know why this doesn't work as well

  • 15 hours ago, # ^ |

    ← Rev. 2 →  

    +9

    Yes even i did the same thing.. and got WA.

    I realized later that "the degree sequence of two graphs should be same to be isomorphic" — this is a necessary but not sufficient condition.

    So what I did was to store the component sizes of each node of two graphs and checked if both are equal. Luckily it passed. But this too is wrong!

    I guess the test cases are weak.

    This the the ac code which I wrote:

    However this code gives wrong answer on this test case:

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

    The answer should be "No" but my code prints "Yes"

    I didn't see the constraints initially (stupid mistake I know). But the intended solution is to use brute force

• 16 hours ago, # ^ |

  Your solution is actually very wrong, it should definitely not pass that many testcases. Graph isomorphism is a hard problem, in here you just need to enumerate all permutations P from the statement and check whether the statement condition holds. You can do that with std::next_permutation().

  • 16 hours ago, # ^ |

    I implemented the intended solution but used adjacency list instead of adjacency matrix and failed 5 cases. Can you please help me figure out what's up?

    • 15 hours ago, # ^ |

      I also did the same way and got AC but my condition to check whether the permutation is valid or not is different.

      Here is my Submission: https://atcoder.jp/contests/abc232/submissions/28008891

  • 12 hours ago, # ^ |

    My submission also fails on only one test case. Weak tests I guess. next_permutation worked.

• 16 hours ago, # ^ |

  Use next_permutation()

• 16 hours ago, # ^ |

  ← Rev. 5 →  

  +4

  Use the edge connectivities, not the degrees. Two graphs might have the same degrees but aren't isomorphic.

  Try this input

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

  • 16 hours ago, # ^ |

    Can you please share an example of when the degrees are equivalent but the graphs are not isomorphic?

    • 16 hours ago, # ^ |

      _\_ _\_ and _\_\_ _

    • 16 hours ago, # ^ |

      I added an example to my comment.

    • 16 hours ago, # ^ |

      Check the structures of 2-Methylpentane and 3-Methylpentane. Same degrees, but not graph isomers.

• 16 hours ago, # ^ |

  Brute force all the permutations using std::next_permutation() and check if the condition mentioned holds true

• 13 hours ago, # ^ |

  ← Rev. 2 →  

  0

  How about this (3×2)(3×2) chessboard?

  E E Source E Target E

  There is exactly one way to go from source to target in 2 moves, while your code reports it to be zero.

• 13 hours ago, # ^ |

  The approach is fine. I implemented the same method and got AC. Here is my implementation. Sub

• 39 minutes ago, # ^ |

  ← Rev. 3 →  

  +3

  I solved it using recursive DP. We just have to maintain that the if our current row matches with the final row or not, and our current column matches with current column or not( Actual row and column values don't matter here ,we just need to maintain that they are equal to final ones or not, so we can use 0/1 to denote that) . So currently if we are in same row as the final row, we can go to any other row and it will be equivalent (n-1 such rows) . If we are in some other row, we have two choices, either we can go to the final row or some other row (n-2 such rows). So similarly we can do it for columns. After K moves we can check if our both row and column are equal to final row and column or not. dp will look like dp[2][2][K] and each transition will be done in constant time . So overall Time complexity will be O(K).

  Submission : https://atcoder.jp/contests/abc232/submissions/28006837