Short Editorial of first 4 problems:
Problem 1 — Matrix Game
Greedy solution applies and Matrix has no rolw in the problem. Just consider the numbers and at each moment of time every person tries to take the largest available number. Find the sum they can accumulate after this process and print answer accordingly.
Problem 2 — Stingy Strings
Again greedy solution applies in the sense that we replace all occurences of a given character by its corresponding number or replace none of them. Next part is to modify the cost function as “length — 2*(count of numbers) + (sum of numbers)/k”. Using this, we can say that we replace only those ccharacters with numbers whose value is greater than or equal to 2*k.
Problem 3 — Maze love
Let number of steps taken in each direction be N, S, E, W. So we have following equations:
N — S = m, E — W = n, Na + Sb + Ec + Wd = P
Replace S, W in last equation, we get N * A + E * B = C, where
A = a + b, B = c + d, C = P + mb + nd
The other constraints are N, S, E, W are integers and N >= m, S >= 0 and E >= n, W>= 0.
Solution exists when gcd(A, B) divides C. After this check, we simply brute force over the possible values of N and update answer (i.e. minimum value of N+S+E+W) if present.
Problem 4 — Replace and Substring queries.
Idea is to find the number of substrings with given mask in string B easily. For this, we fix a particular index and find the first point of occurrence of every character on the right and add the corresponding contribution to the mask. For example- In “aabbbbdac” for index 1, “a” occurs at “1”, “b” occurs at “3”, “d” occurs at “7” and “c” occurs at “9”. So number of substring with one endpoint at 1 and having mask 1 are 2, mask 3 are 3, mask 11 are 2 and mask 15 is 1.
One this initial computation is done, we try to handle the queries and updates. For query on string “a”, we just need to find the mask of the substring a[l:r] and this requires to compute if a particular character occurs in a range. With updates on string “a”, this can be easily handled using fenwick tree or segment tree.
To handle updates on string “b”, idea is to first remove contribution of every substring which contains the xth character and then add the contribution back. For finding number of mask of substrings with contain xth character, we see the substring can either end at x, start at x or contain x in the middle. The first 2 are easy to calculate and are similar to the construction by finding first occurrence to the left and right of index x. For the substring which contain “x” in the middle we can visualise them as 2 parts, left and right and their mask being the “OR” of the left and right mask. Thus doing this OR convolution of the left and right masks in naive manner i.e. O(ALPHA**2) we can find their contribution too.
Complexity of precomputation is O(m * ALPHA * log m) and query and update on string “a” is O(ALPHA * logn) and O(log n) while update on string “b” is O(ALPHA * log m + ALPHA**2).
.jpg)
