STICNOT - Sticky notes solution?

[sahil01123]

I thought exactly the same way and was lost trying DP on graphs. I could not contemplate the question such that it allows us to alter the structure!

[dance123]

Yeah, it sucks really. Do you think the fault is on our part though for not having interpreted correctly? I honestly feel like the question isn’t clear enough in defining what swapping of 2 edges means.

[sahil01123]

I don’t know exactly. On the top of it ,it was the second least solved problem which made such assumption non-trivial. Anyways what’s done is done!

[sahil0907]

With a somewhat similar idea, my submission bags TLE on the last two testcases, could you help as to why?
My Submission

@hitch_hiker42

Here’s my solution: STICNOT the first observation is that the connections in the tree are irrelevant: as long as the multisets of edge weights and node weights are same, the solution remains the same (and you can permute them in any way you like to form any tree in your mind but as you can swap edge weights among edges and node weights among nodes, the solution is independent of the structure of the tree).

What I did was sort the edge weights and node weights in non - decreasing order. Then I traversed through the edges and for each, I searched for the first matching node (the one that obeys the given constraints) using binary search. If we don’t find a match, we pay one coin and change the weight of a vertex (so that it now equals the next edge weight in sequence and the condition is just satisfied). If we find a match, however, we delete the node so that we don’t match it with any other edge in the future. Continuing this way, we have formed exactly n - 1 matchings in the end, with the invariant that one vertex is being matched and deleted in every iteration. The remaining vertex is tested with the last edge weight and if it already follows the condition, no more coin is paid and if it doesn’t, one more coin is paid and we change its value to that of the last edge. Now join each matching together to form a tree (it is always possible as we have paid to achieve the same) and viola, you’re done

[sharath1999]

Cool! This one’s way more elegant than mine.
I’m surprised such an easy answer was even possible but it makes sense.

[hitch_hiker42]

Okay see it like this: if you have a tree defined by a set of vertices and edges, how do you know which edge is which? Well, you may like to label them (like saying, for example, e₁, e₂, …) when the edge weights are uniform (or all equal) and it doesn’t pay to use a similar convention when we have different edge weights assigned to different edges/labels. So every edge has an identity, by which we can recognize (or simply identify it from every other in the tree). Likewise, say we assigned the vertices a set of labels to identify them. Now, what happens when swapping is allowed?

We swap edge weights among edges and node weights among vertices, and these two kinds of swaps would make you visualize that even if you fix the labels, the numbers (weights) within those labels are moving all around the tree (and that would give rise to all kinds of edge weight - node weight associations). The reason the structure is trivial is this: the constraints are on the edge weight - node weight associations and is it constant or varying to our will? Since we can change the associations with swaps which are not costing us anything, why won’t we (if that eventually minimizes what we actually may pay)? Because we are so lost in permuting the association and satisfying the constraints at every edge across the tree, we no longer care for the identities of the poor edges and nodes as long as we have a tree in the end. Hence, for the sake of visualization you can imagine the tree’s structure as complicated as you may or as simple as you may (like a line)

For reference, a solution and the corresponding submission link is posted above that builds on this observation.

@hitch_hiker42

Here’s my solution: STICNOT the first observation is that the connections in the tree are irrelevant: as long as the multisets of edge weights and node weights are same, the solution remains the same (and you can permute them in any way you like to form any tree in your mind but as you can swap edge weights among edges and node weights among nodes, the solution is independent of the structure of the tree).

What I did was sort the edge weights and node weights in non - decreasing order. Then I traversed through the edges and for each, I searched for the first matching node (the one that obeys the given constraints) using binary search. If we don’t find a match, we pay one coin and change the weight of a vertex (so that it now equals the next edge weight in sequence and the condition is just satisfied). If we find a match, however, we delete the node so that we don’t match it with any other edge in the future. Continuing this way, we have formed exactly n - 1 matchings in the end, with the invariant that one vertex is being matched and deleted in every iteration. The remaining vertex is tested with the last edge weight and if it already follows the condition, no more coin is paid and if it doesn’t, one more coin is paid and we change its value to that of the last edge. Now join each matching together to form a tree (it is always possible as we have paid to achieve the same) and viola, you’re done

[nipun_30]

the question said you could swap the values. Didn’t mention anything about whether you can change the structure or not!

[pulkit_mittal]

tree structure doesn’t even matter here

Does we don’t have to care for the degree of each vertex?

[sahil0907]

Nope, not really; although proving it might be difficult