100540A - Army buddies

Let's restate the problem statement:

• You need to maintain a set of alive soldiers.
• You are asked to perform some queries [L, R]: remove all soldiers with index in range [L, R]. And then find the soldier with maximum index which is still less than L, and the soldier with minimum index which is still greater than R.

The most simple way to implement this is to use C++ set. For each query:

• Find one soldier whose index is in range [L, R].
• Remove that soldier
• Repeat until there is no soldier in range [L, R].

This implementation runs in O(N * logN), because:

• For each soldier, he is only removed once from the set.
• For each query, if we remove k soldiers, we need to do binary search (lower_bound) on the set k+1 times. So the total number of times we binary search is at most N + Q.

Code

100540B - Ball Stacking

Consider the figure in the problem statement. In here we have 4 columns:

• Column 1: 3, -5, -8, 3
• Column 2: 3, 2, 9
• Column 3: -8, -2
• Column 4: 7

Consider a possible configuration of choosing balls.

Let's call the number of balls chosen for at each column x_i, where i = 1..N. In the example, we have:

• x₁ = 4
• x₂ = 3
• x₃ = 0
• x₄ = 0

It is easy to see that x₁ ≥ x₂ ≥ ... ≥ x_N.

From this observation, we have the following DP:

f(j, k) = maximum value, if we consider the first j columns, and at column j, we choose at least k balls.

f(j, k) = max(f(j - 1, k') + a(j, 1) + a(j, 2) + ... + a(j, k)) for k' ≥ k

Code

100540C - Candys Candy

You can read this comment. Thanks terribleimposter

100540D - Diccionario Portunol

To solve this problem, you must first know about trie.

First, construct 2 tries. One for prefixes of Portugese words, and the other for suffixes of Spanish words.

For example, in the first example, the prefix trie for Portugese words will contain:

• m, ma, mai, mais
• g, gr, gra, gran, grand, grande
• un, und, undo.

Note that I intentionally removed the prefix "m" of the 3rd word, because it is repeated.

After building 2 tries, you can see that the answer is "near" (size of trie 1) * (size of trie 2). I said near, because there are some words that were counted more than once, for example: "grande" = "g" + "rande" = "gr" + "ande" = "gra" + "nde" = ...

So you need to find how many words are counted more than once. This can also be solved using the tries we just built.

Let denote by + the string concatenation operation, and let a, b, x, y be strings and w be a character.

Consider Portugese words: a + w + x and b + w + y. We can easily see that for each non-empty string a and y, this word is counted at least twice. To count these duplication, we need to count how many pairs of (x, b) exists for each w. For each character w, this value equals to the number of suffix of Portugese words starts with w, times the number of prefix of Spanish words ends with w.

See my code for more details.

100540E - Electrical Pollution

Let's denote by F(x) the anomalies produced by generator at point(x, x).

I have not solved this, but I have the following idea:

• Create a graph. For each equation of the form: F(x) + F(y) = a, add edge between vertex x and y.
• For each connected component of the graph, choose one vertex z, and represents all F(x) = const - F(z). After doing this, for components with cycles, you should be able to get values of all F(x).
• To answer queries, just use the values of F(x) calcualted above.

Since I haven't implemented this idea, I'm not sure if I've missed something.

100540F - File Retrieval

This problem requires Suffix Array.

First of all, concat all the strings in input, separated by some unique characters (For example, use characters with ASCII code 1 to F).

Build Suffix Array on this string, and calculate LCP array.

Now, to count the number of searchable set, observe the following facts:

• For each searchable set, there's a keyword K for this set.
• This keyword K corresponds to a prefix of a suffix in our Suffix Array.
• It's transparent that the searchable sets have consecutive suffixes in our Suffix Array, where K is their prefixes. Because of this, the corresponding LCP of these will be at least |K|.

So, we can iterate through all searchable set, by iterating through K, but we must do this while keeping the following in mind:

• For each searchable set, there can be more than one K. They can be substring of each other. To avoid duplication, we must store all the searchable sets in a hash table (for example, use C++ set).
• When we iterate, we use Suffix Array. For each position, we consider it as having the smallest value of LCP in our set.

There are some more implementation details, and it is hard to explain everything here. Please refer to code.

Code

100540G - Garden Fence

This should be a sweep line problem. During contest, I've tried rotating the points, but it did not work (probably because the function we're calculating is not continuous, so rotating can not work well?)

100540H - Hedge Mazes

This is a graph theory problem. To solve this problem, you must be familiar with [bridges](http://en.wikipedia.org/wiki/Bridge_(graph_theory) ).

Let's say we need to answer query A B. Find an arbitrary path from A to B. Then, you can see that this path is unique, if and only if all the edges on the path are bridges of the graph. Proving this is a bit tricky, though it is easy to understand why this is correct:

• If one edge on the path is not bridge, you'll be able to construct another path from A to B.
• If all edges on the path are bridges, obviously, you have only one path.

Based on the above observation, you can solve the problem as follows:

• First, remove all edges of the graph which are not bridges.
• Then, use disjoint set (also known as DSU) to maintain the connected components in this new graph.

For each query, you just need to make queries on disjoint set to check if 2 vertices belong to same connected component of the new graph.

My code

100540I - In Braille

This is a straight-forward implementation problem:

• For instruction of type B, just compare the input with each Braille characters to find the corresponding digit.
• For instruction of type S, just print the Braille characters corresponding to each digit in input.

Since the size of input is small, any naive implementation should run in time.

Code

100540J - Jupiter Attacks!

In this problem, you are asked to perform two types of queries:

• Modify one element of array
• Calculate hash value of a subarray.

The most straight-forward way to solve this type of problem, is to use some Data structures that can handle range update & query. I used segment tree. If you are not familiar with it, you can read more here and here or at many other places on the Internet.

In addition to Segment tree, you need to know how to do combine the Hash values of 2 consecutive segments. Let's say you have segment [u, v] and [x, y] where v + 1 = x. If you know hash(u, v) and hash(x, y), you can calculate hash(u, y):

hash(u, y) = hash(u, v) * B^{y - x + 1} + hash(x, y).

You can read my code to see how I implemented this Segment tree.

100540K - Kings Poker

This is again an implementation. Though, you need to handle corner cases very carefully. One downfall is that each number cannot appear more than 4 times. Let's call the 3 numbers in input a, b, and c.

• if a = b = c: Then, if a = 13, there is no solution, otherwise, the optimal solution is set containing three a + 1.

• if a, b, c are pairwise distinct: You can use the smallest pair: 1 1 2. This works because no number can appear more than 4 times.

• The last case is where a, b and c forms a pair. For this case, I used brute-force to check for every pair. If no pair is greater than this pair, this pair must be 13 13 12, and you can use the set 1 1 1.

See my code for more details.

100540L - Gates

L & M solution will be updated if I can solve them.

100540M - Game