A. Replacing Elements
The minimum value that an element can get is the sum of the two smallest elements of the initial array. Constraints allowed to find such pair in $$$O(n^2)$$$ by brute force. One can also sort the array in $$$O(n \log n)$$$ and take
a + a. However, the optimal method to select $$$k$$$ min elements is, of course, a heap with a size limit of $$$k$$$ elements which performs this job in $$$O(n \log k)$$$. We then change every element to this value if such a change reduces it, and compare against the limit.
B. String LCM
We have to print the lcm anyways, so we can just generate it by looping over two string simultaneously with a pair of indices. If lcm exists then its length is the lcm of lengths of the two strings, hence it is relatively short. If we encounter a pair of different symbols while iterating then lcm does not exist and we print -1.
C. No More Inversions
If you swap $$$(i, j)$$$ before the maximum element and $$$(j, i)$$$ after it, then the number of inversions does not change. Moreover, it follows that the number of inversions does not change for any set of numbers that are placed like $$$w,x,\dots,y,z,y,\dots,x,w$$$. Therefore, we can take the permutation $$$1,2\dots,a_n-2,a_n-1$$$, $$$k,k-1,\dots,a_n+1,a_n$$$. Finally, we can't change the first part because it is currently sorted, and any change will lead to more than $$$0$$$ inversions.
The number of different coordinates is the maximum coordinate minus the minimum coordinate plus one (example: there are $$$3-(-2)+1=6$$$ integers in the range $$$[-2,3]$$$). If we exclude all commands from $$$[l, r]$$$, then what remains is a prefix $$$[0,l)$$$ and a suffix $$$(r,n)$$$. It now makes perfect sense to compute max and min on all prefixes and all suffixes, along with the current coordinate after every prefix. From here with the help of some drawings, we can restore min and max as follows:
min = min(prefix_min[left - 1], prefix_current[left - 1] + suffix_current[right] - suffix_max[right]) max = max(prefix_max[left - 1], prefix_current[left - 1] + suffix_current[right] - suffix_min[right])
Here index $$$0$$$ corresponds to the empty prefix/suffix.
E. Minimum Path
Every edge can turn out to be min-, max-, or a regular edge. weight of min-edge is twice the weight of the regular edge, and the weight of max-edge is 0. Each path may use at most one edge as its min-edge and at most one edge as its max-edge (a total of four options, according to the product rule). It follows that we can run Dijkstra on the graph with $$$4n$$$ vertices, but for the answer, we only consider paths that use both min and max-edge (or use neither, which can happen for paths of length 1).
F. Strange Set
It is an interesting problem that can be reduced to maximum flow. UPD: I changed my opinion about Dinic. First, it is not all that hard, and second, I actually had it in my library, I just forgot where it was. Added solution to github
Hello $$$998'244'353$$$ my old friend. It is unlikely that you will implement NTT in half an hour that remains after you solved first six problems, so it is basically impossible unless you have NTT in your library, and hence not a good fit for Div. 2 Round. On the other hand, if you do then the problem is rather straightforward, which makes it not a good fit Div. 1 Round. Therefore we see it in Educational Round, popularizing the idea of NTT among lower-rated participants, and reminding higher-rated ones that they should add it to their library.
Overall, I think that this educational round was very good for the purposes of educating people about standard techniques, and problems were used wisely.