### I_Love_Tina's blog

By I_Love_Tina, history, 5 years ago,

# 798A - Mike and palindrome

Let cnt be the number of such that si ≠ sn - i + 1.

If cnt ≥ 2 then the answer is NO since we must change more than 1 character.

If cnt = 1 then the answer is YES.

If cnt = 0 and n is odd answer is YES since we can change the character in the middle, otherwise if n is even the answer is NO because we must change at least one character.

Complexity is O(|s|).

# 798B - Mike and strings

First of all, you must notice that the operation of removing the first character and appending it to the left is equivalent to cyclically shifting the string one position to the left.

Let's denote by dpi, j the smallest number of operations for making the first i strings equal to string si moved j times.

Let f(i, j) be the the string si moved j times,then .

The answer is min(dpn, 0, dpn, 1, ..., dpn, |sn| - 1).

The complexity is O(|S|3 × n).

# 798C - Mike and gcd problem

First of all, the answer is always YES.

If then the answer is 0.

Now suppose that the gcd of the sequence is 1. After we perform one operation on ai and ai + 1, the new gcd d must satisfy d|ai - ai + 1 and d|ai + ai + 1 d|2ai and d|2ai + 1. Similarly, because d is the gcd of the new sequence, it must satisfy d|aj, j ≠ i, i + 1.

Using the above observations we can conclude that , so the gcd of the sequence can become at most 2 times bigger after an operation. This means that in order to make the gcd of the sequence bigger than 1 we need to make all numbers even. Now the problem is reduced to the following problem:

Given a sequence v1, v2, ... , vn of zero or one,in one move we can change numbers vi, vi + 1 with 2 numbers equal to . Find the minimal number of moves to make the whole sequence equal to 0.

It can be proved that it is optimal to solve the task for consecutive ones independently so we divide the array into the minimal number of subarrays full of ones, if their lengths are s1, s2, ... , st,the answer is .

Complexity is .

# 798D - Mike and distribution

In the beginning, it's quite easy to notice that the condition " 2·(ap1 + ... + apk) is greater than the sum of all elements in A " is equivalent to " ap1 + ... + apk is greater than the sum of the remaining elements in A ".

Now, let's store an array of indices C with Ci = i and then sort it in decreasing order according to array A, that is we must have ACi ≥ ACi + 1.

Our answer will always have size . First suppose that N is odd. Add the first index to our set, that is make p1 = C1. Now, for the remaining elements, we will consider them consecutively in pairs. Suppose we are at the moment inspecting AC2k and AC2k + 1. If BC2k ≥ BC2k + 1 we make pk + 1 = C2k, else we make pk + 1 = C2k + 1.

Why does this subset work? Well, it satisfies the condition for B because each time for consecutive non-intersecting pairs of elements we select the bigger one, and we also add BC1 to the set, so in the end the sum of the selected elements will be bigger than the sum of the remaining ones.

It also satisfies the condition for A, because Ap1 is equal or greater than the complement element of p2 (that is — the index which we could've selected instead of p2 from the above procedure — if we selected C2k then it would be C2k + 1 and vice-versa). Similarly Ap2 is greater than the complement of p3 and so on. In the end we also add the last element from the last pair and this makes the sum of the chosen subset strictly bigger than the sum of the remaining elements.

The case when N is even can be done exactly the same as when N is odd, we just pick the last remaining index in the end.

The complexity is .

# 798E - Mike and code of a permutation

Let's consider ai = n + 1 instead of ai =  - 1. Let's also define the sequence b, where bi = j such that aj = i or bi = n + 1 if there is no such j. Lets make a directed graph with vertices be the indices of the permutation p with edges of type (a, b) representing that pa > pb. If we topologically sort this graph then we can come up with a possible permutation: if S is the topologically sorted graph then we can assign to pSi number i.

In this problem we will use this implementation of topological sort.

But how we can find the edges? First of all there are edges of the form (i, bi) if bi ≠ n + 1 .For a vertex i he visited all the unmarked vertices j (1 ≤ j < ai, j ≠ i) and you know for sure that for all these j, pj < pi. But how we can check if j was already marked? The vertex j will become marked after turn of vertex bj or will never become unmarked if bj = n + 1. So there is a direct edge from i to j if j = bi or 1 ≤ j < ai, j ≠ i and bj > i.

Suppose we already visited a set of vertices and for every visited vertex node we assigned to bnode value 0 (for simplicity just to forget about all visited vertices) and now we want to find quickly for a fixed vertex i an unvisited vertex j with condition that there is edge (i, j) or say it there isn't such j, if we can do that in subquadratic time then the task is solved. As stated above the first condition is j = bi if 1 ≤ bi ≤ n, this condition is easy to check. The second condition is 1 ≤ j < ai and bj > i, now consider vertices with indices from interval 1..ai - 1 and take j with maximal bj. If bj > i we found edge (i, j) otherwise there are no remaining edges. We can find such vertex j using segment tree and updating values while we visit a new vertex. In total we will visit n vertices and query the segment tree at most 2 × (n - 1) times (n - 1 for every new vertex and n - 1 for finding that there aren't remaining edges).

