### laoriu's blog

By laoriu, 5 years ago, ,

486A - Подсчёт функции

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

486B - OR в матрице

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

To solve this problem, do 3 following steps:

1. Assign all aij (1 ≤ i ≤ m, 1 ≤ j ≤ n) equals to 1.
2. If some bij = 0, then do assignments: aik = atj = 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 - Преобразование в палиндром

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 sr different to sn - r + 1. (si denote ith character of our input string s)

• Find the smallest index l after p (1 ≤ l ≤ p) such that sl different to sn - 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 - Допустимые множества

• Firstly, we solve the case d =  + ∞. In this case, we can forget all ai since they doesn't play a role anymore. Consider the tree is rooted at node 1. Let Fi 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 Fi through Fj 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 ai ≤ aj ≤ ai + 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 ai ≤ aj ≤ ai + 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(n2). (Be craeful with duplicate counting)

Here is my code.

486E - Наибольшие возрастающие подпоследовательности

LIS = Longest increasing subsequence.

#### Solution 1 (Most of participant's solutions):

• Let F1i be the length of LIS ending exactly at ai of sequence {a1, a2, ..., ai} and D1i is the number of such that LIS.
• Let F2i be the length of LIS beginning exactly at ai of sequence {ai, ai + 1, ..., an} and D2i is the number of such that LIS.
• // Calculates F1i and F2i 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 D1i and D2i by using advanced data structure, like BIT or Segment tree.

• l = length of LIS of {a1, a2, ..., an} = max{F1i} = max{F2j}.

• m = number of LIS of {a1, a2, ..., an} =

• Let Ci be the number of LIS of {a1, a2, ..., an} that ai belongs to. Index i must in group:

1) if Ci = 0

2) if 0 ≤ Ci < m

3) if Ci = m

• How to calculate Ci? If (F1i + F2i - 1 < l) then Ci = 0, else Ci = D1i * D2i. Done!

We have an additional issue. The number of LIS of {a1, a2, ..., an} maybe very large! D1i, D2i and m maybe exceed 64-bits integer. Hence, we need to store D1i, D2i and m after modulo some integer number, call it p.

Usually, we will choose p is a prime, like 109 + 7 or 109 + 9. It's not hard to generate a test such that if you choose p = 109 + 7 or p = 109 + 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 F1i be the length of LIS ending exactly at ai of sequence {a1, a2, ..., ai}.

• Let F2i be the length of LIS beginning exactly at ai of sequence {ai, ai + 1, ..., an}.

• l = length of LIS of {a1, a2, ..., an} = max{F1i} = max{F2j}.

• Let Fi be the length of LIS of sequence {a1, a2, ..., ai - 1, ai + 1, ..., an} (i.e the length of LIS of initial sequence a after removing element ai).

• Index i must in group:

1) if F1i + F2i - 1 < l, otherwise:

2) if Fi = l

3) if Fi = l - 1

• How to caculate Fi? We have: Fi = max{F1u + F2v} among 1 ≤ u < i < v ≤ n such that au < av. From this formula, we can use Segment tree to calculate Fi. 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).

• +94

 » 5 years ago, # |   +3 Really quick editorial! Thank you. The problems are very interesting :)
•  » » 5 years ago, # ^ |   -27 Are you talking about quick sort ? i think merge sort is faster ./* */it seems to be easy to prepare such a quick editorial for that easy problems.
•  » » » 5 years ago, # ^ |   +13 Yeah.It was so easy, so you solved 2 problems? Do not comment other's work if you are not able to do something like this.I can bet you won't host a codeforces round in your miserable life.
 » 5 years ago, # |   +11 There're too many unrated contestant in the top, I think they come from Div1, that make my rank low :(
•  » » 5 years ago, # ^ |   0 As you say; they were UNRATED.
•  » » 5 years ago, # ^ |   -13 do you mean topological sort by "top" ?
 » 5 years ago, # | ← Rev. 6 →   0 I'm trying my code about problem C(failed to submit it on time to be rated for it though) on cofeforces.com but the result my file produces on the website and the result it produces on my computer is VERY different, while on my computer it shows the right result(trying the example at the problem page, and the result is 6), but the same code at codeforces.com gives me a huge, riddiculous number which is 272695054. I don't know there else to look at(I'm new here) can you help me? Submission:8662047 GCC compiler version: Ubuntu 4.8.2-19ubuntu1
