Codeforces problem notes

C. awoo's Favorite Problem

Key observations: Always expand on observations (observations 4, 5), improve implementation
Observation 1: Position of B matters
Observation 2: B moves back when beside A and moves forward beside C -> A moves forward, C moves backward
Observation 3: Segment of consecutive can be moved if ends of the segment can be moved
Observation 4: A cannot pass C, C cannot pass A -> as long as count(B) is the same for both arrays, the two strings without B should be equal
Observation 5: Leveraging (observation 2), check if A and C are moving in the right directions
Check counts of B are the same
Check if strings without B are equal
Check A and C are moving in the same direction (Constructive algorithms)

B. Promo

Key observations: Look at problems from different angles, finding linearities, DO NOT try overkill algorithms recalled from memory
Observation 1: Range sum queries: overkill, needs tedious implementation
Observation 2: Look back at problem: sorting reveals linearity
Observation 3: Use prefix sums to calculate a segment of the sorted array (proof 1)
Sort array
Convert to 1 based indexing for ease of use
Compute prefix sums
Given a query q with values x and y: return a[n-x+y] - a[n-x]
Proof 1:

Let x[1] … x[n] be the array and we want to find x[i] + x[i+1] + x[i+2] + … + x[j]
By computing prefix sums, p(k) = x[1] + … + x[k]: we get p(j) = x[1] + x[2] + … + x[i] + … + x[j]
Therefore x[i] + … + x[j] = (x[1] + … + x[i] + … + x[j]) - (x[1] + … + x[i-1])
= p(j) - p(i - 1) {O(n) time complexity + O(nlogn) sort}

C. Sum of Substrings

Key observations: Identifying patterns in test cases, then explaining the patterns with proofs, leveraging programming paradigms (greedy), careful with implementation
Observation 1: Greedy problem heuristic, move 1’s to front and back
Observation 2: Back first then front (proof 1, parts 1, 2)
Observation 3: (obs 1) greedy -> choose last 1 from back and first 1 from front
Observation 4: Other numbers do not matter (proof 1, part 3)
Method:

Iterate through string s to get first 1, last 1, number of 1’s
If the cost (n - last - 1) or (first) <= k: k -= cost, swap(first, index 0), swap(last, index n)
Simulate the process

Proof 1:

Part 1:

If s[n] is 1, the maximum value it can contribute to the sum by 1
If s[n] is not 1, the s[i] that is 1 can contribute to the sum by >=10 since s[i+1] will exist

Part 2:

If s[1] is 1, the maximum value it contributes is 10
If s[1] is not 1, the s[i] that is 1 can contribute 11 to the sum, as s[i-1] will exist
To minimize the sum, the first option should be chosen for both parts.

Part 3:

Between s[1] and s[n] each s[i] == 0 in the string will contribute to the sum by zero since sum + 0 = sum
For each s[i] between s[1] and s[n] == 1, s[i+1] will always exist -> s[i]s[i+1] will be >= 10 -> s[i] contributes 10 to the sum from its position.
For each of these s[i], s[i-1]s[i] will also always exist -> s[i] = 1 so it will also contribute 1 to the sum
In total: each s[i], 1 < i < n, will always add 11 to the sum

Characteristics of the Optimal Solution: a technique for finding observations in a problem

Introduction

Some of you smart people out there may find the contents of this blog so obvious, that it does not deserve to be called a "technique." It is just the totally normal thought process that comes across our minds when we try to solve a problem!

However, I often find it useful (and others may relate) to state my thoughts explicitly when trying to conquer a problem, whether I write it down on a sheet of paper, comment it in my code, or just talk out loud like a crazy guy :D. I observe that one of the things that makes a problem-solver better than another (other than practice and knowledge about certain topics/algorithms, of course) is the way of thinking and approaching a problem. So, to make myself a better problem-solver, I sometimes go about thinking about how I think and try to improve this way of thinking generically and generally about any problem. It is, to many great problem-solvers, one of the byproducts of practicing problems a lot that develops implicitly, and stating such byproducts to myself explicitly is very helpful to me in order to speed up my learning process.

In this blog, I will try to explain a technique of thinking that I found recurring and often helpful in facing many problems that may seem daunting to many people at first sight, with an unorganized train of thought. Afterward, I will try to apply this technique to some Codeforces problems I solved that I found considerably not easy to go about when I haven't tried this technique explicitly. It is highly encouraged to try these problems out yourself before reading the solution (I know there are already posted great editorials for the problems, but I wrote the solution in my style in order to cope with the theme of this blog).