Complexity and memory are and O(N).

• +90

 » 5 years ago, # |   +88 For D, is this magic? 26557143
•  » » 5 years ago, # ^ |   +47 It was pure intuition xD. I didn't expect such a stupid solution to pass. If someone knows why the probability of choosing a correct solution is sufficiently high, I would be glad to know.
•  » » » 5 years ago, # ^ |   0 I would be glad to know too because I was so surprised about such a nice solution :D
•  » » » 5 years ago, # ^ |   +11 There is a similar Problem which really need randomized algorithm. http://codeforces.com/problemset/problem/364/DMaybe the similar of both problem is half of the array
•  » » » 5 years ago, # ^ | ← Rev. 3 →   +13 I got the same solution to pass 26559070.That was a sick try to prove a solution. This proof doesn't work even for 1 array, because "opposite" subset exists only if we forget about cases, where sum of the subset and the rest part are equal. And of course we can't just multiply probabilities because 2 arrays are depending on each other.By the way, on random tests with n=10000 it takes less than 10 times shuffling.
•  » » » 5 years ago, # ^ |   +17 I solved this problem in same solution. (26557462) I think the worst case is: 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 (This is an example of n=20) In this case, the program must choose n/4 elements in left-half, and n/4 elements in right-half. So, probability of choose successfully is C(n/2, n/4) * C(n/2, n/4) / C(n, n/2) ≒ 1/sqrt(n). In summary, you can solve this problem with randomize algorithm in O(n^1.5).
•  » » 5 years ago, # ^ |   +17 Got AC doing the same and have no idea why it works hahaI don't even know how to make difficult input cases.how to approximate the probability of not getting a valid subset while taking one randomly?Is there non-trivial sequences where the answer is unique?questions I would like to answer haha
 » 5 years ago, # |   +8 The problem B's ideone solution is runtime error.
•  » » 5 years ago, # ^ |   0 Oh I have a solution with Ahocorasick automanta,it can be accepted and I think maybe except for the long length of the code,it can be came up with more simply.This is my submission QWQ
•  » » 5 years ago, # ^ |   0 And I find a truth that bruteforce can AC and maybe better than AC automanta...QWQFORCE
 » 5 years ago, # |   +9 Can someone please explain the proof for Array 'A' in Problem D?It's proof is quite unclear to me.Thanks in advance.
•  » » 5 years ago, # ^ | ← Rev. 10 →   -14 Nevermind what I wrote, I thought you were referring to problem A.
•  » » » 5 years ago, # ^ |   +8 Nice Explanation, but I asked the proof for Problem D. You explained for problem A.I meant proof of 'Array A' in Problem D.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +21 Once again, you have an array of indices. You sort it by ai in nonincreasing order. Next you will take the first index C1 (aC1 is the biggest). Afterwards you will take one from 2-nd or 3-rd, one from 4-th or 5-th, etc... There might be one index left in case n was even, you will take it as well. You will always satisfy "a-condition" choosing indices that way. Because:aC1                    ≥ any(aC2,aC3); any(aC2,aC3)       ≥ any(aC4,aC5); any(aC5,aC6)       ≥ any(aC7,aC8); ... | any(aCn — 1,aCn) > 0; —  if n is odd | aCn                  > 0; — if n is evenYou may take any choice between aC2k and aC2k+1, the sum of a-s on the left side will be always greater than the sum of a-s on the right side. Notice strict inequality sign > in the last statement.Now think about b-s. Simply among C2k and C2k+1 choose one with the biggest b. You will have:bC1                    > 0; max(bC2,bC3)      ≥ min(bC2,bC3); max(bC4,bC5)      ≥ min(bC4,bC5); ... | max(bCn — 1,bCn) ≥ min(bCn — 1,bCn); —  if n is odd | bCn                  > 0; — if n is evenSame considerations for b-s. Sum of the left side will be always greater than sum of the right side.
•  » » » 5 years ago, # ^ |   0 Could you explain, why quite similar greedy doesn't work: 26568197 the idea is: let's sort the first array of pair according to the first element, than create its copy with changed fields and sort the second array according to the second element.Then reverse both of them.Take two pointers.The number of steps is a constant.Iterate steps. If a step is even, choose the best from the first array and insert to the "answer"-set. if it is already there, increase the pointer until finding unused pair.Otherwise, if a step is odd, do the same with the second array.All the test, breaking this solution, are too big and I can't check them.
•  » » » » 5 years ago, # ^ |   +3 Try reversing the order on even take best from second array and on odd take best from first array.you will get wa on pretest1
 » 5 years ago, # |   +9 Can someone please explain the bold part: Problem 798C — Mike and gcd problem: Now suppose that the gcd of the sequence is 1. After we perform one operation on ai and ai + 1, the new gcd d must satisfy d|ai - ai + 1 and d|ai + ai + 1 => d|2ai and d|2ai + 1. Similarly, because d is the gcd of the new sequence, it must satisfy d|aj, j ≠ i, i + 1.
