DWLauraa's blog

My solution on CF #203 Problem E
By DWLauraa, 11 years ago, In English

I have a solution that I cannot prove whether it is true or not. However it passed all the final tests. See my code here 4635501

  1. Pick up 1 unmarked vertice w and 2 marked vertices u & v. The rest vertices are in the set V0.
  2. Add edge between vertices {w + v + V0} to form a complete undirected graph.
  3. Add edge between vertices w & u.
  4. Add edge between vertices u & all vertices in set S which are unmarked.

The maximum number of edges is (n-1)*(n-2)/2+1+(n-k-1).

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

»
11 years ago, # |
← Rev. 4   Vote: I like it +14 Vote: I do not like it

I thinks some details:

First , this graph is connected.

Second , if (n==k) it is right(Should output -1)

Third , It's unnecessary to get two marked verices. I think only one is enough. This one is connected with none of the marked vertices. Beacause of k>=2 We can find it is not connected with other marked vertices.

My solotion ID is 4631948

→ Reply