In the light of the current Russian internet laws obscurantism, an insistent wish to move the site abroad emerged.

Let's try to choose the name you would like most of all:

https://polldaddy.com/poll/7857563/

(I have a weak imagination, so don't bother to suggest your options — you can check them, for instance, here)

UPD Thanks everybody, the poll finished. Results: the winner is e-maxx.io (25%), and the second by popularity is e-maxx.us (16%).

Some days ago I was asked about the problem of finding least common ancestor of two given vertices. Specifically, the task is not to use any preprocessing of the tree, and a single LCA query should be answered in time O(r), where r is the distance between query vertices.

If there are no restrictions on memory usage, then the solution can be seen almost instantly: let's lift up both vertices simultaneously, and mark in two arrays all vertices visited during the first path and during the second path. As soon as we meet a vertex that is visited by both paths — this vertex will be the LCA.

But this solution requires O(n) memory, or, if we use hash-set, O(r) memory.

I started to think, is it possible to solve this problem almost without additional memory, i.e., use O(1) of memory. (Of course, the time complexity should remain the same O(r).)

And it turned out that yes, that's possible. Now I set this nice problem to you. (Possibly this is a known problem? I've never seen it before, though.)

As usual, post your solutions at comments, but hide them under edits, so that one can't read your solution accidentally.

During the yesterday contest we were "lucky" enough to discover a new bug in the g++ (here is the previous bug, which was discussed here some time ago).

The bug becomes apparent in complex recursive functions with -O2 option turned on.

In our case it was a segment tree, and the bug lead to wrong answer even on the sample test case (though without -O2 everything works ok). Interestingly, if we try to add debug output to our program, it started working right :) Of course, these symptoms may signify that it's our bad solution, but, to all appearance, it is not.

So, after the contest I simplified the program, and this is a minimal version of our program to show the bugs: at pastebin.

From debug-outputs we can see, that with -O2 options turned on, the auxillary() function is called twice, returning 1 and 0, but query() in result returns zero, though its result is simply a sum of all results of auxillary() calls.

However, in bugtracker another man managed to create much simpler example: at pastebin.

Link to the bug is here: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48837.

By this moment the bug is confirmed, and also it is confirmed that it exhibits on (!attention!) g++ 4.3.3 - 4.6.0.

So, all versions of GCC by the last 2.5 years. Hmm....

P.S. During our trainings we meet with such strange behaviour of g++ compiler, but usually we didn't take it into account - maybe it's a wrong solution, and it's just a luck that it passed on MS VC. But it turned out that everything is not so simple, and we should take into account the factor of bad compilers.

P.P.S. There will be the same g++ compiler on the ACM ICPC finals...

The most important step on the way to solve this problem - is to understand that it's enough to consider only such rotations of the polygon, that one of its sides lies on the side of the room.

Let's try to understand this fact. Suppose that the fact is wrong, and there exists such a position of vacuum cleaner, that neither of its sides lies on the side of the room. Denote as i and j the numbers of vertices that lie on the room sides. It's easy to understand that the polygon form between vertices i and j doesn't make any sense itself: for each rotation we can see that from the area of triangle OP[i]P[j] some constant area is subtracted, while the concrete value of this constant depends on the polygon form.

That's why we see that the polygon form doesn't influence on anything (if we have fixed numbers i and j), and we have just to minimize the area of right-angled triangle OP[i]P[j]. But, taking into account that its hypotenuse is a constant, it's easy to see that the minimum is reached in borderline cases: i.e. when one of the polygon sides lies on the room side.

So, we've proved the fact. Then we have to invent fast enough solution. We have already obtained an O(n²) solution: iterate over all sides of the polygon (i.e. iterating over all possible i), mentally push it to one side of the room, then find the threshold point j, then calculate answer for given i and j. Let's learn how to do these both things in O(1).

In order to do the first thing (finding j) we can use a method of moving pointer: if we iterate over i in the same order as in the input file, then we can just maintain the right value of j (i.e. when we move from i to i + 1 we have to increase j several times, while it is getting further and further).