•  » » 5 years ago, # ^ |   0 I found that the problem was about the scanning, fixed this and other error and now it runs flawlessly, took me more than 3 hours to do this though(runtime errors everywhere), I wonder how can you guys be so fast...
 » 5 years ago, # | ← Rev. 3 →   +47 Here is one more solution for E. It looks like your first solution but is easier and deterministic. First, calculate F1i and F2i for all i. Obviously, if F1i + F2i - 1 ≠ l than answer for i is 1, otherwise it is 2 or 3.Then, assume there are two elements i and j with answer different from 1 such that F1i = F1j. You can prove that in this case you can replace i-th element with j-th one in any LIS containing i-th element. Thus the answer for i is 2 (and for j it is 2 too, of course). It can also be shown that if F1i is unique among all F1 then the answer for i is 3.So the algorithm is the following: if F1i + F2i - 1 ≠ l then the answer for i is 1 else if F1i is unique (among positions where we didn't assign 1 yet) then the answer for i is 3 otherwise the answer for i is 2
•  » » 5 years ago, # ^ |   +9 What about this case: a = {1, 3, 4, 2} => F1 = {1, 2, 3, 2}. We have F2 = F4 (this is 1-based indexing), but in fact, the answer for index 2 is 3, the answer for index 4 is 2.
•  » » » 5 years ago, # ^ |   +10 If F1i + F2i - 1 ≠ l then we ignore this number in latter computations. And in your example the answer for index 4 is 1 because the only LIS is {1, 3, 4}.
•  » » » » 5 years ago, # ^ |   +4 Oh, I get it! What a great and simple solution! Thanks!
•  » » » » 5 years ago, # ^ |   -31 do you mean "computational geometry" with "latter computations" ?
•  » » » » » 5 years ago, # ^ |   +32 Do you mean "a stupid joke" by posting stupid jokes?
•  » » 5 years ago, # ^ |   +3 Such an elegant solution. :)
•  » » 5 years ago, # ^ |   +13 To check for 3-rd type we can construct first and last (lexicographically) sequences of maximum length and elements in intersection will have 3-rd type. They easy built from F1 and F2.
•  » » 5 years ago, # ^ |   0 You have written "you can replace i-th element with j-th one in any LIS containing i-th element" but in case of [4, 5, 2, 3, 8] here f1[2] = f1[4] = f2[2] = f2[4] = 2 and f1[2]+f2[2]-1==3 but here we cant replace 5 with 3 in LIS [4 5 8] and neither 3 with 5 in [2 3 8]
•  » » 5 years ago, # ^ |   0 Thanks!!! Amazing solution. Very simple and fast.
•  » » 5 years ago, # ^ |   0 I didn't guess why we always can replace i-th element with j-th, but still I have an idea to show that if F1i = F1j then answer for i and j is 2. Let me write it here: suppose answer for i and j is 3, this means that they both participate in every LIS, now suppose ai < aj then this would mean that F1j = F1i + (# elements between them + 1) so these two values can't be equal. For ai > aj there is the same logic. I think I didn't got anything wrong here.
•  » » 3 years ago, # ^ |   0 Thanku so much sir
•  » » 4 months ago, # ^ |   0 Very simple and elegant solution. Thanks !
 » 5 years ago, # |   +5 waiting for D solution. :D
 » 5 years ago, # |   +15 My solution for problem D. http://pastie.org/9712317
•  » » 5 years ago, # ^ |   0 Was your solution successful? I did the same stuff, it works fine on the samples, but fails on 5th test. Any ideas why could that be?
•  » » 4 years ago, # ^ |   0 is it possible to do string matching with graphs?
 » 5 years ago, # | ← Rev. 2 →   0 2 things about problem B:1) assign all elements in row i and column j of matrix a to 0, not to 1 (typo);2) what is the n*m solution?Despite this, thank you for a very interesting round:)
•  » » 5 years ago, # ^ |   0 1) Thanks! Fixed!2) We can use additional array. For example: Ri = 0 means that we assign all elements of row i of matrix a to 0, otherwise Ri = 1; Cj = 0 means that we assign all elements of column j of matrix a to 0, otherwise Cj = 1. Then bij = Ri OR Cj.
•  » » 5 years ago, # ^ |   0 We can assign all elements in matrix A initially to 1.Then keep substituting the rows/columns of A where the same row/column in B has atleast 1 zero.This will create the A matrix and then check if it can form A. P.S.: I would also like to know the O(n*m) solution.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +8 2) n*m solution can be done by simply keeping markers on which rows/columns you must mark with zeroes and then keeping track of which rows/columns are fully zeroed. However O(n*m*(n+m)) still works fine.
•  » » 5 years ago, # ^ |   -12 do you mean "matrix exponantiation" with matrix ? if yes , press 8.
 » 5 years ago, # |   +11 Here's my deterministic and simple solution for E.F1i + F2i -1 =/= l ===> the answer for i is 1Now how to make difference between 2 and 3? Well if some i is of type 2, it means that removing it will leave some existing subsequence of length l. Let's find the elements in that optimal subsequence (after removal of Ai) that Ai lies between. Suppose those two are Ak and Ap, k=Ai or Ap<=Ai.From this the following follows to be true:If there is some Ak such that k=Ai and (F1k+F2k-1)=l, then i is of type 2. Similarly, if there is some Ap such that p>i, Ap<=Ai and (F1p+F2p-1)=l, then i is of type 2.Both can be checked in O(NlogN) with segment tree.