Disclaimer: I don't know if someone else posted something similar to this technique on Codeforces or outside Codeforces, and I tried to search but couldn't; that is why I thought of posting it myself.

The technique

A lot of the problems we face involve finding an optimal solution of some kind, e.g. find a subsequence that has minimum * something * or find a graph of an array that satisfies some requirements. The main technique is to think as follows:

Suppose I did find such a solution, what would it look like? what characteristics it would have? Can we toy around with such a solution so that it remains optimal?

From asking ourselves this question and trying to answer it, we are able to come up with very useful observations that help us in finding the solution. Moreover, the important thing is to have the courage to toy around with the solution and often you would try to reduce it while still satisfying the requirements (e.g. if a subsequence has a minimum * something *, can I reduce the number of elements in it so that it still has the minimum * something *?) If you still don't fully comprehend how useful this may be, don't worry; it will be more clear with the problems.

Problem 1: 1592C. Bakry and Partitioning

(Again, it is highly encouraged to try the problem out yourself if you haven't — before proceeding in this blog.)

So, the problem asks us to find a way to partition our tree into a forest, where each tree has the same bitwise XOR value as all the other trees. Let's try to apply our technique here:

Suppose I did find a way to partition my trees into a forest, and now I have a forest containing $$$q$$$ trees with the same bitwise XOR value $$$x$$$, are there any characteristics of these $$$q$$$ trees? Can I toy around with them a bit and reduce the number of trees?

In this problem, it would be useful to toy around with them.

We note that if we have a tree that we partitioned into 2 trees with XOR values $$$a$$$ and $$$b$$$, then it is clear that before partitioning, the whole tree had an XOR value of $$$a \oplus b$$$. That means that the kind of "toying around" we can do here is to merge two trees into one with and XOR their values. Now, let's get back to our optimal solution. If we try to merge two trees that both have an XOR value of $$$x$$$, then the resultant tree has an XOR value $$$x \oplus x = 0$$$ (don't worry, we didn't ruin the optimality of the solution). If we merge one more tree to the resultant tree, the final tree would have an XOR value of $$$x \oplus 0 = x$$$. So, if we have $$$q$$$ trees in our optimal solution, we can reduce them to $$$q - 2$$$ trees, and the solution would still remain optimal. So, if $$$q$$$ is even, we can reduce it to $$$2$$$ and if $$$q$$$ is odd we can reduce it to $$$3$$$. This means that if a solution exists with $$$q$$$ trees, then so does a solution with $$$q \mod 2 + 2$$$ trees, and we only need to check if we can cut one edge or two edges. The remaining part of the problem is some proper handling of the two cases which is irrelevant to this blog (you can check it out in the editorial if it is still a little difficult for you).

Problem 2: 1629D. Peculiar Movie Preferences

We note that if one string is a palindrome, then we are done (if there is a string of length 1, it would automatically be a palindrome, so we would assume that no strings are of length 1). Otherwise, let's apply our technique:

If a palindrome consists of multiple strings, what would they look like? Can I toy around with them a bit?

Now, it is important to note that if a string is a palindrome, then every prefix is also a suffix of the string. So, if we have a palindromic string consisting of strings of lengths 2 and 3, we can toy around with it by fixing the first string and the last string and drop those in between, and the string would still remain palindromic. This reduces the problem to finding two strings that can be concatenated to form a palindrome.

Problem 3: 1366D. Two Divisors

At first sight, the problem would make me scratch my head a while, asking recurrently "how do I find such divisors?". However, I try to apply this technique and ask:

Let's suppose I did find two divisors $$$d_1$$$ and $$$d_2$$$ where $$$\text{gcd}(d_1 + d_2, a_i) = 1$$$, what characteristics can those two divisors have?

Well it's important to note that $$$d_1$$$ and $$$d_2$$$ are divisors of $$$a_i$$$, but if $$$\text{gcd}(d_1 + d_2, a_i) = 1$$$, then for every prime $$$p|a_i$$$, $$$p \not | (d_1 + d_2) \implies p \not | d_1$$$ or $$$p \not | d_2$$$. This means that if there is a prime $$$p$$$ that divides $$$d_1$$$, it can not divide $$$d_2$$$, otherwise $$$\text{gcd}(d_1 + d_2, a_i) \ge p$$$, so we immediately conclude $$$\text{gcd}(d_1, d_2) = 1$$$, which can't happen if $$$a_i$$$ has one prime divisor, so we assume it would have more than one prime divisor.

If we look at such divisors, we note that if a prime $$$p$$$ does not divide both divisors, then it is possible that it may divide their sum (e.g. $$$5 | (2 + 3)$$$). However, if for every prime divisor of $$$a_i$$$, $$$p$$$ divides one of the two divisors and not the other, then we are certain that $$$p$$$ doesn't divide their sum (because if we assume WLOG $$$p | d_1$$$, then $$$d_1 + d_2 \equiv d_2 \pmod{p}$$$). This means we can partition the primes of $$$a_i$$$ into $$$d_1$$$ and $$$d_2$$$, and so each prime would divide one of the divisors and not the other. So, we can solve the problem by taking one prime divisor of $$$a_i$$$, p, that divides $$$a_i$$$ and divide $$$a_i$$$ by it until it's no longer divisible, and check if $$$a_i$$$ still remains more than 1 and if so, we would have our solution. That one prime divisor of $$$a_i$$$ can be found using normal sieve of eratosthenes.

Problem 4: 1343E. Weights Distributing

It can be apparent that we should distribute the weights on our path greedily, with the minimum having the highest priority. The number of edges we need to distribute the weights on has to be minimal, otherwise, we would need to use a new price from the given array. That way, our prices has to distribute on the edges that are on the shortest paths between $$$a$$$ and $$$b$$$ and $$$b$$$ and $$$c$$$, but an important thing to note is that in a graph, there can be multiple shortest paths.

Let's now ask ourselves: what would the shortest paths look like? What characteristics of the shortest path do we need in order to have them include the minimum price possible?

Ok, so the shortest paths can be one straight line from $$$a$$$ to $$$b$$$ and $$$b$$$ to $$$c$$$, that is the two paths $$$a \to b$$$ and $$$b \to c$$$ are not intersecting with only $$$b$$$ as a common node, otherwise, they would intersect in a considerable number of nodes, so our "optimal solution" would include at least one intersection point. We can fix a common node $$$x$$$, and our path would look like $$$a \to x$$$, $$$x \to b$$$, $$$b \to x$$$, then $$$x \to c$$$, with the common edges on the path $$$x \to b$$$ only. So, we would have to distribute the minimal prices on the edges that are on the path from $$$x \to b$$$ and then $$$a \to x$$$ and then $$$x \to c$$$ because our path would have $$$\text{dist}(a,x) + 2\text{dist}(b,x) + \text{dist}(c,x)$$$. So, we would store the shortest paths from $$$a, b,$$$ and $$$c$$$ using some shortest path algorithm like Dijkstra in 3 arrays, and iterate over $$$x$$$ and minimize $$$\text{pref}[\text{dist}(b,x)] + \text{pref}[\text{dist}(a,x) + \text{dist}(b,x) + \text{dist}(c,x)]$$$, where $$$\text{pref}$$$ is a prefix sum array, on the sorted array of prices.

Conclusion

I hope you found these ideas helpful and not a waste of time.

From my naïve perception, the whole of Competitive Programming can be partitioned into pure problem-solving and thinking skills, and techniques/topics/algorithms that one may learn to help him tackle some problems like graphs, Number Theory, DP, ... . The former part, I see, is implicit to most problem solvers and it is just part of their unorganized train of thought that becomes more and more organized with practice. But, I think it can also be structured, and taught. You can consider this blog's content as a technique to have some kind of organization of the train of thought; it's a help in the "pure problem-solving and thinking skills" part, not the topics/algorithms part.

Here are some practice problems:

233B - Non-square Equation
1064D - Labyrinth
1312E - Array Shrinking
1632C - Strange Test
1656B - Subtract Operation
1656D - K-good

Tips on Constructive Algorithms

Constructive algorithms are common in both olympiads and online programming contests. If you’re looking for some examples, filter for "constructive algorithms" in CodeForces's problemset.

Definition

What’s a constructive algorithm, exactly? I think it’s most helpful to give a problem to motivate:

Let $$$1 \leq N \leq 10^5$$$ and $$$1 \leq K \leq log_2(N)$$$ be fixed. Imagine performing a binary search on the values $$$1...N$$$. Give a value X, $$$1 \leq X \leq N$$$ which would be found in exactly K steps using binary search.

There's a bunch of variations on binary search, so assume I chose a particular one in this example.

We’re supposed to generate an example number which satisfies the above condition (found in exactly K steps of a binary search). In almost all constructive algorithm problems, there are many different approaches that all work, and usually any output which satisfies the conditions is accepted.

Usually working out small examples on pen and paper is easy, but it's hard to imagine how solutions can be arrived at programmaticaly for arbitrary $$$N, K$$$.

Furthermore, these problems are usually ad-hoc, so knowledge of data structures and algorithms isn't likely to be of much use. So essentially to solve this problem you need a strong mathematical intuition. The normal strategy for these problems is to manually solve a few small inputs, and try to generalize your thinking process.

If you don’t come from a mathematical background, I can offer some hacky strategies on solving these problems without requiring much creativity on your side...

Strategy

Notice that the conditions in this problem can be tested with a simple script. You shouldn’t worry about complexity on your script, since we’ll only care about small values of $$$N$$$, since we just want to find a good programmatical approach to use for our full solution.

After writing a function which validates whether an answer satisfies the condition, we can create another function which generates all possible answers. The combination of both functions makes a slow brute-force.

This is very valuable -- instead of having to solve examples yourself, you can just use this solution to see what correct answers look like for different parameter values. So time to put on your detective hat, and try to find a pattern in the outputs you see!

Let's say we're testing $$$N=16, 1 \leq K \leq 4$$$ in the problem above

$$$N=16, K=1$$$: only X=8 works.

$$$N=16, K=2$$$: both X=4 and X=12 work.

$$$N=16, K=3$$$: X=2, X=6, X=10, X=14 work.

$$$N=16, K=4$$$: X=1, X=3, ...

Focus on the very first input we get for each $$$K$$$: it's 8, 4, 2, 1! It seems like there’s a pattern that we can use: we start with N and divide by 2 (rounding down) K times. It's instructive to try out other value of $$$N$$$, like $$$17, 24, 1$$$, etc.

Now that we have a pattern, we ought to prove it… In case you are time constrained or have difficulty proving it in the first place, you can use the script: run the brute-force and "smart" approach on as many inputs as you can, and see if they differ. You probably won't be able to test all parameter values, but you'll probably cover enough of the input possibilities that you're pretty likely to get it correct. Even if it does turn out incorrect -- you've gotten a bit of penalty time, but can get right on to testing another approach.

If a problem of this type has a well-hidden pattern, this strategy shines: you can test patterns as fast as you can write them up. If you didn't have this script ready, you would have to execute the algorithm on paper, which is both slower and more error-prone.

A drawback of this approach is that you might spend time writing the script, and learn that there is no easy to figure out pattern. So use your best judgement -- it might be better to switch to another problem.

TODO

C. Dolce Vita

C. Unequal Array

D. Cyclic Rotation

B. Optimal Partition

G. Fall Down

D. Big brush

B. Build the permutation

A. Circular Local MiniMax

Key observations: Application of the peak valley solution, prove all claims, always check if there are more observations before coding, try more efficient implementations
Observation 1: peak valley sorting problem with circular array
Observation 2: If the array has an odd length, it is invalid (proof 1)
Observation 3: two consecutive elements in the answer array cannot be equal: namely a[i], a[n-i+1] once array a is sorted
Method:

Sort the array
Check for odd length
Check for equal consecutive elements a[i], a[n-i+1]
Append sorted elements in order a[0], a[n], a[1], a[n-1], …

Proof 1:

Let a[n] be array with n = 1 (mod 2)
a[0] is a local min, a[1] is a local max, … , a[n] is a local min
a[0] needs to be a local max, but a[0] is a local min, contradiction.

E. Breaking the Wall

Key observations: Clue in question (observation 1). Using both math, visualization and problem solving to reach an observation or solution. E.g. (**, *)
Observation 1: notice that we only have to break 2 walls. Hence, since the damage of the gun for an index i is 1 for i+1 and i-1, and 2 for i, we have 3 options:

(*) Hit a[i], a[i+1] with damages of 1 and 2
(**) Hit a[i-1], a[i+1]
(***) Hit a[i], a[i+x] for some arbitrary 1 < |x| <= n
We need to select 2 positions

Observation 2.1:

For case (***), since a[i] and a[i+x] are disjoint, we sort the array and hit them both with the highest power (2) -> minimum shots = max(ceil(a[0] / 2), ceil(a[1] / 2))
For case (**), we can hit a[i-1] and a[i+1] separately or together -> damage(i, j) = 2, 0 | 0, 2 | 1, 1; To save the most shots, we hit both once until a[i-1] | a[i+1] = 0. Then we finish with (2, 0) or (0, 2) -> we have cost = min(a[i-1], a[i+1]) + ceil(max(a[i-1], a[i+1]) / 2)

Observation 2.2:

For case (*) we can try an equal case where a[i] = a[i+1]
(1) Notice the expressions a[i] - x - 2y, a[i+1] - 2x - y can describe the optimal solution. Since a[i] = a[i+1], we can combine the expressions as (a[i] + a[i+1]) - 3(x + y). Therefore, the total x + y shots = ceil((a[i] + a[i+1]) / 3), which is optimal
How do we make a[i] = a[i+1]? Let a[i] > a[i+1]. When a[i] - 2 and a[i+1] - 1 is applied, the difference between a[i] and a[i+1] decreases by 1 -> in a[i] - a[i+1] moves of (2, 1), the two elements become equal. Then apply (1).

3 loops for each of (n*)
For (***) sort the array
Swap a[i], a[i+1] when necessary in (**, *)
Count min result for each loop

D. A-B-C Sort

Key observations:

Think of how to get to an optimal solution. What must be done to the array to get it sorted? (observation 2)
During a step, what operation is the step performing?
When a problem has multiple steps, use arbitrary notation (e.g. a1, a2, a3) to grasp a sense of what each step does (observation 1)
Find observations on the data after each step (proof 1)
The phrasing of the problem itself could be an observation (observation 4).

Observation 1: express the array as (a) with arbitrary numbers a1 a2 a3 a4 a5. Perform some mapping from step 1 to step 2.
Observation 2: what operations may be performed from step 1 and 2? Notice that you can choose when the array is even.
Observation 3: Two adjacent elements can be swapped except a1 if the length of the array is odd (Proof 1, example 1)
Observation 4: Notice the phrasing of the question: last -> middle -> last. Theoretically, this means that the order of the original array can be preserved (not all elements have to be swapped)
From observations 3 and 4, we can sort the original array, and perform the swap array on elements ai, ai+1 where ai > ai+1 and i % 2 == 0. If the array is odd, start at index 1, else start at index 0
Example 1:

a1, a2, a3 -> (a2, a1, a3 | a3, a2, a1) -> (a2, a3, a1 | a3, a2, a1 | a1, a2, a3 | a3, a2, a1)
Notice how a2 and a3 can be swapped but a1 cannot.

Proof 1:

After step 1, we can construct the array a as an, an-2, an-4, … , an-3, an-1 where ai and ai+1 are interchangeable
If n is even and since we have 2 choices per final move, we have n = 0 (mod 2) elements left -> all adjacent elements ai, ai+1 can be swapped for i = 0 (mod 2)
If n is odd, we have n = 1 (mod 2), and the last chosen element is a1 since the smallest element converges to the center. This element cannot be swapped as there is no other element to swap it with.

C. Line Empire

Key observations:

a problem can be split into smaller subproblems if it has multiple semi-connected variables (observation 1)
try small test cases first, even if none exist in the problem statement.
Think about DP problems as greedy problems. Use topological ordering, try to find a linearity. This problem looks to be DP or bruteforce at first glance.
Look for obvious observations and see if they can be manipulated (observation 2)
Use mathematical proofs or equations or theorems or imagery to spot linearities (proof 1, observation 3, 4)
Tie all observations back to the problem (prefix sums, starts at 0)

Observation 1: the cost for moving a capital and conquering a kingdom is somewhat disjoint and can be calculated separately (dividing a problem into smaller subproblems)
Observation 2: it does not make sense to skip over an unconquered kingdom. (proof 1 https://imgur.com/a/V4ciJPM)
Observation 3: As shown in proof 1, the total cost for a is a * (largest distance moved)
Observation 4: As shown in proof 1, the cost of b can be optimized to b * (x + i) if we conquer every kingdom and then move the capital.
Simulate the cost for b with a prefix sum of c (this is optimal due to proof 1 / observation 2):

Cost_a = a * c[max]
Cost_b1 = b(c[max] - c[max-1]) + … = c[max] - c[0] = c[max]
Cost_b2 = c[max+1] + c[max+2] + … - c[max] - c[max] - … = (total_sum - prefix_sum[max]) - c[max] * (n - max)

Thus the total cost is:

min((a + b) * c[max] + b * (total_sum - prefix_sum[max] - c[max] * (n - max)) for max in 0 … n (inclusive)

Proof 1:

Let cur = current kingdom, x = next kingdom, x + i = kingdom after x
LHS (conquer x first):

Cost_a = a * c + a * (x - c) + a * (x + i - x)

= a * (c + x - c + x + i - x) = a * (x + i)

Cost_b = b * c + b * x + b * x + i = b * (c + x + x + i) OR more optimally b * c + b * (x - c) + b * (x + i - x) = b * (x + i)
Cost_LHS = (a + b) * (x + i)
RHS(conquer x + i first):

Cost_a = a * c + a * (x + i - c) + a * (x + i - x) = a * (c + x + i - c + x + i - x) = a * (x + 2i)
Cost_b = b * (x + i) (or more)

Cost_LHS < Cost_RHS

B. Bit Flipping

Key observations: parts of the answer are in the problem statement, think about the implications of elements in the problem statement (observation 2). Think creatively, utilize learned techniques (observation 1) Reason about the observations (observation 2..1 & 2.2)
Observation 0: Greedy approach, need to optimize left -> right to get larger string
Observation 1: Can the parity of k be exploited? How would the result of an even k differ from an odd k?
Observation 2: How can a flip be simulated? Since a flip has EXACTLY k moves, each bit gets flipped k moves unless it is chosen, in which case it will be flipped k - 1 times
Observation 2.1: From observation 1: if a 1 is flipped an odd amount of moves, 1 -> 0. Therefore, if k is odd, a[i] must be flipped if a[i] = 1. If k is even, a[i] must be flipped if a[i] = 0
Observation 2.2: Since ALL k must be used, the remaining k can be used on a[n-1] since it is the rightmost element in the array
Initialize the array and check the parity of k, following steps in observation 2.1 and 2.2
Then simulate the process by flipping each element ans[i] times, use modulo to speed up

C. Make Equal With Mod

Key observations: Develop observations to solve the problem (observation 2 to observation 3). If there are no constraints on the number of operations, try the easiest approach (observation 1 to observation 2).
Observation 1: the numbers can be made the same by gcd or parity?
Observation 2: each number can be made zero by n = n (mod n) (divide n by itself). Dividing the largest number does not change the other numbers: 2 3 4 -> 2 3 0 -> 2 0 0 -> 0 0 0, or n / (n - 1) = 1 (mod n-1): 1 3 5 -> 1 3 1 -> 1 1 1
Observation 3: the problem arises when there is n, n+1, 1: n = 0 -> 0, 0, 1 || n = 1 -> 1 0 1. This creates an impossible case as the divisor x has to be >= 2
Sort the array
Check if 1 is in array
If so, check for consecutive numbers. If they are found, the array is invalid

C. Shinju and the Lost Permutation

Key observations: in problems with rotations, there can be an “optimal” or “easy” rotation to work with if the number of rotations is equal to the length of P (Similar to Matrix and Shifts). Numbers can be represented in different ways (e.g. towers). Try different representations of numbers that suit the question. Visualize the question. Use the visualization to find observations (e.g. observation 4.x)
Observation 1: P is a permutation, there are n cycles in C, therefore length P = length(c) and P is a permutation from 1 … n
Observation 2: Calculating most starting numbers in P is difficult, except 1, which is always the largest.
Observation 3: C is cyclic as it has the 0 … n-1th cyclic shift. Since we do not need to calculate each value of P, we can rotate the array to any integer i such that arr[0] … arr[i-1] arr[i] … arr[n] -> arr[i] … arr[n] arr[0] … arr[i-1]
By observations 2, 3: P should be rotated to 1
Observation 4: Think of P as towers. One can see all towers from left to right
Observation 4.1: Larger towers can cover smaller towers, total visible towers can decrease arbitrarily. E.g. 1 2 3 4 6 5 -> 5 1 2 3 4 6 (5 -> 2)
Observation 4.2: A tower placed in front increases the number of visible towers by at most 1. The optimal solution to maximize the number of towers is to move the second largest tower in front, then the third … etc. This increases the number of towers by 1; therefore there can only be at most +1 towers every cyclic shift.
Rotate the towers by observation by observation 3
By observation 4, check if P[i+1] - P[i] > 1, if so it is invalid

C. Palindrome Basis

Key observations: modification of existing solution, test cases may not be independent, read the entire question, debug out of bounds quickly, reduce the existing solution given the problem
Observation 1: Variant of integer partitioning problem
Apply integer partitioning dynamic programming solution, then take away all dp[n-i] if i is not a palindrome
Observation 2: There are much less palindromic integers than non-palindromic integers
Modify the algorithm such that a palindrome is taken away each iteration of dp, dp[j - palindrome[i]]
Observation 3: The memo table does not need to be reset after each test case as there are still the same number of ways to make n. This saves time from O(test cases * n * palindromes) to O(n * palindromes)

B. A Perfectly Balanced String?

Key observation: there are multiple ways of solving a problem. Most of the time, the most efficient method can always be deduced. (e.g. observation 4 vs observation 3) String problems usually satisfy this.
Observation 1: A string can only be invalid if between some letter x1 and x2, where x1 = x2, there contains a letter outside the pair that is not inside the pair
Observation 2: Assuming observation 1 is true, after a character i, the character i+1 should either be completely new or exists in a cycle (e.g. abcd, abab)
Observation 3: It is enough to use a counter to check between every x1 and x2, if every number exists between them exactly once. Since there are only 26 possible letters, the time complexity is O(26n)
Observation 4: To satisfy observation 2 more efficiently, use a preserved order set to check if a string is valid, use modulus for cycling to the start

E. Matrix and Shifts

Key observation: (generalized) a cyclic shift requires the array to be read in a different way e.g. diagonally, but the cycling process is almost always unnecessary
Key observation: Since the matrix is n*n = n^2, every possible diagonal can be obtained from the first level of the array, going diagonally a[i][j] a[i+1][j+1] … a[i+x][0] a[i+x+1][1]
Observation: Shifts do not cost money
Therefore, maximize the number of 1’s in a diagonal, keep track of number of ones, and total number of ones
The answer = number of zeroes to be replaced in the diagonal (n - max number of ones in diagonal) + number of ones outside the diagonal (total number of ones -max number of ones in diagonal)
= n + total ones - 2 * number of ones in diagonal

C. Tree Infection

Observation 1: Two nodes are independent if they have different parents, nodes can be grouped
Observation 2: Start by infecting the largest group of nodes, so that they would decrease the most
Simulate the process using a Counter object, tedious implementation
Time is still O(N) for simulation as the sum of the counter is at most N

E. Half Queen Cover

Key observations: More methodical thinking before and during test cases, ask questions, what should an optimal placement look like?
Observation 1: Least intersecting attacking queens
Observation 2: Queens placed 2 across 1 down is optimal
Observation 3: Variation of n-queens, follow n-queens pattern, place queens until reach midpoint, then go back to 2nd column
Total = n/3 + (n+2) / 3
Place queens in order of Observation 2 and 3

D. Vupsen, Pupsen and 0

Key observation: how can small cases be applied to handle a large case? Can small cases be solved independently? (Observation 2) Are there any better ways to manipulate numbers? (Observation 3)
Observation 1: use of -1 to switch array values
Observation 2: lowest common multiples to cancel out pairs
Observation 3: multiply pairs to get 0, a[i] * b[i+1] + a[i+1] * -b[i] (e.g. 1 * -1 + -1 * 1)
Handle last three numbers separately for odd n; always works due to n > 1
Sum is always < 10^9 as the values of sum(b[1 … n]) are equal to sum(a[1 … n])
A[i] is never 0 so b[i] is never 0 for even n
In odd cases, try all combinations of sums c(a + b) + c(-a - b) where a + b != 0

C. Pokemon Array

Similar to peak-valley problem
Iterate 0 … n -> find local max a[i] then find local min a[i+x]
Reset max to min and continue peak finding
Sum up the a[i] - a[i+x] + a[i+y] - a[i+y-z] … until n

C. Odd Even Increments

Obvious observation
Observation: make a[i] using b[i] .. b[n] before making a[i+1] (optimal)
K distinct sorted values so k - 1 switches from value x -> value y
Therefore, you need x / (k - 1) (x switches throughout the whole array, a[] / (k - 1) switches for each array b[]