jerseyguy's blog

Needed some hints to this problem
By jerseyguy, history, 3 years ago, In English

Can someone give some hints to this problem from cf edu. Problem : D. Minimum maximum on the Path

Regards.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Hint 1
Hint 2
Hint 3

Hope that helps!

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

    got it thanks

    → Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    hey maxwellzen thanks for the hint, but how are you proving that it will be a .....1111110000.... or .....00000011111.... type of function in x.

    I get this "If the maximum is some number x then you're only allowed to use edges with a value less than or equal to x" but how can we say that this x is the optimal answer, or no other x left or right to it?

    → Reply
    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If you can connect node 1 to node n in a way such that the maximum edge has a value at most x, then you guarantee that you can connect node 1 to node n in a way such that the maximum edge has a value greater than or equal to x. Therefore, the BS check function has the form ..00000111111..

      → Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can we apply dfs also ?

    → Reply