Hint: If you fix some node, all the shortest paths between it and all the other nodes will use all edges except for one (the one coming after the farthest node). Also, if you find the farthest node from i, the farthest node from i + 1 must be found afterwards (or it could possibly be the same one as the farthest node from i).

facing same problem :(

Problem I: First if N is odd and there's any cheating pair then the answer is -1 by default (figure out why). Otherwise, when two friends are a cheating pair, this means in an optimal solution one of them sits in an even position and the other one in an odd position. This also indicates that if we construct a graph where two friends have an edge if they're a cheating pair, and we couldn't make it into a bipartite graph then the answer is also -1 since there's a conflict. If not, we would have many independent components each divided into 2 parts (let's call them first and second). The solution is as follows: if we can select from each component either the first or second and the number of nodes we took in total is N/2 (note that the ones we didn't take are also N/2) then we can put those non-cheating nodes together in even seats, and the other N/2 in odd seats and we will have our solution. If we can't do that then the answer is also -1. This can be done using dynamic programming (check the limits).

Problem J: I'm not really sure about the proof, but the solution is as simple as: If the sum of distances of each marble with its corresponding home spot is divisible by 7 then the answer is "yes", otherwise "no". Though I'm not really sure of the proof to be honest.. If anyone could share why this is always right it'd be great :D

since there is always at least one road that is destroyed, we can shift the cities and roads such that the destroyed road connects the new city at location 1 and the new city at location n, now our array is no longer cyclic and we can run dp on it.

let dp[i] denote the minimum cost such that all the paths that start in the interval 1..i — 1 are cut.
dp[1] = 0.
when we want to calculate dp[i], there will be two options to do with the road (i — 1, i).
1- keep the road: now consider all the paths that pass thru this road and let j be the maximum beginning of all those paths, dp[i] = min(dp[i], dp[k]) for j < k < i, because if we take any k <= j, then the path that starts at j wont be cut.
2- destroy the road: similar to the above, consider all paths that do not pass thru this road and let j be the maximum beginning of all those paths, dp[i] = min(dp[i], dp[k] + cost) for j < k < i, since we are destroying this road, any path that pass thru it should be cut and if we take any k <= j, then the path that starts at j wont be cut.

you can also denote by dp[i] the minimum such that the road (i — 1, i) is destroyed and all paths that start before i are cut, the transaction should be very similar to the above.
this dp can be calculated in O(N²), but we can also do it in O(NlogN) with segment tree or in O(N) with minimum sliding window technique(using deques).
my code using deques.

15 12
BGGRGRRGGRBBBBR
12 14
3 9
9 14
2 3
8 14
10 13
10 15
13 14
1 4
5 13
1 7
14 14

The answer for the last two queries is 5 5 5.

UPD: Actually from query 3 the answer is wrong.