In order to do the second thing (the area calculation) we have to do some precalculation. For example, we can find the mass center Q of the vacuum cleaner, and pre-calculate all partial sums S[i] - sums of all triangles QP[j - 1]P[j] for all j ≤ i. After this precalculation we can get the answer for every i and j in O(1) as a combination of difference of two values from S[] and two triangles' areas: QP[i]P[j] and OP[i]P[j].

I invite to this round all schoolchildren who have just returned from their training camp "LKSH.Winter" - not to give their brains an excess respite, and all students - to distract from all the troubles caused by such a fearful phenomenon as the Examinations :)

The contest is over, congratulations for the winner - RAVEman!

Problem editorials:

• problem C
• problem D
• problem E

• Russian Statements in PDF
• English Statements in PDF

The problems in this round will be five stories from a life of one Hedgehog (don't be surprised - hedgehogs are my loved creatures :) ).

Welcome all to the next Codeforces Format round!

In this round I will replace Artem Rakhov in his usual role of contest administrator: Artem have set out to America to take part in TopCoder Open Algorithm onsite. Good luck, Artem!

The contest has ended, results.

User a4461497 has won the contest, while among first-division users - kuniavski was the first who solved all 5 problems.

Tutorial for problem "B. Codeforces World Finals"

To solve this problem we had to learn how to check the given date XD.XM.XY for correctness (taking into account number of days in each month, leap years, and so on). After implementing this, we had just to iterate over all 6 possible permutations of three given numbers (BD,BM,BY), checking each of them for correctness as a date, and comparing it with the date of Codeforces World Finals DD.MM.YY. The comparison itself could be done, by simply adding 18 to the year number, and comparing the two dates as a triple (year,month,day).

The only difficult case is the case of February, 29-th. It's easy to understand that the solution described above works correctly, if we suppose that this unlucky man (having its birthday on February 29-th) celebrates his birthday on March, 1st in 3/4 years. Interesting question - what do people usually do in this situation in the real life? :)

Tutorial for problem "D. Kings Problem?"

In this problem to create a wright solution you need to perform the following chain of inferences (though, if you skip some steps or do them not completely, you can still get an AC solution :) ):

• Note that after we visit the city numbered n + 1, the further answer depends only from the leftmost and the rightmost unvisited cities (and it would be optimal to come to the nearest to n + 1-th city of them, and the come to another of them). That's why we know the answer for the case k = n + 1, and won't consider this case later.
• Before we visit the n + 1-th city, - this part of the path covers some segment of cities lying in the OX axis. This segment, obviously, contains the point k. But we can't iterate over all such possible segments, because there are O(n²) of them, so it's still a slow solution.
• Let's understand the following fact: if before visiting city n + 1 we visited some other cities, but neither the leftmost nor the rightmost, then it was surely unprofitable. Really, after we come into the n + 1, the answer will depend only on the leftmost and the rightmost of non-visited cities. So, if before the n + 1-th city we performed some movements, but didn't change the leftmost and the rightmost cities, then it was completely unnecessary and unprofitable action.
• We can can get even more: there is no optimal solution, where we should move from the start city k to the n + 1-th city directly, without vithout visiting other cities (here I suppose that k is neither the leftmost nor the rightmost city). Btw, this step of reasoning could be skipped - we can believe it's sometimes profitable to come from k to n + 1 directly, and it's not difficult to support this case in a solution we'll build later; but in order to describe the problem completely let's prove this fact too. In order to prove this, let's write down two formulas: first for the length of the answer if we come from k to n + 1 directly, then come to city 1, and then to city n (here I suppose that 1 and n are the leftmost and the rightmost cities, accordingly, and city 1 is nearer to n + 1 than n); second formula - for the length of the answer if we come from k to 1 first, then to n + 1, then to k + 1, and then to n. If we compare these two formulas, then after the cancellation of like terms we can use the triangle's inequality to see that the second formula always gives smaller value (at least, not greater) than the first. So, it's really unprofitable to come from k to n + 1 directly.
• So, to make a right solution, it's enough to iterate over only two types of segments: [1;i] for i ≥ k, and [i;n] for i ≤ k (here I suppose for convenience that cities are sorted by their x-coordinate).
• The last idea is how to process each of these cases accurately. In order to do this we iterate over all possible i = 1... n. Let, for example, i ≤ k. Then we have to try the following case: go from k to n, then return to i, then come to n + 1, and then return back to the OX axis if need (if i > 1). Also it is required to check another type of cases: try to go from k to i, then to n, and then come to n + 1, and return back to the OX axis if need. Answer for each of these cases can be calculated in O(1). For i ≥ k everything is symmetric.

