I'll upload my example solutions and will post links to them as soon as it becomes possible.

Some of the problems editorials contain an additional challenge which is apparently harder to comprehend than the original problem. Feel free to share and discuss your ideas in the comments. =)

465A - inc ARG

If we add 1 to a number, its binary representation changes in a simple way: all the least significant 1's change to 0's, and the single following 0 changes to 1. It suffices to find the length of largest suffix which contains only 1's, suppose its length is l. Then the answer is l + 1 except for the case when all the string consists of 1, when the answer is l.

It is amusing that div1E problem is concerned with addition of 1 to a binary integer as well. =)

465B - Inbox (100500)

Optimal strategy is as follows: for every segment of consecutive 1's open the first letter in segment, scroll until the last letter in segment, if there are more unread letters left, return to list.

It is easy to show that we can not do any better: observe the moment we read the last letter from some segment of consecutive 1's. There are no adjacent unread letters now, so we either have to scroll to some read letter or return to list of letters, either way we make an operation which does not result in reading an unread letter, so every segment (except for the last) must yield at least one such operation.

464A - No to Palindromes!

If string s contains a non-trivial palindromic substring w, then it must contain palindromic substring of length 2 or 3 (for instance, center of w). Therefore the string is tolerable iff no adjacent symbols or symbols at distance 1 are equal.

Now for the lexicographically next tolerable string t. t is greater than s, so they have common prefix of some size (maybe zero) and the next symbol is greater in t than in s. This symbol should be as right as possible to obtain minimal possible t. For some position i we can try to increment s_i and ensure it's not equal to s_i - 1 or s_i - 2. If we find some way to do this, the suffix can always be filled correctly if only p ≥ 3, as at most two symbols are forbidden at every moment. Every symbol from suffix should be as small as possible not to make conflicts. So, a greedy procedure or some kind of clever brute-force can be implemented to solve the problem in O(n). Cases p = 1 or 2 are easy, as only strings of length at most 1, and at most 2 respectively fit.

This is an application on general approach to generate next lexicographical something: try to increment rightmost position so that suffix can be filled up in some way, then fill the suffix in least possible way.

As pointed out in Russian discussion, this problem is a simplified version of the problem from some previous round: 196D - The Next Good String. We were not aware of this and apologize for the misfortune. Luckily, no copied solutions from that problem were spotted. If you enjoyed this simple version, you may want to try the harder one know. =)

464B - Restore Cube

There are several ways to solve this problem. We'll describe the most straightforward one: we can generate all possible permutations of coordinates of every point and for every combination check whether given point configuration form a cube. However, number of configurations can go up to (3!)⁸ > 10⁶, so checking should work quite fast.

One way to check if the points form a cube is such: find minimal distance between all pairs of points, it should be equal to the side length l. Every vertex should have exactly three other points at distance l, and all three edges should be pairwise perpendicular. If these condition are met at every point, then configuration is a cube as there is no way to construct another configuration with these properties. This procedure performs roughly 8² operations for every check, which is fast enough. There are even more efficient ways of cube checking exploiting various properties of cube.

There are various optimizations to ensure you fit into time limit. For instance, applying the same permutation to coordinates of all points keeps every property of the cube, therefore we can fix order of coordinates for one point and permute all other. This single trick speeds up the algorithm 6 times, which allows some less efficient programs to be accepted.

A challenge: apparently, checking may be done as follows: find the length side l, then count number of pairs on distance l, , . A cube must contain exactly 12 pairs of first kind, 12 pairs of second kind and 4 pairs of third kind. Can you prove that this condition is sufficient for configuration to form a cube? Is it true if we allow points to have non-integer coordinates? Can you propose an even easier algorithm for checking?

464C - Substitutes in Number

It is quite diffcult to store the whole string after each query as its length grows exponentially and queries may change it dramatically. The good advice is: if you can't come up with a solution for a problem, try solving it from the other end. =)

Suppose we know for some sequence of queries that digit d will turn into string t_d for every digit. Then string s = d₁... d_n will turn into t_d1 + ... + t_dn (+ for concatenation). Denote v(s) numeric value of s. Then v(s) can be expressed as v(t_dn) + 10^|d_n|(v(t_dn - 1) + 10^{|d_n - 1|}(...)). So v(s) can be computed if we know m_d = v(t_d) and s_d = 10^|t_d| for all d. As we need answer modulo P = 10⁹ + 7 we can store these numbers modulo P.

Now prepend some new query d_i → t_i to given sequence. How will m_d and s_d change? Clearly, for all d ≠ d_i these numbers won't change, and for d_i they can be computed according to the rule above. This recounting is done in O(|t_i|) time. After adding all queries, find answer for s using the same procedure in O(|s|) time. Finally, our time complexity is . The code for this problem pretty much consists of the above formula, so implementation is as easy as it gets once you grasp the idea. =)

