486A - Calculating Function

If n is even, then the answer is n / 2, otherwise the answer is (n - 1) / 2 - n =  - (n + 1) / 2.

486B - OR in Matrix

Hint of this problem is presented in its statement. " where is equal to 1 if some a_i = 1, otherwise it is equal to 0."

To solve this problem, do 3 following steps:

1. Assign all a_ij (1 ≤ i ≤ m, 1 ≤ j ≤ n) equals to 1.
2. If some b_ij = 0, then do assignments: a_ik = a_tj = 0 (1 ≤ k ≤ n, 1 ≤ t ≤ m) (that means, assign all elements in row i and column j of matrix a to 0).
3. Then we have matrix a which need to find. Just check whether from matrix a, can we produce matrix b. If not, the answer is obviously "NO".

Complexity: We can implement this algorithm in O(m * n), but it's not neccesary since 1 ≤ m, n ≤ 100.

486C - Palindrome Transformation

Assuming that cursor's position is in the first half of string(i.e 1 ≤ p ≤ n / 2) (if it's not, just reverse the string, and change p to n - p + 1, then the answer will not change).

It is not hard to see that, in optimal solution, we only need to move our cusor in the first half of the string only, and the number of "turn" is at most once.

Therefore, we have below algorithm:

• Find the largest index r before p in the first half of the string (p ≤ r ≤ n / 2) such that s_r different to s_{n - r + 1}. (s_i denote i_th character of our input string s)

• Find the smallest index l after p (1 ≤ l ≤ p) such that s_l different to s_{n - l + 1}.

• In optimal solution, we move our cusor from p to l and then from l to r, or move from p to r and then from r to l. While moving, we also change character of string simultaneously (if needed) (by press up/down arrow keys).

Be careful with some corner case(for example, does'nt exist such l or r discribed above).

Complexity: O(n).

486D - Valid Sets

• Firstly, we solve the case d =  + ∞. In this case, we can forget all a_i since they doesn't play a role anymore. Consider the tree is rooted at node 1. Let F_i be the number of valid sets contain node i and several other nodes in subtree of i ("several" here means 0 or more). We can easily calculate F_i through F_j where j is directed child node of i: . Complexity: O(n).

• General case: d ≥ 0. For each node i, we count the number of valid sets contain node i and some other node j such that a_i ≤ a_j ≤ a_i + d (that means, node i have the smallest value a in the set). How? Start DFS from node i, visit only nodes j such that a_i ≤ a_j ≤ a_i + d. Then all nodes have visited form another tree. Just apply case d =  + ∞ for this new tree. We have to count n times, each time take O(n), so the overall complexity is O(n²). (Be craeful with duplicate counting)

Here is my code.

486E - LIS of Sequence

LIS = Longest increasing subsequence.

Solution 1 (Most of participant's solutions):

• Let F1_i be the length of LIS ending exactly at a_i of sequence {a₁, a₂, ..., a_i} and D1_i is the number of such that LIS.

• Let F2_i be the length of LIS beginning exactly at a_i of sequence {a_i, a_i + 1, ..., a_n} and D2_i is the number of such that LIS.

• // Calculates F1_i and F2_i is familiar task, so I will not dig into this. For those who have'nt known it yet, this link may be useful)

• // We can calculate D1_i and D2_i by using advanced data structure, like BIT or Segment tree.

• l = length of LIS of {a₁, a₂, ..., a_n} = max{F1_i} = max{F2_j}.

• m = number of LIS of {a₁, a₂, ..., a_n} =

• Let C_i be the number of LIS of {a₁, a₂, ..., a_n} that a_i belongs to. Index i must in group:

  1) if C_i = 0

  2) if 0 ≤ C_i < m

  3) if C_i = m

• How to calculate C_i? If (F1_i + F2_i - 1 < l) then C_i = 0, else C_i = D1_i * D2_i. Done!

We have an additional issue. The number of LIS of {a₁, a₂, ..., a_n} maybe very large! D1_i, D2_i and m maybe exceed 64-bits integer. Hence, we need to store D1_i, D2_i and m after modulo some integer number, call it p.

Usually, we will choose p is a prime, like 10⁹ + 7 or 10⁹ + 9. It's not hard to generate a test such that if you choose p = 10⁹ + 7 or p = 10⁹ + 9, your solution will lead to Wrong answer. But I have romeved such that tests, because the data tests is weak, even p is not a prime can pass all tests.

Solution 2:

// Some notation is re-defined.

• Let F1_i be the length of LIS ending exactly at a_i of sequence {a₁, a₂, ..., a_i}.

• Let F2_i be the length of LIS beginning exactly at a_i of sequence {a_i, a_i + 1, ..., a_n}.

• l = length of LIS of {a₁, a₂, ..., a_n} = max{F1_i} = max{F2_j}.

• Let F_i be the length of LIS of sequence {a₁, a₂, ..., a_i - 1, a_i + 1, ..., a_n} (i.e the length of LIS of initial sequence a after removing element a_i).

• Index i must in group:

  1) if F1_i + F2_i - 1 < l, otherwise:

  2) if F_i = l

  3) if F_i = l - 1

• How to caculate F_i? We have: F_i = max{F1_u + F2_v} among 1 ≤ u < i < v ≤ n such that a_u < a_v. From this formula, we can use Segment tree to calculate F_i. Due to limitation of my English, it is really hard to write exactly how. I will post my code soon.

Complexity of both above solution: O(nlogn).

Hello everyone!

Today, there will be another CodeForces Round at 18:00 (Moscow time). It is a Div. 2 contest, but Div. 1 participants can take part out of competition also.

My name is Vuong and this is my very first CodeForces round. Hope that this is not the last one. I would like to thanks Maxim Akhmedov(Zlobober) for help me preparing the round, Maria Belova(Delinur) for translating problems into English, and Mike Mirzayanov(MikeMirzayanov) for such a great Polygon and CodeForces.

Be sure to read all problem statements before contest ended. Hope you enjoy the contest.

Good luck and have fun!

UPD The contest is over! Thanks all of you for participating!

Here is top 5 participants:

1. khykhm110
2. My_First_Lady
3. Perditio
4. AkatsukiPain
5. s_z_l

The editorial can be found here.