jerseyguy's blog

Needed some hints to this problem
By jerseyguy, history, 5 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 (6)
| Write comment?
»
5 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
Hint 1
Hint 2
Hint 3

Hope that helps!

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

    got it thanks

    → Reply
  • »
    »
    4 years ago, hide # ^ |
     
    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
    • »
      »
      »
      4 years ago, hide # ^ |
       
      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
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    can we apply dfs also ?

    → Reply