501A - Contest

In this problem one need to determine the number of points for both guys and find out who got more points.

Time complexity: O(1).

501B - Misha and Changing Handles

The problem can be formulated as follows: The directed graph is given, its vertices correspond to users' handles and edges — to requests. It consists of a number of chains, so every vertex ingoing and outgoing degree doesn't exceed one. One need to find number of chains and first and last vertices of every chain. The arcs of this graph can be stored in dictionary(one can use std::map\unoredered_map in C++ and TreeMap\HashMap in Java) with head of the arc as the key and the tail as the value.

Each zero ingoing degree vertex corresponds to unique user as well as first vertex of some chain. We should iterate from such vertices through the arcs while it's possible. Thus we find relation between first and last vertices in the chain as well as relation between the original and the new handle of some user.

You can see my solution for details.

Time complexity: .

504A - Misha and Forest

Note that every non-empty forest has a leaf(vertex of degree 1). Let's remove edges one by one and maintain actual values (degree_v, s_v) as long as graph is not empty. To do so, we can maintain the queue(or stack) of the leaves. On every iteration we dequeue vertex v and remove edge (v, s_v) and update values for vertex s_v: degree_sv -= 1 and s_sv ^= v. If degree of vertex s_v becomes equal to 1, we enqueue it.

When dequeued vertex has zero degree, just ignore it because we have already removed all edges of corresponding tree.

You can see my solution for details.

Time complexity: O(n)

504B - Misha and Permutations Summation

To solve the problem, one need to be able to find the index of given permutation in lexicographical order and permutation by its index. We will store indices in factorial number system. Thus number x is represented as . You can find the rules of the transform here.

To make the transform, you may need to use data structures such as binary search tree or binary indexed tree (for maintaining queries of finding k-th number in the set and finding the amount of numbers less than given one).

So, one need to get indices of the permutations, to sum them modulo n! and make inverse transform. You can read any accepted solution for better understanding.

Time complexity: or .

504C - Misha and Palindrome Degree

Note that if the amount of elements, which number of occurrences is odd, is greater than one, the answer is zero. On the other hand, if array is the palindrome, answer is .

Let's cut equal elements from the end and the beginning of array while it is possible. Let's call remaining array as b and its length as m. We are interested in segments [l, r] which cover some prefix or suffix of b.

We need to find the minimum length of such prefix and suffix. Prefix and suffix can overlap the middle of b and these cases are needed to maintain. To find minimum length you can use binary search or simply iterating over array and storing the amount of every element to the left and right from the current index. Let's call minimum length of prefix as pref and as suf of suffix. So .

Time complexity: O(n) or .

504D - Misha and XOR

Firstly, we convert each number into a binary system: it can be done in O(MAXBITS²), where MAXBITS ≤ 2000 with rather small constant(we store number in system with big radix).

To solve the problem we need to modify Gauss elimination algorithm. For each row we should store set of row's indices which we already XORed this row to get row echelon form (we can store it in bitset), also for each bit i we store index p[i] of row, which lowest set bit is i in row echelon form.

Maintaining the query we try to reset bits from lowest to highest using array p and save information, which rows were XORed with current number. If we can reset whole number, the answer is positive and we know indices of answer. We update array p, otherwise.

Time complexity: O(m × MAXBITS × (MAXBITS + m)) with small constant due to bit compression.

504E - Misha and LCP on Tree

Let's build heavy-light decomposition of given tree and write all strings corresponding to heavy paths one by one in one string T, every path should be written twice: in the direct and reverse order.

Maintaining query we can split paths (a, b) и (c, d) into parts, which completely belongs to some heavy paths. There can be at most such parts. Note that every part corresponds to some substring of T.

Now we only need to find longest common prefix of two substrings in string T. It can be done building suffix array of string T and lcp array. So, we can find longest common prefix of two substring in O(1) constructing rmq sparse table on lcp array.

Time complexity:

For the better understanding see my solution.

P.S. One can uses hashes instead of suffix array.