Optimized simple solutions which just replaced substrings could manage to pass pretests. Sorry for that.

A challenge: this problem has a natural modification when you have to give an answer after each query. Using algorithm described above it can be solved offline in O(n²) time. Can we do better than this? What if we are limited to answer online?

464D - World of Darkraft - 2

This problem required some skill at probabilities handling, but other than that it's quite simple too.

Denote number of earned coins as X, and number of earned coins from selling items of type i as X_i. Clearly X = X₁ + ... + X_k, and EX = EX₁ + ... + EX_k (here EX is expectation of X). As all types have equal probability of appearance, all X_i are equal, so EX = kEX₁. Now to find EX₁.

If we look only at the items of one type, say, 1, items generation looks like this: with probability we get nothing, and with probability we get out item with level distributed as usual. Denote d_n, t expectation of earned money after killing n monsters if we have an item of level t at the start. Clearly, d_0, t = 0 (we have no opportunity to earn any money), and , which is equal to = . To get the answer note that EX₁ = d_n, 1. The sad note is that this DP has Ω(n²) states, which is too much for .

Maybe if we cut off some extremely-low-probability cases we can do better? For instance, it is clear that probability of upgrading an item descreases with its level, so apparently it does not get very high. We know that expected number of tries before first happening of event with probability p in a series of similar independent events is 1 / p. Therefore, expected number of monsters we have to kill to get item of level T is . So, in common case our level can get up to about , which does not exceed 500 in our limitations. We would want to set such bound B that ignoring cases with t > B would not influence our answer too much. That can be done with rigorous bounding of variance of T and applying some bounding theorem, or with an empirical method: if we increase the bound and the answer doesn't visibly change, then this bound is fine. It turns out B ≥ 700 is good enough for achieving demanded precision. Thus solution with complexity is obtained (here we assert that , and constant C is buried in the big O).

A challenge: suppose we have the same rules of killing monsters and obtaining items, but now we are free to choose whether to sell a new item or an old one. We act so that to maximize our number of coins in the end. What is the expected number of coins if we act optimally?

Now it is sometimes more profitable to sell a powerful item, but sometimes it isn't. How fast a solution can you come up with?

464E - The Classic Problem

This seems to be a simple graph exercise, but the problem is with enormous weights of paths which we need to count and compare with absolute precision to get Dijkstra working. How do we do that?

The fact that every edge weight is a power of two gives an idea that we can store binary representation of path value as it doesn't change much after appending one edge. However, storing representations explicitly for all vertices is too costly: the total number of 1's in them can reach Ω(nd) (d is for maximal x_i), which doesn't fit into memory even with bit compression woodoo magic.

An advanced data structure is needed here which is efficient in both time and memory. The good choice is a persistent segment tree storing bit representation. Persistent segment tree is pretty much like the usual segment tree, except that when we want to change the state of some node we instead create a new node with links to children of old node. This way we have some sort of ''version control'' over tree: every old node is present and available for requests as its subtree can never change. Moreover, all queries are still processed in time, but can create up to new nodes.

What queries do we need? Adding 2^x to binary number can be implemented as finding nearest most significant 0 to x-th bit, setting it to 1 and assigning 0's to all the positions in between. Usual segment tree with lazy propagation can do it, so persistent tree is able to do it as well.

Comparing two numbers can be done as follows: find the most singificant bit which differs in two numbers, then number with 0 in this bit is smaller; if no bits differ, then numbers are clearly equal. That can be done in if we store hashes of some sort in every node and perform a parallel binary search on both trees. Time and memory limits were very generous so you could store as many different hashes as you wanted to avoid collisions.

That concludes the general idea. Now we use this implementation of numbers as a black-box for Dijkstra algorithm. Every operation on numbers is now slowed by a factor of , so our solution has complexity. However, great caution is needed to achieve a practical solution.

First of all, in clueless implementation comparison of two "numbers" may require additional memory as we must perform "push" operation as we descend. memory is too much to fit even in our generous ML. There are plenty of ways to avoid this, for instance, if we want to push the value from node to children, we actually know that the whole segment consists of equal values and can answer the query right away.

I would like to describe a clever trick which optimizes both time and memory greatly and also simplifies implementation. It allows to get rid of lazy propagation completely. Here it comes: initially build two trees containing only 0's and only 1's respectively. Now suppose we want to assign some value (0, for instance) on a segment and some tree node completely lies inside of query segment. Instead of creating a new node with a propagation mark, we can replace the node with corresponding node from tree filled with 0. This way only new nodes are created on every query (which is impossible to achieve with any kind of propagation which would require at least ), and also nodes need to store less information and become lighter this way. Also, no "push" procedure is required now.

No challenges for this problem as it is challenging enough itself. =) Implementing this problem is a great exercise for anyone who wants to become familiar with complicated structures and their applications, so solving it in the archive is advisable.

That's pretty much it. If there are still questions, you may ask them in the comments. Thanks for reading!