### ch_egor's blog

By ch_egor, 4 years ago, translation,

(Developing — vintage_Vlad_Makeev, ch_egor, V--o_o--V, demon1999)

(Developing — ch_egor)

(Developing — ch_egor)

(Developing — halin.george)

(Developing — Sehnsucht)

(Developing — cdkrot, ch_egor)

• +56

 » 4 years ago, # |   +14 Thanks for the editorial !
 » 4 years ago, # |   0 For Problem F,cant we make p = sqrt(n) and get the complexity as n*root(n)?Or did I misunderstood something?
•  » » 4 years ago, # ^ |   +10 Complexity is for movement of , and for movement of . If you choose you got .
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 My badThanks for the reply
•  » » » 4 years ago, # ^ | ← Rev. 3 →   0 I'm having trouble understanding how those complexities are derived. Can you explain it in more detail? Thanks!Edit: figured it out.There are O(N^2/P^2) blocks, each with O(P^2/N) elements. Left pointer: For each block with O(P^2/N) elements, it takes O(P) to go from one element to the next. So the complexity for processing each block is O(P^3/N), and the complexity of processing every block is O(P^3/N) * O(N^2/P^2) = O(NP).Right pointer: For each of O(N^2/P^2) blocks, the right pointer moves O(N) times. The total number of times the right pointer moves is O(N^3/P^2).We can find the minimum complexity by setting the left and right pointers complexity equal. So NP = N^3/P^2, which gives P = N^(2/3). So the total complexity for both movements is O(N^(5/3)).
 » 4 years ago, # |   0 plz explainn>=k part in problem c
•  » » 4 years ago, # ^ |   0 extract prefix of length k and find the next string lexicographically.
•  » » » 4 years ago, # ^ |   0 Thanxx
•  » » » 17 months ago, # ^ |   0 Can you give a proof for this?
 » 4 years ago, # |   0 In 5th problem it should be multiset and not set as there could be equal values.
 » 4 years ago, # |   0 plzz explain the third point in problem B??
 » 4 years ago, # | ← Rev. 3 →   0 can someone tell me problem in this 35727835 __ __fixed now
•  » » 4 years ago, # ^ | ← Rev. 4 →   0 gotem. boyzdebug urself
 » 4 years ago, # |   0 The explanation for D kinda seems more complicated than it needs to be. I mean... the problem gives you three cases.First case allows you to change a 1 to a 0 if some condition happens. Second case allows you to change a 0 to a 1 if some condition happens. Third case allows you to keep the current digit (with no condition).Therefore, to solve, if the current digit was changed from a 1 to a 0, apply the restrictions for case 1; if it was changed from a 0 to a 1, apply restrictions for case 2. Else, no restrictions need to be applied.
•  » » 4 years ago, # ^ |   0 All cases here are just for prove that we haven't other cases. It's obvious that we don't need upper bound for and lower bound for .
 » 4 years ago, # |   0 For multiset in E do we maintain a rolling sum. When inserting in multiset we add it to that sum and while removing ( if the size of multiset exceeds the required (i-j+1)/c elements ) we subtract. And final is sum of i-j+1 elements minus the rolling sum we maintained? Or we have to do something else?
•  » » 4 years ago, # ^ |   0 I don't get why you even need a rolling sum
•  » » » 4 years ago, # ^ |   0 'storing sum of minimums in some structure like std::multiset.'I did not understand this line in the editorial.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 So i also struggled with this line for some time. And here is what i figured:you'll need four things: a tree-multiset (multiset< int > ms), an integer containing sum (int sum), an integer with the greatest element in the multiset to be contained in the sum (the greatest summant; int geis) and an integer counting summants equal to geis in the sum (int nog).Firstly we set: ms = empty multiset, sum = geis = nog = 0; Only when ms.size() == c we reassign sum and geis with the first smallest number in ms: sum = geis = *(ms.begin()); nog = 1;Now, when you insert an element (int el) to ms you need to update sum and geis values only when ms.size() > c. If el < geis: sum += el; sum -= geis; //we replace geis as a summant with el in sum. if (nog == 1){ geis = *(ms.lower_bound(geis)--); // we find the first "old" geis position in ms and get value of previous element - this is our "new" greatest summant nog = ms.count(geis); } else { nog--; }  If number of summants increase (ms.size() % c == 0) we add to the sum next value not less than geis: int geis_count = ms.count(geis); if (geis_count > nog){ nog++; } else { nog = 1; geis = *(ms.upper_bound(geis)); } sum += geis; Please note, that each update requires O(1) searches (or other operations with the same complexity) in a tree-multiset of size O(n), thus requiring O(log n) time for each insert, O(n log n) time for each i in the main for loop and finally O(n**2 log n) for the solution.
 » 4 years ago, # |   +5 For problem F: sorry, I don't understand why we should change t to one in O(1) time. And does it means that we should let r be the sequence of {r1, r1 + s, r1 + 2s, ...}(s = n2 / P2) and let l and t be different number in n as step of P so there may be O(n5 / 3 × n2 / 3) different movement.
•  » » 4 years ago, # ^ |   0 I think it's supposed to say that you can change t by one in O(1) time, i.e. go from t to t + 1 or t - 1 as necessary. What you do is sort the queries as described and answer them using Mo's Algorithm.
•  » » » 4 years ago, # ^ |   0 thx~ , I have to learn how to use Mo's algorithm.
 » 4 years ago, # |   0 In editorial of F, how it's ensured after sorting that 1st type queries are calculated after the intended number of 2nd type queries for ex. lets say P = 10 so for number of change queries from 1 to 9 will fall together and there might be wrong ordering in processing them.
 » 4 years ago, # |   0 I do not understand in problem B 3 case can anyone plzz tell me in simple terms it will be very helpful thnkss ?
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 +1
 » 4 years ago, # |   0 Can we Solve 940-B using BFS?
•  » » 19 months ago, # ^ |   0 No.Not so sure but first cause of the constraints, Secondly he is not asking for the minimum number of operations but asking for the cost so if the constraints was like 1e5 you can use Dijkstra not BFS.and i may be wrong.
 » 2 years ago, # |   0 For problem F, I am pretty sure that for the "minimum length of array, such that answer for it is c", the length should be: $1 + 2 + 3 + ... + \ c \ -\ 1 = \frac{c(c - 1)}{2}$This is because $c$ must not be present in the set that is used in the mex function. Luckily, the assertion that the answer won't be more than $2 \cdot \sqrt{N}$ still holds. We can get a tighter bound though. But the expression will not be so nice anymore.
 » 20 months ago, # |   0 Anyone have any idea why Problem D is tagged as Binary Search / Implementation? It seems more like a Greedy solution to me.
•  » » 18 months ago, # ^ |   0 You can binary search for l and r. The idea is simple: just check if the conditions are satisfied at the points where we have "00001" or "11110" (because these are the ones which matter) for l and r separately (while doing the binary search). Since the answer is guaranteed to exist, you can find it by binary search too.
 » 8 months ago, # |   0 I tried to solve 940B because it has a DP tag since I've been trying to improve my understanding on DP recently. I solved this using greedy only without any DP concept, and the editorial seems to do the same. Is there any DP idea to solve this?Thanks a lot!
•  » » 7 months ago, # ^ |   0 With DP u can solve it but my solution's time complexity is O(n)
 » 7 months ago, # |   0 Can someone plz. provide me better solution than O(n^3) for problem A