Please read the new rule regarding the restriction on the use of AI tools. ×

dwellings's blog

Maybe the best solution to CF #228 Problem B
By dwellings, 11 years ago, In English

For the largest k=2^29-1, the standard solution (STD) use about 500 vertices, but my solution only use less than 100 vertices (exactly 92).

For example, if needs 1 path, add an edge between 61 & 92. if needs 2 paths, add an edge between 59 & 91. More commonly, if needs 2^n paths, add an edge between 61-n*2 & 92-n.

For the input k, transform k to binary type. For example k = 9 = (1001)2. Add edges between 61 & 92, 55 & 88.

You can view my code here 5891486

PS. Taube 5886357 seems to have a better solution for he use less than 90 vertices.

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

»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I had the same idea of putting k into binary, and my solution also only uses 100 nodes.

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

    I had the same idea too... But my code's answer has 95 vertexes for every valid test :D

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

I think that the best solution is your solution, but instead of nesting 2 by 2 nodes, do it 4 by 4.

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

Firstly I used the same idea (I called it 'two columns') and got n=1036 (!!!), then I use 'four columns ' to reduce n into 660.

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

I think that we can consider the following idea:

k = a[1]*(b1^b1) + a[2]*(b2^b2) + ...

x^x can be described by a table x*x. Cell[i][j] connects to every Cell[i+1][1..x].

I'm sorry that my bad English couldn't describe this idea better.

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

awesome solution!

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

My solution is same.

→ Reply