Thanks for the scoreboard! And I've corrected the title, thanks for pointing it out...

I'd like to know about D, F, J and K. The only one I had a clue about how I'd start was F, but couldn't come up with a working solution in the last 30 minutes

For each trip plan you choose, you'll always take the maximum amount OF kids, which is the GCD of the islands in the plan. Also remember that the problem doesn't ask for the maximum K, but for the amount of different K's

Lets focus on a numeric string and 1 base indexed.

It's a dp problem, define f(N, S) how many positions up to N sums S, work with S mod 3.

Lets define A as the sum of the digits up to N in mod 3.

For each digit d in the string (d mod 3) 0 <  = d < 3 do.

• Add d to A, keeping A mod 3.
• If A is zero, this is already a substhreeng Add 1 to answer.
• Add to the answer f(N-1,A)

As an example, consider the following String "20144"

1. d = 2, add d to A, now A is 2, add f(0, 2) = 0
2. d = 0, add d to A, now A is 2, add f(1, 2) = 1
3. d = 1, add d to A, now A is 0, add 1 + f(2, 0) = 1
4. d = 4, add d to A, now A is 1, add f(3, 1) = 0
5. d = 4, add d to A, now A is 2, add f(4, 2) = 2

So the number of substhreengs is 4, {0, 201, 0144, 144}

You can solve this problem using Dynamic Programming on the input graph with state(node, actual_gcd). For each new state you reach, just add the corresponding gcd at some set recording all the possible answers. The key idea for this implementation is to realize that the number of divisors of any number between 1 and 10^5 won't be big, and because of that, the number of possible actual_gcd's too.

To solve this problem you have to realize that the answer is: for every non-empty connected sub-graph of the input graph, take the GCD of the values of all nodes in the sub-graph and store it. That GCD is a possible k, the number of different k's is the answer of the problem. To make a working implementation of this idea, let's iterate over all different GCD's (not that many) and try to find a connected sub-graph such that the GCD of the values of their nodes is exactly the one we are considering. How to do that? Well, if we are considering GCD g, then all nodes whose values are not divisible by g can be discarded, the resulting sub-graph has only nodes whose values are divisible by g. Now, let's make a DFS on any node of this sub-graph keeping the current GCD of the values of the visited nodes: every time we visit a new node, the current GCD cannot increase and will always be greater or equal than g, so here a greedy approach works. Find the GCD of all connected components of the sub-graph (as explained before) and check if any of them is equal to g, if so then g is a possible k.

The algorithm look like this:

For every node v:
  For every divisor d of value_of(v):
     Add v to sub-graph_d

def check(g):
  For every connected component c of sub-graph_g:
    x = GCD(c) // gcd of the values of the nodes of c
    if x == g:
      return True
  return False

sol = 0
For every possible GCD g:
  if check(g):
    sol++

Sorry I don't like to read other's code :(, B can be solved in O(N).

First of all let's define X as the number of black stones and Y the number of white stones in the first X positions.

You have to put all black stones in the first X positions of the string.

Start with the worst cost, which is Y * A, that comes from swap all Y white stones in the first X positions with the black stones that are not in the first X positions.

Now take white stones, starting with the one that is near to the position X, and try to improve the cost by doing continuous swaps until the first black stone to the right, you don't have to simulate it, it's just (BlackPosition - WhitePosition) * (A - B), if the cost gets lower update the cost otherwise terminate the algorithm.

To solve it in O(N) you can store the positions of the blacks or the whites stones or both, whatever works for you. :)

If you need a solution this is this is my solution.

You don't need scc, as caioaao suggests here, you just need to generate a graph, each point is adjacent only to points with distance less than or equal to 5.

Now for each connected component (not scc) color it (let's say 1 and 2) with a bfs, and pick the set with minimum size out of this two colors sets and add this size to your solution.

I think the approach is incorrect, there might be some cases where use the minimum distance for a pair will increase the distance for others, I can't find an example right now.

You have to use the property of circularity, sort all elements, to get the minimum cost, you have to pair each element with one of his neighbors in the sorted sequence, left or right.

There are only two options,

• Start from the first element and pair it with his right neighbor, advance two, do the same for the rest.
• Start from the second element and pair it with his right neighbor, advance two, do the same for the rest, pair last and first too.

Take the minimum of this two options.

As an example let's take the following input

1, 3, 4, 6

If I am not wrong your algorithm will form the following pairs (1, 3)(1, 4)(1, 6)(3, 4)(3, 6)(4, 6)

And greedily will take (3, 4) first, then as the only remaining option will be (1, 6) giving you 6 as answer, while the correct answer is 4, taking (1, 3) and (4, 6).