Lain's blog

By Lain, history, 7 months ago, In English

I was reading the editorial for 1136D, and solution 2 talks about a graph-based solution. I didn't completely understand it. I understood the graph they built(I think), and the answer is the number of unreachable vertices, but what is this "standard algorithm" called DFS by complement graph? I've never heard of it, and I just see a bunch of papers on Googling, which leads me to believe it isn't as standard as the editorialist claims it is. Also, if this is the standard definition of a complement graph, why is the graph described in the problem the complement of the provided graph? Is it assuming I remove all the edges where $$$v$$$ is behind $$$u$$$?

I've posted this blog since comments about the same on the editorial went ignored, so I hope this will reach more people. Thanks in advance.

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

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

The problem is beautiful but the explanations for the solution are really a mess. I suppose that all you have to do is to change the number of the pupils standing in line (1,2,...,n instead p[1],p[2],...,p[n]) and correspondingly in all the pairs (u,v), easy task using a map. After that, imagine the graph having vertices 1,2,3,...,n and directed edges u->v if v<u and v AGREES to switch the place with u. In this graph we are interested in the maximal number of positions the vertex corresponding to Nastya can advance to the beginning of the row, that is the number of reachable vertices (the official solution is fuzzy because they count the number of unreachable vertices in the complement graph, actually the same thing)

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    This isn't true is it? Consider the queue 1 2 3 4 5. Then I add one edge — 5 -> 2. I can reach one vertex, but I cannot actually move that far ahead. Am I misunderstanding what you're saying?