It's a gym contest.

Contest will be available in Gym.

Minimum spanning tree, answer is maximum edge weight

Let's build graph, where string are verticles abd between each pair of verticles there is an edge of weight equal to difference between strings. Now question is: what is the smallest K such a graph with edges with weights <=K is connected. It can be done using binary search. If we fix K we just do dfs which is going by edges <= K and check if graph is connected

my solution : build graph with recipes. g[i][j] is equal to distance between recipe i and recipe j. then use binsearh for answer: for the fixed answer there shuold be a path with all recipes and without edges with weight greater then anwer

ans = 0
while (true) {
  posA = (position of the rightmost not processed 'A')
  posF = (position of the leftmost not processed 'F')
  if (posA < posF) break
  ans += posA - posF
}

Here's my idea: all we want to do is all As should come before F. Now considering A and F are some values such that A<F now we want to calculate no of inversions ( problem becomes similar to sorting an array with only operation of swapping two adjacent elements. I dont know proof but its equal to no of inversions in the array). Now main problem is every N can be taken as A or F. Which we can solve using a recursive function with two arguments 1.position we are referring to 2.no of Ns considered as F before this position. For every F just count no of As after that position. For every A dont do anything. Now for every N if we consider it as F do same thing as normal F and if its A then add to the answer total no of Fs before this position (original no of F + considered ones). I hope this helps.

consider dp[i][j][k] which means how many swaps do we need to move all A's in first k positions of substring(i,j) and moves F's out of first positions.
then you can update dp so easily.

Something similar to:
7 5
1 1 1 1 1 5 1
Correct answer is
7
+++++-+
but your answer is 5.
Correct approach is dynamic programming dp[i][j] — are we able to get number j after i moves.

Try this:

4 100
50 10 10 60

Build pairs of  < skill, field >  for each course, sort all of them in increasing order by skill and find an interval [i, j] of courses which has the following properties:

1. There exist at least one course for each field in that interval
2. Skill[j] - Skill[i] is minimum

dp[i][a][b] — the best result for i processed indices, a of them are chosen for the first player, b of them — for the second player.

There is also a flow solution but DP is much easier.

Sorry for my bad English.

C) Main idea: go from up halls to downs and for each hall keep set of disjoint intervals. Interval is a structure with following parameters:

• hall — hall number
• from — first moment such that we can come in interval
• to — last moment such that we can leave interval
• start — start of the flight such that we can come in interval in moment from
• prev — prev interval on hall with number hall - 1 or null if we start from hall with number hall

For each hall we can construct its intervals using intevals of previous hall (it is case when we come from up hall) and open segments of current hall (case when we start from that hall). After building intervals for current hall we have to merge them greedily. All that can be done in O(numberOfIntervals) operations if we keep intervals sorted by from and use two pointers. Maximum available value of numberOfIntervals is less or equal than , so we can process all halls with total asymptotic . Further we can find best interval. It is interval with minimal start such that to - start ≥ t. After we just need to restore the answer.

Source: pastebin.

D) I’ll just leave this here: part 5 in article.

E) Just find cutpoints and biconnected components and construct tree of biconnected components. After that we can use dfs on that tree to calculate for each cutpoint sizes of children components and size of parents components. English, Russian. It can be done in O(m) operations.

Source: pastebin.

H) It will be written later by me or elena.

J) In first calculate maxGame  –  prefix maximum of queries(lengths of games) and sort gamers by t. After that come from the last game to the first and for game number i will be add gamers with t ≥ maxGame[i] in DSU. Answer for game number i: g[i] * size(0), where size(0) — size of set, which contains knight. It also can be solved by BFS and TreeSet. Asymptotic: O(m·α(n)).

Source: DSU, BFS.

some write ups in rev 1.

Your submission is not available for all.

And why will we use straightforward approach small amount of times?