Problem - 818F - Codeforces

So I’m doing this problem and got an AC with this solution. However, I don’t really understand *why* the optimal arrangement is to have a mess in the middle and some bridges branching out.

Any help would be appreciated. Thanks!

Uh @SansPapyrus683 I can’t seem to open the solution.

Yeah- I think the link expired.

Here’s the raw code:

```
#include <iostream>
using std::cout;
using std::endl;
bool edges_fittable(long long vertices, long long edges) {
if (vertices <= 1) {
return edges == 0;
}
long long bridge_num = edges % 2 == 0 ? edges / 2 : edges / 2 + 1;
vertices -= bridge_num;
edges -= bridge_num;
return vertices >= 0 && ((long long) vertices) * (vertices - 1) / 2 >= edges;
}
/**
* https://codeforces.com/problemset/problem/818/F
* 3
* 3
* 4
* 6 should output 2, 3, and 6, each on a newline
*/
int main() {
int test_num;
std::cin >> test_num;
for (int i = 0; i < test_num; i++) {
long long vertex_num;
std::cin >> vertex_num;
long long lo = 0;
long long hi = vertex_num * vertex_num; // why in frick does cpp not have an exp operator
long long valid = -1;
// cout << edges_fittable(vertex_num, 33964120395954290);
while (lo <= hi) {
long long mid = (lo + hi) / 2;
if (edges_fittable(vertex_num, mid)) {
valid = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
cout << valid << endl;
}
}
```