•  » » 5 years ago, # ^ |   +5 If you have d|x and d|y, then it's not hard to see that d|x + y and d|x - y also holds (just use the basic definition of definition of divisibility). Now just replace x with ai - ai + 1 and y with ai + ai + 1.Also, if d|a and d|b, we also have . This comes from the properties of , you should probably google it
•  » » » 5 years ago, # ^ |   +7 Using the above observations we can conclude that d | gcd(a1, ..., 2 * a[i], 2 * a[i + 1], ..., a[n]) | 2 * gcd(a[1], ... a[n]) = 2 so the gcd of the sequence can become at most 2 times bigger after an operation. This means that in order to make the gcd of the sequence bigger than 1 we need to make all numbers even. Now the problem is reduced to the following problem:I don't understand why d | 2 * gcd(a[1], ... a[n]) and why "the gcd of the sequence can become at most 2 times bigger after an operation"
•  » » » » 5 years ago, # ^ | ← Rev. 10 →   0  =  |  =  so d ≤ 2.
•  » » » » » 3 years ago, # ^ |   0 Thank you, I got it.
•  » » » » » 23 months ago, # ^ |   0 No,if we choose d=15 and x=3 and b=5 then although 15 is divisible by 3 and 5 both but not by 5+3=8,neither by their difference 2.Will you please explain!
•  » » » » » » 23 months ago, # ^ |   0 dude its not d thats divisible by x or y .... its the other way round'''example d=3; x=15, y=9d|x and d|yso d|(x+y)
•  » » » » » 16 months ago, # ^ |   0 what's the meaning of "d|gcd(........)"....thanks in advance
•  » » » 23 months ago, # ^ |   0 No,if we choose d=15 and x=3 and b=5 then although 15 is divisible by 3 and 5 both but not by 5+3=8,neither by their difference 2.Will you please explain!
 » 5 years ago, # |   0 can somebody please explain what does this statement mean in the editorial of C Using the above observations we can conclude that , so the gcd of the sequence can become at most 2 times bigger after an operation. This means that in order to make the gcd of the sequence bigger than 1 we need to make all numbers even.
•  » » 5 years ago, # ^ |   +3 My observation was this. Let's take any two consecutive numbers a1, a2. Let us assume that we are trying to make gcd k which is an odd number. So a1 = k * x1 + r1, a2 = k * x2 + r2. Now a1 — a2 will be a multiple of k if r1 = r2. a1 + a2 will be a multiple of k if r1 + r2 = k. If k is an odd number, it is impossible that r1 = r2 and r1 + r2 = k. Hence we can conclude that you can never try to make gcd an odd number. So we have to aim for making gcd even. That means you need to make the numbers even. That will be enough to make gcd an even number (which will atleast be 2). Now let's take a1, a2. In two steps, (a1, a2) = > (a1 — a2, a1 + a2) = > (-2 * a2, 2 * a1). So in two steps, any two numbers will be a multiple of 2. So find all consecutive odd numbers. Let this be cnt. Add cnt / 2 to final answer if cnt is even. Add cnt / 2 + 2 to final ans if cnt is odd. If both numbers are odd, only 1 step is needed. If one of them is odd, two steps are needed.
•  » » » 5 years ago, # ^ |   0 Found your explanation more easy to understand than the editorial. Thanks. Can anyone explain the following statement taken from the tutorial I understand that d divides gcd(a1,...2ai,2ai+1,...an) after operation on ai and ai+1 but why gcd(a1,...2ai,2ai+1,...an) divides 2*gcd(a1,...an)?
•  » » » » 4 years ago, # ^ |   0
 » 5 years ago, # |   +1 How to solve C using DP ?
