Figured this out together with KrishnaForNow — sharing the idea here.
So let's read the problem. It says the sum of distances as we go 1 → 2 → 3 → ... → n → 1 (i.e. we come back to node 1 at the end) should equal exactly k. We need to build a tree that makes this true, or say it's impossible.
The first observation: every edge in the tree gets counted at least twice. Think about why — as we walk from one node to another and then eventually have to come back that way to reach some other part of the tree, we retrace the same edges. Take a simple line 1-2-3-4. We go 1→2→3→4, and then to get back to 1 we go 4→3→2→1. So the edges 1-2, 2-3, 3-4 all got walked twice.
This gives us two things immediately:
khas to be even. It's built entirely out of these "at least twice" contributions, so it can never land on an odd number.khas a minimum value. Since every edge is crossed at least twice, the smallest possiblekis2 * (n-1)(there aren-1edges in any tree). You can hit this minimum with a straight line1-2-3-...-n, or with a star — doesn't matter, both give you exactly2*(n-1).
Now what's the upper bound?
I tried this out on small n by hand and noticed a pattern: the max happens when you build the tree like this — odd numbers going up, even numbers coming back down. So something like 1, 3, 5, 7, 8, 6, 4, 2 for n=8. Going from the ith node to the i+1th this way makes the distance as large as possible at every step, because you're always jumping across the "middle" of the tree.
Doing this gives a max upper bound of n*n / 2.
So now we've got three cases where the answer is -1:
kis oddk < 2 * (n-1)k > n*n / 2
For everything else, a valid tree exists — here's how to build it.
Building it
We already know we can hit the maximum k with the odd-ascending, even-descending tree. Now here's the trick I noticed: if you take the last node of the tree and shift it to connect to a different node, the total distance decreases by exactly 2 — as long as the node you're attaching it to is "greater" (i.e. further up the spine, closer to the middle/root) than where it was before. If you go the wrong direction, the distance just goes back up.
Example: take 1 3 5 7 8 6 4 2 (n=8). This gives k = 32.
If I shift 2 off of 4 and connect it to 6 instead, the distance drops by 2, so k becomes 30. And I can keep doing this — take 2 and slide it up again to 5, k drops another 2. I can keep sliding a leaf up until it hits its limit — I can't drag it past its "half point" without breaking the pattern, so after that I move on and start sliding the next leaf from the bottom instead.
If I keep doing this until every even node ends up directly attached to its natural odd pair (2 to 3, 4 to 5, 6 to 7, etc.) it's guaranteed to land on the smallest possible k, which is 2 * (n-1).
So the actual algorithm is:
- Build the max spine: odds ascending then evens descending.
- Figure out how much we need to reduce:
(max_k - k) / 2— this is how many "slides" we need to do. - Repeatedly grab the last node in the spine and slide it up as far as it can go (or as far as we still need), pop it off, and move to the next one if we still need more.
- Print whatever's left of the spine as-is.
Worked example: n = 8, k = 16
min_k = 14,max_k = 32, and 16 is even and in range, so it's constructible.- Spine:
1, 3, 5, 7, 8, 6, 4, 2 - We need
(32 - 16)/2 = 8slides.
Take the tail, 2. It can slide from its current spot (attached to 4) up until it hits 3 (its limit is 2/2 = 1, i.e. it can't go past node 3). That's 5 slides used. We still need 3 more.
Take the new tail, 4. It can slide from 6 up to 5 (its limit is 4/2 = 2). That's exactly 3 slides, and we're done.
Final tree: spine 1-3-5-7-8-6, with 2 attached to 3 and 4 attached to 5. If you trace 1→2→...→8→1 on this tree, it sums to exactly 16.
Accepted submission: 383513489
Runs in O(n) per test case.
That's basically the whole idea — build the max, then slide leaves up one at a time until you land exactly on k. Hope this helps.
This is my first editorial, so if you have any suggestions, feel free to comment!
— joyboy24
