chokudai's blog

AtCoder Beginner Contest 276 Announcement
By chokudai, history, 2 years ago, In English

We will hold AtCoder Beginner Contest 276.

The point values will be 100-200-300-400-500-500-600-600. We are looking forward to your participation!

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

Comments Comments (10)
| Write comment?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody give some hints to solve G ?

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

    Try to enumerate a[n] , and look at the array b such that b[i]=a[i]-a[i-1] (a[0]=0).

    Sorry for my poor English.

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

whats wrong in d sol 6 tc failing

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

In editorial for E, where does the number 6 come from?

Therefore, it is sufficient to inspect all (at most 6) pairs of different squares adjacent to the starting square to check if there is a path connecting those squares consisting only of road squares.

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

Alternative solution of E :

Lets store a color value for each vertex, initially $$$-1$$$.
Color the $$$4$$$ adjacent vertices of $$$S$$$ by $$$1,2,3,4$$$.
Then do one BFS.
Initially insert all $$$4$$$ adjacent vertices of $$$S$$$ in BFS queue.
If you reach vertex $$$(i,j)$$$ from $$$(x,y)$$$ :
— If $$$color[i][j]$$$ is $$$-1$$$, then assign it $$$color[x][y]$$$
— Else if $$$color[i][j]$$$ is not $$$-1$$$ and its also not equal to $$$color[x][y]$$$, then we can reach one adjacent vertex of $$$S$$$ from another. Set the answer to "Yes"

Accepted Code

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

    I did the same. I used 'n', 'w', 's', 'e' instead of 1 2 3 4. Submission

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

    There's another solution in which we directly find the cycle containing the start point and having maximum length. If its length is greater than 3, the answer is "yes", else "no". Simple DFS

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

    here. you don't consider the lenght of the cycle. please details, how it is work? **if the grid is : 1. #### 2. #..#
    3. #.S#
    4. ####

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

Is there any approach different from the editorial of problem G?

→ Reply