ch_egor's blog

By ch_egor, 2 years ago, translation, In English,
Tutorial is loading...

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

Tutorial is loading...

(Developing — ch_egor)

Tutorial is loading...

(Developing — ch_egor)

Tutorial is loading...

(Developing — halin.george)

Tutorial is loading...

(Developing — Sehnsucht)

Tutorial is loading...

(Developing — _kun_, ch_egor)

 
 
 
 
  • Vote: I like it
  • +56
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Thanks for the editorial !

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For Problem F,cant we make p = sqrt(n) and get the complexity as n*root(n)?

Or did I misunderstood something?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Complexity is for movement of , and for movement of . If you choose you got .

    • »
      »
      »
      2 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      My bad

      Thanks for the reply

    • »
      »
      »
      2 years ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      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)).

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

plz explain

n>=k part in problem c

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In 5th problem it should be multiset and not set as there could be equal values.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

plzz explain the third point in problem B??

»
2 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

can someone tell me problem in this 35727835 __ __fixed now

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 .

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't get why you even need a rolling sum

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      'storing sum of minimums in some structure like std::multiset.'

      I did not understand this line in the editorial.

      • »
        »
        »
        »
        2 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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.

        1. 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--;
        }
        
        1. 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.

»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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 = n 2 / P 2) and let l and t be different number in n as step of P so there may be O(n 5 / 3 × n 2 / 3) different movement.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thx~ , I have to learn how to use Mo's algorithm.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I do not understand in problem B 3 case can anyone plzz tell me in simple terms it will be very helpful thnkss ?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can we Solve 940-B using BFS?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone have any idea why Problem D is tagged as Binary Search / Implementation? It seems more like a Greedy solution to me.

  • »
    »
    2 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.