A. Who Is The Winner

We can keep the name of the winner team while reading the input, if the current team solved more problems than the current winner, or solved the same number of problems but with less penalty, we set the current team as the winner:

cin >> curTeam >> curSolved >> curPenalty;
if (curSolved > winSolved || curSolved == winSolved && curPenalty < winPenalty){
	winTeam = curTeam;
	winSolved = curSolved;
	winPenalty = curPenalty;
}

Complexity: O(N)

B. Rock-Paper-Scissors

Let's start with the brute force solution, we can try all possible pairs (X, Y), if we know X and Y, then Z = N - X - Y.

The number of times Bahosain wins depends on the number of Scissors in the first X rounds, the number of Rocks in the next Y rounds, and the number of Papers in the last Z rounds.

We can find the number of times he will lose in a similar way.

int res = 0;
for (int X = 0; X <= N; ++X)
	for (int Y = 0; Y <= N; ++Y){
		int winCount = countInRange(0, X - 1, 'S')	 //     Rock > Scissors
			     + countInRange(X, X + Y - 1, 'R')   //    Paper > Rock
			     + countInRange(X + Y, N - 1, 'P');  // Scissors > Paper
		int loseCount = countInRange(0, X - 1, 'P')      //     Rock < Paper
			      + countInRange(X, X + Y - 1, 'S')  //    Paper < Scissors
			      + countInRange(X + Y, N - 1, 'R'); // Scissors < Rock
		if(winCount > loseCount)
			++res;
	}

This solution works in O(N³) if the function countInRange works in O(N), we can improve it using prefix sum (cumulative sum).

Create 3 arrays: rockSum, paperSum, and scissorsSum. We set rockSum[i] = 1 if there is a rock at index i. We fill the other two arrays in a similar way.

After calculating the prefix sums, we can modify countInRange to work in O(1). For example, to find the number of rocks in a range [L, R], we can use rockSum[R] - rockSum[L - 1] (watch out when L > R or L = 0).

Complexity: O(N²)

C. Street Lamps

If we don't have any asterisk *, then for each 3 dots we need one lamp, so the answer is , where D is the number of dots.

We can solve the problem by creating a copy of the given string, and for each asterisk in the first string we place an asterisk at it's adjacent indices in the second string. So if the given string is ...**.., the second one will be ..****..

After that, we count the number of dots in each block of consecutive dots and find the number of needed lamps for that block.

Complexity: O(N)

D. Alternating Strings

This problem can be solved using dynamic programming.

Let dp[i] be the minimum number of partitions needed for the suffix that starts at i, we try all possible cuts [i...j]. A cut is possible if i = j, or the substring S(i...j) is not alternating and j - i + 1 ≤ K.

dp[s.length()] = 0;
for (int i = s.length() - 1; i >= 0; --i){
	bool isAlter = true;
	dp[i] = 1e9;
	for (int j = i; j - i + 1 <= k && j<s.size(); ++j){
		if (j>i && s[j] == s[j - 1])
			isAlter = false;
		if (i == j || isAlter == false)
			dp[i] = min(dp[i], 1 + dp[j + 1]);
	}
}

Finally, the answer will be dp[0] - 1, because dp[0] represents the number of partitions, not cuts.

Complexity: O(NK)

E. Epic Professor

Let M be the maximum mark of a student, then the maximum possible bonus marks will be 100 - M.

We can find the maximum mark in one loop, and then count the number of students such that Mark_student + 100 - M ≥ 50.

Complexity: O(N)

F. Travelling Salesman

We can greedily keep adding the edges with the minimum length to the graph until we have one component, then the answer is the length of the last added edge.

This can be done using disjoint-sets data structure. The number of components in the graph will decrease by 1 after merging two components.

Note that the answer is the same as the maximum length of an edge in a minimum spanning tree.

Complexity: O(MlogM)

G. Heavy Coins

We need to find the maximum size of a subset such that the sum of it's values sum ≥ S and the minimum value in the subset is greater than sum - S.

Since N is small, we can try all possible subsets recursively, or iteratively using a bitmask.

int res = 0;
for (int mask = 1; mask < (1 << n); ++mask){
	int sum = 0, size = 0, minVal = 1e9;
	for (int i = 0; i<n; ++i)
		if((mask>>i)&1){
			sum += val[i];
			++size;
			minVal = min(minVal, val[i]);
		}
	if (sum >= s && minVal > sum - s)
		res = max(res, size);
}

Complexity: iterative solution O(2^NN), recursive solution O(2^N)

H. Bridges

After removing bridges from the graph, we will have one or more components with no bridges.

Imagine each component as one big node, and connect those big nodes using the removed bridges:

The resulting graph is a tree, each edge in this tree is a bridge in the original graph, we need to remove the maximum possible number of bridges by adding one edge.

Adding an edge between two nodes will remove a number of bridges equal to the number of edges on the unique path between them, so we need to remove the longest path in this tree.

The final answer is the number of bridges in the graph minus the longest path in the tree.

Mapping each component into one node can be done using disjoint-sets. It is possible to solve the problem without actually building the tree, check I_love_Tanya_Romanova's comment.

Complexity: O(N + M)

I. Bahosain and Digits

We can try all possible K, we also try all possible digits D, that is we want to make all digits in the string equal to D.

To check if that's possible, we add the needed value to the first digit to make it equal to D (mod10), we should add the same value to the next K - 1 digits, some contestants did this using segment tree and got TLE.

To do this efficiently, we can keep a variable add that represents the total added value, and an array remove to mark that when we are at index i, we should subtract remove[i] from add, please check the code if that wasn't clear:

int add = 0, remove[251] = {};
for (int i = 0; i + k <= digits.length(); ++i){
	add -= remove[i];
	int curDigit = (digits[i] - '0' + add) % 10;
	int need = (10 - curDigit + D) % 10;
	add += need;
	remove[i + k] = need;
}
// after that we need to check that we won't need more
// operations to make the last K digits equal to D.

Complexity: O(10|digits|²)

J. Candy

Let's create two frequency arrays, one for ages and one for packet sizes, after that we can match ages with packet sizes greedily.

We keep matching the minimum age i with the minimum possible packet size j such that freqAge[i] ≤ freqSize[j]. Note that we can't use sizes less than j after that because the problem says that older students must get more candies.

bool yes = true;
for (int age = 5, size = 1; age <= 15; ++age){
	if(freqAge[age] == 0)
		continue;
	while (size <= 50 && freqAge[age]>freqSize[size])
		++size;
	if (size == 51){
		yes = false;
		break;
	}
	++size;
}

Complexity: O(15 + 50)

K. Runtime Error

Many contestants got runtime error in this problem because of dividing by zero.

We can solve the problem in O(N) using an array that tells us if we have some number or not.

bool have[100001] = {};
int X = 1e9, Y;
for (int val, i = 0; i<n; ++i){
	cin >> val;
	if (val>0 && k%val == 0 && have[k / val]){
		int curX = min(val, k / val);
		int curY = k / curX;
		if (curX<X){
			X = curX;
			Y=curY;
		}
	}
	have[val] = true;
}

There are other solutions that use frequency arrays or binary search. Be careful in case K is a square number like 25 and there is one 5.

Complexity: O(N)

L. Alternating Strings II

Let's go back to the solution of problem D, notice that once the substring is not alternating, it won't be alternating again, so we just choose the minimum value in the range [x, i + k - 1], where x is the first position after i such that S(i...x) is not alternating. In other words, S_x - 1 = S_x.

We can use segment tree to get the minimum value of dp in the required range.

Complexity: O(NlogN)