•  » » 5 years ago, # ^ |   +3 hey you can checkout my solution http://codeforces.com/contest/798/submission/26676645
 » 5 years ago, # | ← Rev. 2 →   0 Please explain DP solution of B, can't get it from the editorial. what is the idea and the overlapping subproblem ?
•  » » 15 months ago, # ^ |   0 Have u got it?
 » 5 years ago, # | ← Rev. 7 →   +8 The test data of Problem D maybe too weak? I just used sort and slides to Get AC. In contest, I just fogot the length of this is [n/2]+1WA32: 26560156 After contest, I just do r+1, then I got ACAC: 26571236 Could someone prove my idea is correct?UPD1: I delete sort also got AC.. The algorithm complexity is O(n) 26571390UPD2: I can prove it now xD
 » 5 years ago, # |   +3 can someone please explainGiven a sequence v1, v2, ... , vn of zero or one,in one move we can change numbers vi, vi + 1 with 2 numbers equal to . Find the minimal number of moves to make the whole sequence equal to 0.in problem C？
•  » » 5 years ago, # ^ |   +1 Basically since we're trying to make every number a multiple of 2 we're only concerned about the parity of each number so we convert them to zeros and ones by taking ai mod 2. Then we do the moves on this array and try to make them all zero, which is even parity. Also note that on array v1, ..., vn each move is equivalent to vi xor vi + 1 since we're only concerned about the parity.
 » 5 years ago, # |   0 Anyone finds C div 2 hard ? Or it is just me
 » 5 years ago, # | ← Rev. 3 →   0 In C, sorry to tell that I just couldn't understand how to translate these mathematical language, could anyone please tell me the meaning in plain english?What's more, the 't' here confused me, too. UPD1:now I understand the 't', so stupid am I. XD
 » 5 years ago, # | ← Rev. 3 →   +6 Why do we need dp in B? Here is a simple solution -First fix a si, we will try to make all other sj equal to si.We can find the number of shifts needed efficiently by C++ STL function: (s[j] + s[j]).find(s[i])Sum the total number of shifts needed, repeat this for all si, minimize the number of total shifts needed.Complexity: , the find() function works in average case!Code: 26543372
•  » » 5 years ago, # ^ |   0 hi, I saw ur code and I think you assumed that for minimum moves the string to which other strings have to move lies among the given string (in unrotated state ) can you correct me if I am wrong ? you take i th string and check cnt of rotations other strings have to undergo to match this i th string , but what if they have to match i th string rotated twice ?
•  » » » 5 years ago, # ^ |   0 I am not assuming that! That will happen always!Let me give an example!s[j] = cdab and s[i] = abcd. We need to rotate s[j] to make s[i].I am not assuming that s[i] is contained in s[j] but surely it will be in s[j]+s[j].s[j] + s[j] = cdabcdab and first occurrence of s[i] appears in position 2. Se we need 2 shifts! To make s[j], s[i]. Just think about it! You will get why this works!
•  » » » » 5 years ago, # ^ |   0 just to confirm, are u saying that answer is always one among given strings (if all strings are valid) ? thanks for reply
•  » » » » » 5 years ago, # ^ |   0 Yes! The base string will always be one among given strings :) Because we are not allowed to shift right, only shift left. So it will not be optimal if we shift one left and then try to make all other equal to this! it will be optimal not shifting the base! So the base string is always from one of the given strings :) Hope it helps :)
 » 5 years ago, # | ← Rev. 2 →   0 I'm not sure for the correctness(At least I passed the tests), but may problem B and C be done in an easier way?problem B can be achieved in O(nS^2) just by Bruteforce. 26550167And problem C can be done with linear DP(define f[i][0/1] represents the minimum operation number needed to make the sequence a[1...i-1] all even and leave a[i] even/odd). 26561463
 » 5 years ago, # | ← Rev. 5 →   0 In problem C my approach was first you can take gcd of all numbers and check whether it is greater than 1. If not then you can greedily check for no of moves required to make all ones by using the property that when there are two odd numbers then you can make them even in one move else if there is one odd and one even then you require two moves.Time complexity: O(n)Submission link: http://codeforces.com/contest/798/submission/26564933
