# Why does this work lol

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.

oh lol, can you repost?

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;
}
}
``````