Why does this work lol

Problems and Contests
#1

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!

#2

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

#3

Yeah- I think the link expired.

#4

oh lol, can you repost?

#5

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