Vesper_Lynd's blog

DIV 1 B?
By Vesper_Lynd, history, 6 years ago, In English

IN THIS PROBLEM I DON'T UNDERSTAND THE GRAPH APPROACH FOR THIS PROBLEM? CAN ANYBODY HELP OUT!! PROBLEM LINK TUTORIAL LINK

  • Vote: I like it
  • -23
  • Vote: I do not like it

»
6 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Make a graph with vertexes 1, 2, ..., n; for each i a substring sisi + 1...si + k - 1 should be a palindrome, so for each i you should make edges between si and si + k - 1, between si + 1 and si + k - 2, etc. For each connected component in this graph, letters should be equal in each vertex of that component; if number of components is e then the answer is me

→ Reply