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
→ Pay attention
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3831 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | gamegame | 3386 |
| 10 | ksun48 | 3373 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Nov/05/2024 08:41:24 (k2).
Desktop version, switch to mobile version.
Supported by
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.
Claim 1: Optimal choice for $$$x$$$, given some $$$m$$$ values, will then surely be between the $$$m$$$ , i.e. $$$p_{1} \le x \le p_{m}$$$.
Proof: (By contradiction) Let's assume that $$$x \lt p_{1}$$$, Then obviously $$$x = p_{1}$$$ is better option. Similiarly for other case, if $$$x \gt p_{m}$$$, then $$$x = p_{m}$$$ is better. So Claim 1 must be true.
Claim 2: When you take any $$$x$$$ such that, $$$p_{1} \le x \le p_{m}$$$, then Farthest point from $$$x$$$ is either $$$p_{1}$$$ or $$$p_{m}$$$.
Proof: This is obvious, because we have $$$p_{1}$$$ through $$$p_{m}$$$ in sorted manner.
Final Claim: Best option for x ( as a real number ) is $$$(p_{1} + p_{m})/2$$$. So, if we require integer point for $$$x$$$, we must check floor and ceil of this real number.
Proof: Since we want such $$$x$$$, that farthest point among $$$m$$$ points is closest to $$$x$$$, and we know that farthest point among $$$m$$$ points is either first one, or last one ( by Claim 2 ), then to minimize the distance from farthest point we must have distance of $$$x$$$ from both $$$p_{1}$$$ and $$$p_{m}$$$ to be least possible, which means $$$x$$$ must be roughly at mid-point of $$$p_{1}$$$ and $$$p_{m}$$$.
Solve these parts with $$$m = k+1$$$.
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|).
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.