Eventual
Notice that each operation an even number of each character is removed. If there is a sequence of operations that removes all characters an even number of each character will have been removed. However this could have been done in one step: just remove everything. We just need to check directly if we can erase the entire string
Orthodox
Suppose that OR(l_1,r_1) = OR(l_2,r_2). Then for any range (l,r) which contains (l_1,r_1) it must be the case that OR(l,r) has a 1 in it’s binary representation everywhere OR(l_2,r_2) has a one. I will denote this as OR(l_2,r_2)\subseteq OR(l,r). Now look at OR(1,r_2-1). w.l.o.g we will assume that (l_1,r_2) lies in this range, otherwise we would take OR(l_2+1,N). Now we get the chain A[r_2] = OR(r_2,r_2) \subseteq OR(l_2,r_2)\subseteq OR(l_1,r_1)\subseteq OR(1,r_2-1). From this chain we can conclude that OR(1,r_2-1)=OR(1,r_2).
In short it is sufficient to check that for all i that A[i]\nsubseteq OR(1,i-1).
A mistake I made was not to check for i=1 where OR(1,0)=0
Pathetic
We will use the fact that each integer has a prime decomposition. We only need to consider prime numbers. We need to make sure that for any prime p that any path with p nodes containss at least one value that is divisible by p. We will assign these nodes that are divisble by p using a depth first search. We initialize all values as 1. If the distance from the root is a multiple of p/2 we will multiply the value of that node by p. We don’t do this for the root as otherwise it would become too large. The p/2 is needed to take branches into account, see the sketch below as an example
p=3
O-#
/
O-O-#-O
\
O-#
The left node is the root. O is a root that is not multiplied by p, # is a node that is. We notice that by spacing the depths by 3 we have accidentally created a path of length 3 that contains no multiples of p. Using p/2 as the depth interval solves this problem
Bojack
It took a long time for me to discover a pattern that worked. I ended up with the following pattern:
aba, aabaa, …, a^Dba^D
Let’s count the numer of unique substrings:
All substrings containing the b are unique, because there is only one b. There are (D+1)^2 substrings that contain the b. Furthermore each sequence of 1 to D a’s is a unique substring. Giving us a total number of distinct substrings: D^2+3D+1
Now let’s count the number of palindromes. By the triangle formula we have 2\cdot (\frac12\cdot D\cdot (D+1)) palindromes containing only a’s. Furthermore there are D+1 palindromes containing the b. This gives the total number of palindromes is D^2+2D+1
We notice that the difference between these is D as required
Extreme
This one was fun, but I didn’t complete it in time. It was however accepted in practice. I enjoyed being able to solve the hardest problem in the competition without much trouble.
First of all it is handy to know how to find the length of the longest increasing subsequence. This is often done by a sequence of “stacks” and we add the elements to these stacks one by one. An element is added to the leftmost stack that contains a top value larger than the element. Because the tops of the stacks are always increasing we can do a binary search for the corresponding stack.
The trick is to first build up the longest - decreasing - subsequence (LDS) datastructure of the reverse array, but keep track on when each element was inserted where. Then we construct the normal longest - increasing - subsequence as normal. While we do that we "play the construction of the LDS backwards. If the element being inserted is lower than the LIS size we check the LDS datastructure for the largest value that can complete the subsequence to be a LIS. We can keep inserting until we reach that value, so that value is the best we can do.
Feel free to ask questions about my approaches below. I have only explained problems above that I have solved, so the only-div2 problems are missing.