FreeHit's blog

Regarding Edu section of Step 3 Binary Search question- A. Get together
By FreeHit, history, 7 months ago, In English

I want to code A. Get together with approach by limiting value of f(t) ? but i cant get through it ? can i use sweep line algorithm.... after limiting value?and how to code it?here is link to question https://codeforces.com/edu/course/2/lesson/6/3/practice/contest/285083/problem/A

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

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

You can binary search on the answer, and maintain a segment that everyone can reach. If the segment is non-empty then the value is ok.

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

    i find function to be unimodal so ternary search is most optimal then binary search.

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

      How is the function unimodal?

      → Reply
      • »
        »
        »
        »
        7 months ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        by general intution plot will be minima type where at local minima there will be minimum time requird for all peoples to collect at place.

        still can get more precise

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

    how to find out that segment where everyone can reach

    → Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Even I amn't able to get this, we know that my valid answer will be between [ xi — vi*t , vi*t + xi ], but how to binary search on this?? Also, the problem states that the absolute error should be less than 1e-6. Can someone tell how to proceed with it??

→ Reply