chokudai's blog

AtCoder Beginner Contest 276 Announcement
By chokudai, history, 3 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?
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can anybody give some hints to solve G ?

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

whats wrong in d sol 6 tc failing

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

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

→ Reply