So, not taking into account the sorting of the citites in the beginning of the program, we get a O(n)-solution.

Tutorial for problem "A. Accounting"

First solution: naive brute

Let's brute all possible values of X, and check each of them. It's easy to understand, that X will be constrained in the same limits as values A and B, that is, from -1000 to 1000 inclusive (obviously, there exists a test for each such X, so we can't decrease these limits).

When we have some fixed value of X, we check it simply by multiplying A by X n times. But, you should be careful with possible integer (and even 64-bit integer :) ) overflow. For example, you should stop multiplying by X if the currect result exceeds 1000 by absolute value already.

Second solution: formula

It's easy to note, that if solution exists, then it is n-th root from |B| / |A| fraction, with changed sign if A and B have different signs and if n is odd (if n is even, then no solution exists). That's why we could just use pow() function (or some analog in your language) to calculate 1 / n-th power of the fraction, and after that we just have to check - is the result integer number or not. Of course, we have to check it with taking into account precision errors: that is, number is integer if it is within 10^- 9 (or some another number) from nearest integer.

Moreover, in this solution you should be careful with zeroes. The worst case is when A = 0, and this case should be checked manually (you should note the difference between B = 0 and B ≠ 0 cases).

It should be told that many of the solutions failed on tests with A = 0, or B = 0, and if these tests were not included in the pretestset, I think, about half of participants would fail to solve this problem :)

Tutorial for problem "E. Tricky and Clever Password"

Scheme of the author solution

The author solution has the following scheme. Let's brute over each possible position pos of the center of the middle part (the part that must be palindrome by problem statement). Then let's take as a middle the maximum palindrome among all centered in the position pos. After that we have to take as prefix and suffix such maximum-sized substrings, which satisfy all problem constraints, and don't intersect with medium part.

After we do these calculations for each possible position pos, the answer to the problem will be just maximum among answers found on each step.

Efficient Implementation

In fact, the problem consists of two sub-problems:

First, it's a search for a maximum-length palindrome, having its center in the given position pos. We can calculate these answers in O(n) with Manacher's algorithm, which is described on my site (unfortunately, the article is only in Russian, so you have to use Google Translator or something like this). Alternatively you can calculate this "palindromic array" using binary search and, for example, hashes or suffix array: let's search for maximum palindrome length using binary search, then inside the binary search we have to compare for equivalence two substrings of the given string, which can be done in O(1) using hashes or calculated suffix array.

Second, it's a search for maximum length and corresponding positions for prefix and suffix parts, not intersecting the given substring [l;r]. Let's look at lengths sufflen of suffix suffix in order of their increase, then for each fixed sufflen obviously it is the best to look only at first occurence of string prefix = reverse(suffix). Thereby, by increasing the length sufflen, we can move the corresponding prefix only to the right, not to the left. Designating by lpos[sufflen] the position of first occurence of string reverse(suffix(sufflen)) in the given string, we get that these lpos values are non-decreasing. It will be more comfortable to introduce another array rpos[len] = lpos[len] + len - 1 - end-position of occurence of this suffix (obviously these values will strictly increase).