•  » » 5 years ago, # ^ |   0 Nice!
•  » » 5 years ago, # ^ |   0 for type 2 or 3 checking.Lets ignore all those "nodes" that never belong to the LIS. Use a map "ma" for counting the number of different nodes i that have F1i. that is:for(i = 0; i < n; i++){ if(res[i] == '1') continue; ma[f1[i]]++; }then, for every i check if ma[f1[i]] == 1. If it is true, every LIS in the array will have that node in the sequence at that level. Sorry about my english.
•  » » 5 years ago, # ^ |   +8 Very nice solution ! :D Also note that all the processes described by you can be done just using binary indexed trees. ( http://codeforces.com/contest/486/submission/8697188 )
•  » » » 5 years ago, # ^ |   0 Anything done with BIT can be done with segment tree...8676667
•  » » » » 5 years ago, # ^ |   0 But not everything done using segment tree can be done using BIT :P
 » 5 years ago, # |   +1 Editorials should have contain bit more details. Overall...thank you. :)
•  » » 5 years ago, # ^ |   -34 do you mean binary indexed tree with "bit" ?
 » 5 years ago, # |   0 here is a solution for E without segment tree or BIT: 8657105
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Hi,Could you please explain how your solution works?I am unable to completely understand it but it looks nice.Thanks.
•  » » » 5 years ago, # ^ |   0 You can look at Exercise 15-4.6 in Cormen "Introduction to Algorithms" book.
•  » » » » 5 years ago, # ^ |   0 Thanks, but I I finally understood the solution. :P
•  » » 5 years ago, # ^ |   0 I did the same solution. I recommend use std::lower_bound\std::upper_bound to do a binary search over a sorted range. 8763721
 » 5 years ago, # |   0 Could you explain the main idea of the solution D, please?
 » 5 years ago, # |   0 For problem D I'm using the following logic :- I'm applying separate DFS on all the nodes, With the discovery of every node ( except the ones on which DFS had already been applied ) on whose addition the difference between minimum and maximum does not exceed 'D' , I'm adding 1 to the answer. Can anyone tell me why this logic wont work? Code :- 8665299
•  » » 5 years ago, # ^ |   0 First, your min/max values change on different branches of the tree when you DFS. Second, you only count the number of nodes, while the statement asks for the number of sets.
•  » » » 5 years ago, # ^ | ← Rev. 3 →   0 Why do i have to find the values for d=inf ? i don't understand that . This is my submission , but im still unable to handle all the cases.8709569
 » 5 years ago, # |   -25 Why Mr.Vuong makes this contest ?
 » 5 years ago, # |   0 Link to the code for problem D doesnt work
•  » » 5 years ago, # ^ |   0 Thanks! Fixed.
 » 5 years ago, # |   +8 D — Valid Sets "Firstly, we solve the case d = 0. " It should be "d=inf"
•  » » 5 years ago, # ^ |   0 Thanks! You are right.
 » 5 years ago, # |   +7 I have another solution for E:Let f[i] be the length of a LIS ending at a[i], and g[i] be the length of a LIS beginning at a[i], It's easy to see that L[i] = f[i] + g[i] — 1 is the length of a LIS containing a[i].The length of LIS of A should be m = max{L[i]},1/ An index i is belong to the 1st class iff L[i] < m2/ An index i is belong to 2nd class iff L[i] = m and there exists ANOTHER index j so that (L[j] = m) and (f[j] = f[i]). Because a[i] and a[j] can never belong to the same LIS of A.3/ The remaining index(es) will be assigned into 3rd class.The computation of f[.] and g[.] takes O(n log n) time, and the classification takes O(n) times using counting technique
•  » » 3 years ago, # ^ |   0 8dm651
•  » » 3 months ago, # ^ |   0 Nice one solution.
 » 5 years ago, # |   0 can any anyone explain how is the following relation F(i)=prod(F(j)+1) true? where F(i) be the number of valid sets contain node i as root. F(j) is a node in subtree of i.