•  » » 5 years ago, # ^ |   0 Yeap, our solutions are quite close, basicly the same idea.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 WOW, almost the same idea, I had just finished it! XD code
 » 5 years ago, # |   0 Thank you for the fast editorial! It was a great contest :)
 » 5 years ago, # |   0 For problem D what should be the answer for below case? I guess its not possible to choose a subset! Thanks in advance. 2 1 4 5 5 4 1
•  » » 5 years ago, # ^ |   0 21 3
•  » » » 5 years ago, # ^ |   0 But some accepted solution give output 2 2 3 Its wrong I guess!
•  » » » » 5 years ago, # ^ |   0 Surprisingly dreamoon_love_AA's AC solution gives 2 1 2 It is obviously wrong!!
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 I think you meant to run this case 3 1 4 5 5 4 1
•  » » » 5 years ago, # ^ |   0 Yea. Sorry. That was my mistake.
 » 5 years ago, # |   +1 can someone explain why d | gcd(a1, a2, ...., 2ai, 2(ai+1), ....an) | 2*gcd(a1,....an) = 2? I get the first step and the last step. but i don't quite see why gcd(a1, a2, ...., 2ai, 2(ai+1), ....an) | 2*gcd(a1,....an)
•  » » 5 years ago, # ^ |   0 don't know ++
 » 5 years ago, # | ← Rev. 2 →   0 I haven`t read all the below comments (might possible , anybody has already mentioned what I will tell ) so spare me if you feel I have wasted your time .I just want to request I_Love_Tina to kindly once again go through the solution of C problem . Your solution is absolutely correct but I believe you have done a minor mistake while writing editorial . The formula written for calculating answer should have 2 * (si % 2) rather than si % 2 .I can explain that by a simple test case .for n = 3 and a = {1 , 1 , 1} it will take 3 steps .Steps are {0 , 2 , 1} {0 , 1 , 3} {0 , 4 , -2}The above written formula is possibly ignoring the last step . Note :- si means ith element of vector s (as given i is the subscript) .
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 That's what the ceiling function is for in
•  » » » 5 years ago, # ^ |   0 Oh ! Is that ceil function ?? I thought its greatest integer function (floor) .If that is so , there is no problem .
•  » » » » 5 years ago, # ^ |   0 yes :)ceil: ⌈x⌉floor: ⌊x⌋
•  » » » » » 5 years ago, # ^ |   0 Oh.. Okay.. Thanks yassin_.. I didn't know that..
 » 5 years ago, # | ← Rev. 2 →   +5 I can't understand the editorial for E, can someone help me? I don't understand the described construction and it doesn't seem to correspond to the code...How do you do toposort with O(n^2) edges in less time?Obv. my submission which constructs the graph first and then does toposort got TLE (and could also MLE) 26580802
•  » » 5 years ago, # ^ |   0 Here.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 I had the same question and finally I realized three keys: The edges are saved in a compact form, i.e. vector a and vector b. To know if there is an edge (i, j), we can check the rules as described in the editorial. The memory requirement is O(N). Vector b is kept updating while doing toposort. The goal is to avoid checking all the edges (otherwise it takes O(N^2) time). The idea is that if a vertex v is processed while doing toposort, then we can remove all the edges connecting to it. Doing this is simple: set b_v to 0 (and also update the segment tree). Segment tree is used for efficiently query an unprocessed child node. Hope this helps.
•  » » » 5 years ago, # ^ |   0 Yes, thank you for this intuition behind solution :)
 » 5 years ago, # |   0 Please someone help me on E. I could not get its algorithm in editorial.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +9 I updated the editorial and added some links to the editorial in the code, hope it will help, sorry i'm but bad at explanations :(.
•  » » » 5 years ago, # ^ |   0 Nice problem. Thank you very much
•  » » 5 years ago, # ^ |   -6 Vietnamese detected!!!
 » 5 years ago, # |   0 I have a question for problem D. I understand this "_If BC2k ≥ BC2k + 1 we make pk + 1 = C2k, else we make pk + 1 = C2k + 1_" , but how to prove that sum of all Acpi (let's say S) is greater than (sum of all a[i])-S.
 » 5 years ago, # |   0 Thanks for the editorial.In problem E:'So there is a direct edge from i to j if j = a_i or 1 ≤ j < a_i, j ≠ i and b_j > i.'I think it should be 'i = a_j' (or 'j = b_i') to match the definition of a and b.