So, if we knew the values of the array lpos (or, more convenient, of the array rpos), then in the main solution (in the place, where after selecting maximum in pos palindrome we have to search for maximum appropriate prefix and suffix) we can use binary search over the length sufflen. Moreover, we can just precalculate answers to each of query of this form, and after that we'll answer to each query in O(1).

The last thing is to learn how to build lpos array - array of positions of first occurences of reversed suffixes.

For example, this can be done using hashes or suffix array. If we've calculated the value lpos[k], let's learn how to calculate lpos[k + 1]. If the substring s.substr(lpos[k], k + 1) equals to s-th suffix of length k + 1, then lpos[k + 1] = lpos[k]. In the other case, we try to increase lpos[k + 1] by one, and again do the comparison, and so on. Comparison of any two substrings can be done in O(1) using hashes or suffix array. Of course, total time to build lpos array will be then O(n) - because there won't be more than n increases (and string comparisons) during the whole algorithm.

Another approach to building lpos array is to use prefixe-function. For this, let's make a string reverse(s) + # + s, and if in some point of the right half of the string the value of the prefix function equaled to k, then let's assign lpos[k] =  this position (if, of course, this lpos[k] haven't yet been assigned before - because we have to find only first occurences).

Finally, it's rather easy to get O(n) solution of this problem using rather famous approaches: hashes, suffix array, prefix-function and palindromic array. -solution is somewhat easier, - it is based on binary search (for building palindromic array and for answering the queries) and, for example, hashes (for comparison of two substrings).

Proof

The only non-obvious thing is why after we've fixed the position pos (we remind it's a position of middle of central part of middle), - after that we can greedily take the maximum palindrome with center in it.

Let's suppose the contrary: suppose it was better not to take the maximum palindrome centered in pos, but to take some smaller palindrome centered here. Look what happens when we decrease a length of palindrome by two (by one from each end): we loose two symbols in middle, but instead we get more "freedom" for prefix and suffix parts. But for both of them their freedom increased only by one: prefix gained one symbol after the end, and suffix - one symbol before this beginning. So, taking into account the monotonic increase of rpos, we see that prefix and suffix could increase only by one, not more. Summarizing this discussion, we can say that after decreasing the middle part we loose two symbols, and gain maximum two symbols. That's why there is no need in decreasing the middle part, we can always select it as the maximum-sized palindrome.

Another approach

Let's iterate over each suffix length, and after we've fixed some suffix length, we have to find maximum-sized palindrome between the suffix and the found prefix (position of the prefix still has to be found, just like in the previous solution).

First idea is to use some greedy (similar to described above): take maximum-sized palindrome with center between prefix and suffix, and "cut" it down, in order to fit between the prefix and suffix. It's wrong: there are tests, where after cutting the maximum palindrome becomes very small, so after cutting down it's better to choose another palindrome.

But we can cope with this using the following approach: let's find the length of middle part using binary search. To do this, we have to answer the following queries: "is there a palindrome of length at least x among all palindromes centered between l and r". I.e. given x, we should answer, is there a number greater that or equal to x in the segment [l + x;r - x] (I suppose that x is a half of the length of palindrome).

We can answer to these maximum queries using segment tree in , so the total solution is . Alternatively we can use sparse-table to reach asymptotics (sparse-table is a table where for each position i and power of two j the answer for segment [i;i + j - 1] is precalculated).

This can be done using segment tree, built over the palindromic array (the palindromic array should be calculated, as described in the previous solution).

Today's contest was prepared by Saratov SU 2 team (Maxim Ivanov, Artem Rakhov, Nickolay Kuznetsov).

You will be asked to solve five easy and not so easy problems for some King, whom you hardly heard anything before. The king hopes that the problems won't turn out very difficult to you, and he will have a wide choice among different solutions to each of the problems.

UPD. The contest has finished, thanks to all of you.

The Results table.

Greeting to rng_58 for his win in today's round!

Problem tutorials: A, B, C, D, E.