chokudai's blog

M-SOLUTIONS Programming Contest 2021(AtCoder Beginner Contest 232) Announcement
By chokudai, history, 3 years ago, In English

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!

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

Comments Comments (28)
| Write comment?
»
3 years ago, # |
  Vote: I like it +53 Vote: I do not like it

C++20 support when

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

How to solve C ? I'm just getting WA on one case and AC on the other 21 — Submission sad noises

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

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

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

      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

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

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

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

      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?

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

        I think the problem might be usage of a set. It will discard equal elements. Use multiset instead.

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

    Use next_permutation()

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

    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
    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

can we solve F with flow.

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

For problem E, how do you find theses DP optimization ideas ?

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

Can anyone explain, how we are getting 4 distinct value from f(k,i,j) and how we are forming those transitions? It would be a great help. Thanks!

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

    "for each k, there are at most 4 distinct values of f(k,i,j)" :

    • case 0 (i=0, j=0): Current row != Dest row. Current column != Dest column
    • case 1 (i=0, j=1): Current row != Dest row. Current column == Dest column
    • case 2 (i=1, j=0): Current row == Dest row. Current column != Dest column
    • case 3 (i=1, j=1): Current row == Dest row. Current column == Dest column

    My submission uses 4x4 = 16 transitions, although some transitions are impossible and can be simplified.

    → Reply
»
3 years ago, # |
← Rev. 7   Vote: I like it 0 Vote: I do not like it

My approach for E is different from the editorial, and I'm getting wrong answer on a few test cases. Any help would be much appreciated. Submission: Link

Approach: We are at (x1,y1) and want to reach (x2,y2) after exactly k operations. in one operation we can change either x or y. Let's say that we change x in p operations and y in k-p operations, and let dp1[p] be the number of ways to start from x1 and end at x2 after exactly p operations and dp2[k-p] be the number of ways to reach from y1 to y2 after exactly p-k operations, then I will add C(k,p)*dp1[p]*dp2[k-p] to my answer. (C(k,p) is the number of ways to select p operations that will change x out of the k operations)

Now as far as dp1 and dp2 are concerned. We can precalculate both of then as follows: dp1[i] = (w-1)^(i-1) — dp1[i-1]

dp1[0] is 1 if x1 = x2 and 0 otherwise

dp2[i] = (h-1)^(i-1) — dp2[i-1]

dp2[0] is 1 if y1 = y2 and 0 otherwise

Can anyone point out the flaw in this approach?

Update: nevermind I interchanged h and w.

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

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

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

One of the best atcoder contests

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

Can someone explain the solution of problem E.

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

    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

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

I did problem D using BFS but getting TLE.Anyone know how to resolve?

Problem link:-Problem-D

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

    I also solved the mentioned problem using BFS but got no TLE. Could you share your submission?

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

      My Submission-HERE

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

        Your function fun is very bad in more than one way (why recursion? why undirected graph when we are only allowed to move right and down?) and can't handle a 100x100 grid filled with '.' because it becomes too slow. You can change it to something like this:

        Spoiler

        But even building an adjacency list is an overkill.

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

    BFS should work just fine for this problem (example). But be sure not to visit the same cell more than once. If this isn't done, then a 100x100 grid filled with '.' would fail with TLE.

    → Reply