Prabal08's blog

Doubts in Problem C ( educational round 66)
By Prabal08, history, 5 years ago, In English

Can anyone explain me problem C ELECTRIFICATION from Educational Codeforces Round 66 (Rated for Div. 2). My doubts are from the tutorial are: 1. Since we need the dk+1 distance that means we should minimize distance to k+1 points so why we are looking over k points . 2. How they got the expression for f(x). The problem statement is https://codeforces.net/problemset/problem/1175/C and tutorial link is https://codeforces.net/blog/entry/67484

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

Comments Comments (3)
| Write comment?
»
5 years ago, # |
← Rev. 9   Vote: I like it +3 Vote: I do not like it

Answers to your Queries:

1). We are looking at $$$k+1$$$ consecutive points. ( Indexing from $$$0$$$ to $$$k$$$ means total of $$$k+1$$$ points ).

2). What do you mean by 'expression for $$$f(x)$$$', it was defined for you in the question.

Explanation for the problem:

Firstly, we notice that considering $$$k+1$$$ consecutive points is always better than non-consecutive points.

Then, after you have $$$k+1$$$ points selected, let's say they are numbered from $$$1$$$ to $$$k+1$$$ $$$( p_{1}, p_{2}, ..... , p_{k+1} )$$$ [ Note: this is sorted order ]. Then, main thing to note is that, the aim is to minimize the distance from $$$k+1$$$th closest point, and not all $$$k+1$$$ distances.

Hint 1
Hint 2
Hint 3 / Solution
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks Finally got AC. BTW by f(x) I meant the expression they had in tutorial to get the value of f(x) . This one fk(x)=min(|ai−1−x|,|ai+k−x|).

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

      Isn't that exactly what they defined it to be. You have to understand that clearly understanding the problem from given statement is also a part of solving the problem. They won't spell out everything for you. You have to make inferences, maybe in some cases think about similiar problems or transform given problem into something else which can be solved easily. This is all a part of solving the problem. But you don't have to worry too much about it, you should be fine as long as you keep practicing.

      → Reply