•  » » 5 years ago, # ^ | ← Rev. 5 →   0 According to writer's code it's j = bi。 And what is even more .... is\n " Lets make a directed graph with vertices be the indices of the permutation p with edges of type (a, b) representing that pa < pb " According to writer's code SHOULD BE "Lets make a directed graph with vertices be the indices of the permutation p with edges of type (a, b) representing that pb < pa"
•  » » » 5 years ago, # ^ |   0 Fixed.
•  » » » » 5 years ago, # ^ |   0 thanks
•  » » » » » 5 years ago, # ^ |   0 by the way，is it possible that the solution will decrease to O(n^2) if it check's every edge?
•  » » » » » » 5 years ago, # ^ |   0 Yes.
•  » » » » » » » 5 years ago, # ^ |   0 thanks for your amazing problem and patient explantion.:)
•  » » » » 5 years ago, # ^ |   0 In"But how we can find the edges? First of all there are edges of the form (bi,  i) if bi ≠ n  +  1" shouldn't it be "(i, bi) if bi ≠ n  +  1" ?
 » 5 years ago, # |   +16 Really decent/wonderful solution for E! I really love this problem and solution. Thank you for preparing this awesome problem!
 » 5 years ago, # |   0 For the problem E if I understand well, the last element of input should be 5 because 4th is found 5 as the next vertex so the smallest j such as Pj > Pi should be 5 right?
 » 5 years ago, # |   0 can anyone please guide me as to why my solution is failing for D, it is passing only first test case ?Logic which i followed here is first sort the arrays in ascending order, then take a subset of K elements and add them and check 2*sum > sum of array. If not, then move the subset by one element maintaining it of K elements and continuing. whats wrong with this ? I also tried by sorting in descending order, using long long int but still same result.Here's the solution — 26824837
 » 5 years ago, # | ← Rev. 2 →   0 For problem C, the editorial states:It can be proved that it is optimal to solve the task for consecutive ones independentlyIs anyone able to explain this proof? I cannot seem to understand why this is true.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Suppose for k consecutive ones the answer will be . Now i claim that it isn't optimal to make one subarray full of one out of two. Suppose we have two subarrays of length a, b and distance c(c > 0) between them. It is needed exacty c operations to transform it into one subarray. Then we need to just check if c + f(a + b + c) < f(a) + f(b), it turns out that for c > 1 the inequality isn't satisfied while for c = 1 you can check 3 cases (each parity for a, b) and also verify that it isn't satisfied.
 » 5 years ago, # |   0 Can someone please explain how choosing just the j with maximal bj work in Problem E, instead of the obvious and inefficient way of choosing all the j(s) satisfying the second condition?
 » 3 years ago, # |   0 for problem B I did a simple brute force (without DP) with the same complexity
 » 2 years ago, # |   0 B solution without dp ... Very Fast Solution https://github.com/joy-mollick/String-Problems/blob/master/Codeforces-798B%20-%20Mike%20and%20strings%20.cpp
 » 2 years ago, # |   0 How does this solution even works, I mean it should give TLE in some testcase This solution for Problem D. He is shuffling the array.
 » 2 years ago, # | ← Rev. 2 →   0 How to prove the greedy part of problem C: that it is optimal to deal with consecutive odd numbers first and then deal with all the remaining odd numbers. This was the difficult part of the proof, which the author of the editorial quite conveniently skips.
 » 22 months ago, # | ← Rev. 2 →   0 Great problems :)
 » 16 months ago, # |   0 getting WA on TC 40 of the problem C can anyone explain why.103511979
•  » » 2 months ago, # ^ |   0 try the following test case: 3 3 6 9It is because the test case already has gcd > 1, and the gcd is odd
 » 9 months ago, # | ← Rev. 2 →   0 Hey. Why in problem C 789C - Functions again if $d \mid a_i - a_{i+1}$ and $d \mid a_{i+1} + a_i$ then $d \mid 2a_i$ and $d \mid 2a_{i+1}$?
 » 9 months ago, # |   +9 I saw this blog in the recent actions and after looking at the author's username, sorry but only 1 question popped up in my head. I_Love_Tina, does Tina love you?!
 » 9 months ago, # |   0 Can anyone explain DP solution for B