ADD: There is another approach to solve this problem in but it's rather slow in practice. We can do binary search on answer and use hashes, but we do it for all queries at one time. The only problem is to find k-th vertex on the path, we can do it offline for all queries in O(n + m) time. We run dfs and maintain stack of vertices. See my solution for details.

Hi, Codeforces!

Codeforces Round #285 will be held at 12 January, 12.00 MSK. Problems are authored by me, Evgeny Savinov. This is my first round at Codeforces. I hope that this isn't the last one.

I want to thank sokian and Golovanov399 for help in preparing and testing round, Zlobober for invaluable help in preparing round, AlexFetisov for testing round, Delinur for translating problem statements in English, and of course, MikeMirzayanov for great systems Codeforces and Polygon.

By the way, today(11 January) is MikeMirzayanov's birthday. Happy birthday, Mike!

The round will be for both divisions. Information about score distribution will be posted just before the round starts.

UPD1: Scoring system will be dynamic. Problems will be arranged in ascending expected difficulty order.

UPD2: The editorial can be found here. I'm sorry for the delay.

Hi! I'll try to explain solution of problem E on Codeforces Round #132.

Ok, in the very beginning let's try solve some other task. We'll find the number of such integers in the interval (2^k, x], where . And someone can see that x has length len = k + 1.

Then we should try blocks of {0, 1} to be the same part of periodical number. These blocks have length, which is divisor of len.

Let's calculate number g[i] of such blocks of length i, where i is some divisor of len. We get i of first(from the left side) bits of number x and name it as t = x >> (len - i), e.g. if x = 10011000₂, and i = 4 then t = 1001₂, if i = 2 then t = 10₂. Firstly, we should check block t, it needs for example to check number p = ttttt... repeated times, it can be calculated in a loop p = p << i + t. It's clear if p ≤ x, then we should take into account this block g[i] = 1. It's clear that every correct block less or equal than t, and it should begin from 1 (because of periodical number is without leading zeroes). Case of equality we took. And we should add to g[i] difference between t and 2ⁱ = 10000...₂ i-1 zeroes, g[i] = g[i] + t - (1 << (i - 1)). It seems that all is ready and we can sum g[i] for every divisor of len and not equal len, but we cant. Because some cases we count more than once, e.g. x = 10101100₂, i = 4, g[4] = 1 + (1010₂ - 1000₂) = 3 we considered cases of blocks 1000, 1001, 1010, and when we count for i = 2,g[2] = 1 + (10₂ - 10₂) = 1, we considered one case 10, but 1010 is obtained from 10 repeated two times. But we can easily escape these problems, for this we should substract from g[i] all g[j] where j < i and j divides i.

Some note. We get some DP problem, we calculate g[i] from i = 1 to the most divisor of len which is not equal to len, and update its value by substracting all g[j].

Let us summarize some ideas, we can count number of periodical numbers in the interval (2^k, x], by going through divisors of len and calculating g[i], and then we return sum of g[i] where i < len and i divides len. One can see that 2^k cant be periodical. Given this fact we will calculate this value for x = 2^k - 1, then 2^k - 1 - 1 and so on.In the end we get x = 1, and we get set of non-intersecting intervals, counting on each of them and sum up it we get answer. It can be done recursively. My code in C++, when I also precalculated divisors of each number from 1 to 60. I'm waiting for your replies and some criticism.

Hi, everybody! Recently, I tried to solve a problem. In this problem I had to determine, is number N sum of two squares? i.e. N = a² + b²?, where a and b are integer. N < 10¹⁵. Firstly, I tried to brute-force a and check N - a² for a square, but got TL. Also I tried to factorize the number and check degree of prime divisors p = 4k + 3 and used Fermat-Euler theorem to check the fact. But also I got TL. I suppose this problem to solve with number of operations . And I'm interested in technical realization of it. Can anybody show how to write accurate brute-force or factorization for example on C/C++? And what advices can you give to write same programs, making as less operations as possible? It's the problem from acm.timus.ru link here Thanks in advance!