•  » » 5 years ago, # ^ |   0 If we have only one child with F(j)=x for the root node, in how many ways can we make a tree containing root.(this is same as F(i) ). Surely x+1 as we can select child in x ways and not select in 1 way.When children increases we simply multiply F(j)+1 for every child we have.How to calculate F(j) for child? (Just do it recursively.) As we reach leaf node its F(i) will be 1.
•  » » 5 years ago, # ^ | ← Rev. 3 →   +9 At each child j, you have the option to select (0,1,2....F(j)) valid sets from subtree rooted at j. Hence F(i) = prod(F(j)+1)It's the same as the proof of finding no of divisors of any number using prime factorization where, if n = a^x * b^y * c^z, no of divisors = (x+1)(y+1)(z+1). Proof Try to relate this to the no of divisors problem, you will find your answer :)
•  » » » 5 years ago, # ^ |   0 great explanation !!! thanks..
•  » » » 5 years ago, # ^ |   0 Can you explain how we can avoid duplicate counting? Thanks.
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 While iterating on all nodes we suppose that the current node will be smallest in our subtree. Therefore for each node i we consider all other node j such that a[j]>=a[i] (and also a[j]<=a[i]+d) . Now suppose we are on j now than all the a[i]'s which are less will not be included in our answer but those a[i]'s which are equal to a[j] would have been already counted if (i
 » 5 years ago, # |   0 My solution for problem E. :) http://codeforces.com/contest/486/submission/8692548
 » 5 years ago, # |   0 In problem E. S[i] is "length of LIS start exactly at i", E[i] is "length of LIS end exactly at i" If (S[i] + E[i] — 1 == l). A[i] belong to a LIS. Otherwise index i must in Group 1. I put A[i] in to n layer (L), n = max{S[i]} = max{E[i]}, without any member of Group 1. A[x] belong to L[i] if (S[x] == i) (or E[x] == i, anyway) If L[i] include 1 element, index of this element belong to Group 3, because we can't make a LIS without it. Otherwise, index of these element belong to Group 2.I haven't code it yet but I think my solution more simple them 2 solution of laoriu, but if anything wrong, tell me pls :).
 » 5 years ago, # |   0 I cant understand how to caculate Fi using segment tree? Can anyone tell me ?
•  » » 5 years ago, # ^ |   0 I don't see any segment tree used in calculating Fi. You are referring to D-Valid Sets, right?We just used DFS to do our work.Can you give link to the solution which used it?
•  » » » 5 years ago, # ^ |   0 i forgot it. segment tree is in E solution. in solution 2, laoriu says: "we can use Segment tree to calculate Fi" but how ?
 » 5 years ago, # | ← Rev. 2 →   0 Can you please tell me how one can think of solution to problem OR matrix in this(tutorial) way? I mean to say is there any specific algo related to it or its pure thinking skill.
•  » » 5 years ago, # ^ |   0 Just pure thinking. The insight of this problem is the property of bitwise OR.
 » 5 years ago, # |   0 problem C is giving correct output(i.e. 6) for first test on my system,but codeforces is showing output '0' for same test.Plz help. http://codeforces.com/contest/486/submission/11666147
 » 4 years ago, # |   0 this is my code for solution 2 :)
 » 22 months ago, # |   0 Can someone tell me how to solve problem E using the way mentioned in the editorial? I have already solved after reading ifsmirnov comment but I want to solve the problem with the way mentioned in the editorial because I am weak at segment trees , can someone explain or link their solution? thanks!
 » 22 months ago, # |   0 486-A sum=(((n*(n+1))/2)-(x*(2*a+((x-1)*d)))/2); why this case failed?? Input 3037000499 Participant's output 9223372035336275558 Jury's answer -1518500250
•  » » 14 months ago, # ^ |   0 what do you mean with a ?
 » 15 months ago, # |   0 Editorial to problem D is love.(^_^)
 » 14 months ago, # |   0 can anyone prove me the answer of problem A ?
 » 11 months ago, # |   0 can anyone please explain the equation of problem D? especially why we have add one to all f[v] before multiplying with f[u]?
 » 9 months ago, # |   0 Hey Guys, Query regarding 486D- Valid Sets: considering case when d= inf, number of valid sets would differ based on root. Consider following case:3 1 2 2 3 when we run dfs(1), number of valid sets will be 3 when we run dfs(2), number of valid sets will be 4.Can anyone clarify this and explain the formula for calculating valid sets.
 » 4 months ago, # |   0 There's a mistake on tutorial of problem C. In the bullet point it says that r should come before but the equation (p ≤ r ≤ n / 2) says the opposite, so just swap the "before" and "after" in the bullets and happy AC :)