Author: BekzhanKassenov
This problem asked to determine whose chess position is better.
Solution: Iterate over the board and count scores of both player. Then just output the answer.
Complexity: O(n2), where n is the length of the side of the board (8 here)
Code: 10083191
Author: ADJA
In this problem you were given three arrays. Second array is the same as the first array without one element, third array is the same as second array without first element. You were asked to find deleted elements.
Solution: I'll describe easiest solution for this problem: Let's denote a as sum of all elements of first array, b as sum of all elements of second array and c as sum of all elements of third array. Then answer is a - b and b - c
There are also some other solutions for this problem which use map, xor, etc.
Complexity: O(N)
Code: 10083248
Author: ADJA
In this problem we should split n experienced participants and m newbies into teams.
Solution: Let's denote number teams with 2 experienced partisipants and 1 new participant as type1 and teams with 1 experienced participant and 2 new participants as type2. Let's fix number of teams of type1 and denote it as i. Their amount is not grater than m. Then number of teams of type2 is min(m - 2 * i, n - i). Check all possible i' and update answer.
Complexity: O(N)
Code: 10083265
Author: ADJA
In this problem you were asked to find number of substrings of given string, such that each substring starts and finishes with one and the same letter and sum of weight of letters of that substring without first and last letter is zero.
Solution: Let's denote sum[i] as sum of weights of first i letters. Create 26 map < longlong, int > 's, 1 for each letter. Suppose we are on position number i and current character's map is m. Then add m[sum[i - 1]] to the answer and add sum[i] to the m.
Complexity: O(NlogN), where N — the length of input string.
Code: 10083293
Author: BekzhanKassenov
In this problem we have to answer to the following queries on tree: for given pairs of vertices your program should output number of eqidistand vertices from them.
Let's denote:
dist(a, b) as distance between vertices a and b.
LCA(a, b) as lowest common ancestor of vertices a and b.
depth[a] as distance between root of the tree and vertex a.
size[a] as size of subtree of vertex a.
On each picture green nodes are equidistant nodes, blue nodes — nodes from query.
Preprocessing: Read edges of tree and build data structure for LCA (it is more convenient to use binary raise, becase we will use it further for other purposes).
Complexity: O(NlogN)
Queries:
We have to consider several cases for each query:
1) a = b. In that case answer is n.
2) dist(a, b) is odd. Then answer is 0.
3) dist(a, l) = dist(b, l), where l = LCA(a, b).
Find children of l, which are ancestors of a and b (let's denote them as aa and bb). Answer will be n - size[aa] - size[bb].
4) All other cases.
Assume that depth[a] > depth[b]. Then using binary raise find dist(a, b) / 2-th ancestor of a (let's denote it as p1), dist(a, b) / 2 - 1-th ancestor of vertex a (denote it as p2). Answer will be size[p1] - size[p2].
Complexity: O(logN) for each query, O(MlogN) for all queries.
Resulting complexity:: O(MlogN + NlogN)
Code: 10083310