pikmike's blog

By pikmike, history, 5 weeks ago, translation, In English

1437A - Marketing Scheme

Idea: adedalic

Tutorial
Solution (adedalic)

1437B - Reverse Binary Strings

Idea: adedalic

Tutorial
Solution (adedalic)

1437C - Chef Monocarp

Idea: BledDest

Tutorial
Solution 1 (pikmike)
Solution 2 (pikmike)

1437D - Minimal Height Tree

Idea: adedalic

Tutorial
Solution (adedalic)

1437E - Make It Increasing

Idea: Ne0n25

Tutorial
Solution (Ne0n25)

1437F - Emotional Fishermen

Idea: BledDest

Tutorial
Solution (BledDest)

1437G - Death DBMS

Idea: BledDest

Tutorial
Solution 1 (pikmike)
Solution 2 (pikmike)
 
 
 
 
  • Vote: I like it
  • +88
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks for the tutorial

»
5 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

Well i'm not so sure about this but i think another more straight forward answer for b is that we use the fact below

Spoiler

Once again I say as i'm still a beginner i'm not fully confident of this approach tell me if it has a problem

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

    I used a similar approach submission

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

    I did this, but I don't have proof why this works.

    I saw that when there is a even length contiguous block of bad indices then one reversal fixes that block. But for odd length blocks it still works, I don't why, I was seeing that probably the odd length blocks cam be paired up with other odd blocks but couldn't conclude much.

    Anybody can prove this?

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

      MJ_TheTechGuy You are almost correct. The reason this works is that since the number of indices that have to be reversed is always even (pretty straightforward), the number of odd blocks will be even in number. Two consecutive odd blocks can be made correct in 2 moves, the first move- reverse the whole substring between the first odd block tot he next odd block(both inclusive), then in the second move reverse only the middle part which was initially correct before the first move.

      So overall, 2 odd blocks require 2 moves, and they are even in number, so for the sake of counting we can say that we need 1 move per odd block, and 1 move per even block is obvious. So the answer is the total number of blocks.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Ah, I see, I was unable to see why number of odd blocks is even, turned out it's because total bad indices are even. I think I had hard time realising this. Thank you for your comment!

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

    a simpler approach submisson

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

      Can you please explain your logic?

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

    Yup, you are right. I used this approach only. :-)

»
5 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

For G, can someone please explain why iterating over all the terminals in each query is $$$O(Q*sqrtN)$$$?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    Not exactly $$$q \sqrt n$$$ but $$$(sum~of~lengths~of~q) \cdot \sqrt{sum~of~lengths~of~s_i}$$$. No more than $$$\sqrt{sum~of~lengths~of~s_i}$$$ words can end in each position and there are $$$(sum~of~lengths~of~q)$$$ positions in total.

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

      why n^(1/2)? I think it should be n^(2/3).

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

        Why? If we want to find out the maximum number of unique lengths then let's take the smallest possible lengths $$$1, 2, \dots, k$$$, one string per each length. The sum of them is $$$\frac{k(k+1)}{2}$$$, thus $$$k$$$ is $$$\sqrt{2 \cdot total\_length}$$$.

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

          Let's conside the worst case, when you query for a string T, let's says T = abcd...z, and insert every substrings into the Automaton, There are O(|T|^2) substrings, and the total length of them is n = 1*|T| + 2*(|T|-1) + .... + |T|*1 = O(|T|^3).

          By subsititution, we have O(n^(2/3)) in the worst case. Did I make some mistake?

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

            I think you are mistaking what are we summing up. What we are doing with the query is the following: add the first letter, save the current vertex and look at the terminals above the vertex (their count is $$$O(\sqrt{dictionary\_length})$$$). Then go over the next letter from the saved vertex, once again jump no more than sqrt times. I don't really see how the substring count of the query is relevant here.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    for each search you can also just keep a set of which words you have already matched in the current search (actually a set with each terminal of the trie that has already matched). thus, if you are visiting it again during the same search, you just ignore it. then the first solution for G becomes O((q+T) log n), T being the sum of lengths of each query of type 2.

    97259249

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

      Why do you think the complexity is like that? I don't quite see how to construct a test such that there are a lot of distinct substrings of fixed total length but I don't see $$$O((q + T) \log n)$$$ either.

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

        that's true, I can't figure out a better bound for the number of matched strings in total. the O(q sqrt(n)) bound seems tight. the set i suggested just avoids going up the suffix link tree more than once per terminal.

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

Thanks

»
5 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

In E, I am not able to get why are we subtracting i from each a[i] int the following step forn(i, n + 2) a[i] -= i; in editorial solution.

Can somebody help me? Thanks in advance!

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

    Same Here. I didn't get that part For eg. if the seq is [2,5,3,1] then we can't choose LIS as [2,3] but by taking distance consideration and by making a[i]-=i how we are able to do that.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    If you subtract i, it leaves room for you to make the other elements in strictly increasing order.

    For example, if we have the array

    1, 1, 2, 3

    And we subtract i from each,

    1, 0, 0, 0

    You can see if we make these elements all equal, then the original array will be increasing. If we change everything to one and then add i again, we have

    1, 1, 1, 1 -> 1, 2, 3, 4

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

Hi which programming language is this: (answer to A) ? (I'm asking cuz it looks sexy)


fun main() { repeat(readLine()!!.toInt()) { val (l, r) = readLine()!!.split(' ').map { it.toInt() } println(if (2 * l > r) "YES" else "NO"); } }
»
5 weeks ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

adedalic "The longer the segment [a2,a) is the better and the maximum we can take is a=2l."
Can you please explain this statement a bit more? maximum a possible is 2*l but there can be a such that a<l and satisfies the constraints!! and we have to analyze that also.. Am I missing something?

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

    It has been shown that $$$\left\lfloor\frac{l}{a}\right\rfloor = \left\lfloor\frac{r}{a}\right\rfloor$$$. And also that, we must find $$$a$$$ such that $$$\frac{a}{2} \leq l$$$ $$$mod$$$ $$$a \leq r$$$ $$$mod$$$ $$$a < a$$$. So, it must be obvious that $$$r - l < \frac{a}{2}$$$, if such an $$$a$$$ exists
    Case I: $$$r \geq 2l$$$
    Here we must have $$$l \leq r - l < \frac{a}{2}$$$. That is $$$a > 2l$$$. But this wont work as $$$l$$$ $$$mod$$$ $$$a$$$ would be less than $$$\frac{a}{2}$$$
    Case II: $$$r < 2l$$$
    We can always choose $$$a = 2l$$$

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

      I got what you said, it becomes easy as soon as you have the two cases(r>=2*l and other one) to analyze.

      but what if we want to analyze cases as below
      0) obviously a should not belong to [l,r]
      1) if it is possible to have required a such that a>r, this gave me 2*l>r
      2) then a<l, this I couldn't get to any conclusion

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

        i thought the same way beacause between l and r you will get mod 0 and hence it cant be an answer so you need atleast something larger than r . then i tried a= r+1 and it worked and also r+1 should be less than l because l%a >=a/2 .

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

        According to 0), either a > r or a < l. if a > r, obviously that a == r+1 is the best. Now we want to prove if a == r+1 is not satisfied, a < l will be not satisfied too.

        If a == r+1 is not satisfied, it means l*2 < r+1, right? Because Only in the situation that l mod (r+1) = l < (r+1)/2, the restriction is not satisafied.

        Next, l*2 < r+1 means l*2 <= r. If a < l, you will easily become aware of that for every a, exist a k that satisfy l <= k*a <= r. Because l*2 <= r.

        If l <= k*a <= r, the restriction is not satisfied. So we finally find if a == r+1 is not satisfied, a < l will be not satisfied too.

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

      It can be done using simple fact that for any no x ,it will have maximum possible mod when we take its mod by any no grater than x

      Proof for x% y :

      case1 — when y > x in this case ans is always x .

      case 2 — when y =x int this case ans is 0 always.

      case3 -when y < x in this case x % y < y and y < x so maximum value of mod occurs in first case.

      so for any l to r just think of taking a = r+1 ;

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

For Problem F, I've got a $$$O(n log n log max a_i)$$$ solution. Code

Basically $$$dp[i][j]$$$ means the number of ways to make fisherman $$$[1,i]$$$ emotional while $$$j$$$ of them are happy, considering the sequence in descending order.

Then use a segment tree with range multiply update and range sum query to speed up the solution.

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

G can also be solved with suffix tree. I dont know about Aho Corasick , but i heard that algorithm use in Aho-Corasick is similar .

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

It may be completely irrelevant but I just want to ask one doubt. Should I upsolve the problem which are rated at something greater than 2600 (For example F,G in this contest) or should I upsolve only problem which I currently feel comfortable with? (From experience, I can say I am able to understand 2400 rated problem if given some hours)

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    If you just want to be high expert or low cm, you should probably just do easier tasks(<=1900). Though in theory, doing hard problems is a lot better but doing too hard tasks can make you demotivated, make you look at editorial too quick etc.

    I would suggest upsolve upto 200-400 rating points above you, depending on how hard they feel to you.

    Contests are about struggling with problems so also make sure you struggle before reading editorial.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

why would greedy fail for C?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    what greedy?

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

      Like we use T for every distinct ti equal to it so answer will be 0 till then and for every duplicate ti we will use the smallest absolute difference to it's left(greater than 0) or right which has not been used and add it to the answer

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

        Any reason why this should work?

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

          we are trying to minimize the answer but now that it's known that greedy doesn't work, I just want to know why

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

            How will you choose which side you should take

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

              I will sort the initial array first and then if both sides have equal absolute difference then I will choose the left side as the right side may come in handy for further values of the array

              • »
                »
                »
                »
                »
                »
                »
                »
                5 weeks ago, # ^ |
                  Vote: I like it +9 Vote: I do not like it

                Just take this example: 1 3 4 4 6 7 7 8 9 10 11 12

                According to your logic, you'd take 5 for the repeated 4 because 2 is farther, however, taking 2 would be more beneficial because then you'd have 5 available for the repeated 7 later. I hope it's clear.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 weeks ago, # ^ |
                    Vote: I like it +3 Vote: I do not like it

                  Thank you. This is the test case I was missing.

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

                  And we can always reach this lower bound, by pairing 00 with 11 or with left/right border of s What Does This Mean Can Someone please elaborate

                  In Problem B

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

                  I think it is because of only look of situation when we have pairs of one type is like: 010101101010.

                  Generic look: ...xyxyxyxxyxyxyx... here you can just reverse a half.

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            And even your algorithm will not follow this: " I claim that there is an optimal answer such that the times T for each dish go in the increasing order. "

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

    Even I was doing same during contest but cant find why it is wrong https://codeforces.com/contest/1437/submission/96912740 .Help if anyone got it?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1437/submission/96882318 can anyone please explain what is wrong with my code Problem A

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

    Floating point precision maybe. Just change the condition in the other form l*2>=r+1

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

      But on some Ide's it is actually giving ans Yes at 7th case and also when I use double instead of float it got accepted.

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

        I have similar experience when i used to use ceil function instead of the formula a+b-1//b precision can be pain. I have read double is more precise than float though.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain the implementation of problem C first approach. I understood the tutorial, but didn't understand implementation.
why do we use dp[i][j + 1] = min(dp[i][j + 1], dp[i][j]); ?

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

    I will try to present this in an easy manner here i means ith dish and j signifies the time when it was picked so this transition (dp[i][j + 1] = min(dp[i][j + 1] , dp[i][j]) implies that either the current time is the most appropriate time to pick the ith dish or you can simply check for j + 1 — 1 th minute which is nothing but jth minute and this works because we are calculating the answer for each minute from 1 to MAX limit so we just need to pick the best one which we will assign to the current dish you can have a look at my submission for reference . Hope it helps :) sorry for my bad english :(

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

    Let's see what we are doing while iterating the for loop in the first approach-

    We are updating two values dp[i+1][j+1] and dp[i][j+1].

    We are updating dp[i+1][j+1] when it has larger value than dp[i][j] + abs(t[i] — j), which is in fact always (so you can try changing min(dp[i + 1][j + 1], dp[i][j] + abs(t[i] - j) to dp[i][j] + abs(t[i] - j)).

    Now to the real question- We are updating dp[i][j+1] when it has larger value than dp[i][j], as dp[i][j+1] currently stores dp[i-1][j] + abs(t[i-1] - j)(accept for i=0), if its more than dp[i][j] we update it.

    In simpler terms, we are just comparing dp[i][j] + abs(t[i] - j) and dp[i+1][j] and assigning the minimum of the two to dp[i+1][j+1].

    Try making dp matrix and dry run the code against some sample test cases, you will surely get it. Correct me if I'm wrong :P

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In the Hungarian implementation of Problem C, can anyone provide a general code that also includes finding which employee was allotted which job ? ( or in this case what was the final T for all input values) Thanks.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

for B i used so simple approach and i have no proof of it but somehow it worked . if someone knows please tell me too. just counted max(adjacent count of(0) , adjacent count of (1)) = answer... thats it.. May be we need to do work when something is consecutive , this what i thought while solving

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

    I think in the editorial it is proved. Actually adjacent count of(0)==adjacent count of (1) if you link the a[0] with a[n-1]. So the answer is sum(s[i] == s[(i+1)%n]) / 2

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain the second proposal in B's editorial which says there will be equal pair of 0's and 1's if we add 1 to the left and 0 to the right

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

    Either the no. of consecutive 0 pair and 1 pair are equal already or in the other case if no. of 1 pair is more than it could be only one more than the no. of 0 pairs and both ends will have 0 same for more 0 pairs than 1 pairs (I am getting this intuition) . I think this can be proved by using the fact that no. of 0s and 1s are equal, but didn't tried to prove yet. Sorry for bad english.

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

There's a simpler dp for problem F that doesn't require any optimization. The state is just $$$dp[i]$$$, which is just the number of ways in which we can choose fisherman $$$i$$$ to be happy (again, we have the fishermen sorted in non-decreasing order). The overall running time is $$$O(n^2)$$$.

My submission.

If you've got any doubts about what's going on here, feel free to ask :)

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

    I don't understand anything in there, can you explain it?

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      Yeah, my bad. I should've realized that code is hard to read. I'll try my best to explain it.

      Firstly, the fishermen are sorted in non-decreasing order.

      Secondly, $$$smaller[i]$$$ is the number of $$$j < i$$$ such that $$$2 * a[j] > a[i]$$$. These are fisherman that we cannot place to the left of $$$i$$$ should we choose $$$i$$$ to be a happy fisherman. When I say some $$$j$$$ belongs to $$$smaller[i]$$$, it just means that $$$j < i$$$ and $$$2 * a[j] > a[i]$$$.

      Thirdly, when we have reached any state $$$i$$$, we have already placed all elements $$$j$$$ such that $$$j \le i$$$ excluding the elements which belong to $$$smaller[i]$$$, because as stated before, these are elements that we cannot place in front of $$$i$$$, so we must decide their positions later on after choosing some other happy fisherman (after changing maximums i.e. transitioning to another state).

      From here, I will describe the transitions in the dp ($$$dp[i]$$$ is the number of ways in which we can make fisherman $$$i$$$ happy). $$$i$$$ will denote the current state we are in, and $$$j$$$ the state we want to transition to. ($$$i < j$$$).

      When we make this transition, we place element $$$j$$$ in the first unoccupied position, and so there is only one way to place element $$$j$$$. The reason the first unoccupied position is always given to $$$j$$$ is because all the other elements that we are yet to be placed can only come after $$$j$$$, which in turn is because we cannot place it directly to the right of $$$i$$$ (either because they belong to $$$smaller[i]$$$ in which case we will get a content fisherman, or because they are just larger than $$$i$$$ and would result in a change in maximum).

      The other elements that we can place (and have to place) when making a transition from $$$i$$$ to $$$j$$$ are those belonging to $$$smaller[i]$$$ and those strictly between $$$i$$$ and $$$j$$$ but not belonging to $$$smaller[j]$$$. Let the number of such elements be $$$count$$$. Now we have some number of free positions that hasn't been occupied yet. This number is exactly $$$n - i + smaller[i] - 1$$$ (because we have already placed all elements before $$$i$$$ except for those belonging to $$$smaller[i]$$$, and have also placed $$$j$$$).

      We can freely place all $$$count$$$ elements in any order we wish in these positions. The variable $$$factor$$$ basically gives the number of ways to do this. We pick exactly $$$count$$$ of the free positions, and then we can freely permute the order of the fishermen in those positions, thereby giving what you see in the code.

      Then we just sum over all valid $$$j$$$ (i.e for all $$$j$$$ such that $$$a[j] \ge 2 * a[i]$$$) for each $$$dp[i]$$$ thereby giving an $$$O(n^2)$$$ solution. The answer is just $$$dp[0]$$$ (according to how I've implemented it), and by default I take $$$a[0] = 0$$$.

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Problem F is solvable in nlogn. Here is the code link https://codeforces.com/contest/1437/submission/96998991.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it -10 Vote: I do not like it

    You just need to see the minimum requirement of the customer. Your main motive is to sell more cans to the customer.For that you just need to check if(r<l*2) and if the condition satisfies then you sold the customer more cans and you are profitable. Here is my code you can see for referral.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I would really appreciate an explanation for Problem A. I don't understand the one provided.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I can not understand the editorial of problem A,someone please explain in more detailed way.

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

    For a continuous interval modulo operation, the result is continuous.

    So just let a = r + 1 and check if l >= a / 2

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

    You just need to see the minimum requirement of the customer. Your main motive is to sell more cans to the customer.For that you just need to check if (r<l*2) and if the condition satisfies then you sold the customer more cans and you are profitable. Here is my code you can see for referral.

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

    Our main task is to find a number(a), such that, (l)mod(a),(l+1)mod(a),...(r-1)mod(a),(r)mod(a) is >= a/2. You want to maximize the result of mod operation, now a mathematical fact, if you have a number, say 8 and you want to choose another number (a) for which (8)mod(a) is max...what will you choose?? You will get max value when a is strictly greater than 8, for example (8)mod(9)=8, (8)mod(10)=8...so on. Imagine if you get a range (l,r)... Eg: (6,9) and you applied the above idea and chose a=10, (6)mod(10) = 6, and 10/2 =5, clearly (6)mod(10) is greater than 10/2, so the answer in this particular case is "YES". But what if you get a range (6,12) you applied above idea again and chose a=13, (6)mod(13)=6, and 13/2 is 6.5, which makes (6)mod(13)<13/2, so the answer in this case is "NO". Now to sum it up, the min value of (a) you can choose is such that the half of (a) is exactly equal to l, l=a/2 or a=2*l. also this (a) must be strictly greater than r, so that you get max value of (r)mod(a)... therefore we come up with this condition, r<a, r<2*l.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Solution for A in C++ C++ code

Soltuion for B in C++( Much simpler solution than in editorial) Code of B

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey guys, If it's okay with you guys I have created a telegram group to upsolve problems faster and get experience from other coders to learn things really fast. In the end, it's all about new techniques and different perspectives to solve the same problem so why not make a small group of friends to discuss problems after contests and random problems too. I think this way we would learn really fast and would able to improve our rating faster. Join this group if you think it's worth it. Join Group Here

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem E's editorial i could not understand the part a[i] -= i; can anyone explain it to me ? thanks in advance !!!

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

check out for the simple approach for B submission

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

    Can you please explain the idea behind that code? Thanks in advance.

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

In D, what we exactly needed to do? My approach:-

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

    We will not increase depth every time when v[i]<v[i-1]. We have to find the minimum depth.

    So if there are more nodes in the above level, we can just switch to another node (the node which is a sibling of the parent node).

    We increase the depth only when there is no node left with zero child in the above level.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    You can attach multiple nodes under a single node.
    You can also use multiple nodes of a single level to this.
    For example, 1 5 6 7 2 4 3
    Here, we can do this,
    Level 0 = 1
    Level 1 = 5 6 7
    (3 of them joined to node 1)
    Level 2 = 2 4 3 (2 joined to 5, 4 joined to 5, 3 joined to 6)
    But your code does this wrong.
    It will increment c when 2 < 7, so current c = 2.
    Then when it sees 3 < 4, again it will increment c and c becomes 3.
    But we could have attached this 3 to a node from the level 1 as we had more nodes in it.

»
5 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Problem A was rated 800. Is it a joke? I know it's a one liner, but just look at the number of people solved it during the contest. This problem is at least 1000. Probably 1100. People got angry because of the div. 4 rating inflation and now they increased the difficulty of all div 2 contests leaving the problem rating as before. Amazing job, guys.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the "slope trick" mentioned in the editorial of problem c. I do get the o(n^2) solution. The o(nlogn) solution seems to be interesting

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Problem B was too tricky for div2 B..

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello Everyone Can someone help me in understanding the hungarian implementation used in problem C I understood the algo but the code is just not striking if someone could help me with this code because this one is very smaller than any other available by google search.

Can someone define the use of all the arrays/ vectors used in the hungarian function Thank You

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Any idea how to solve G using Suffix array?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why we are sorting in Chef MonoCarp Problem?

»
5 weeks ago, # |
Rev. 2   Vote: I like it -7 Vote: I do not like it

include <bits/stdc++.h>

using namespace std;

int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); // your code goes here long long int t,n,a[200009],i,j,c,x,l,r; cin>>t; for(j=0;j<t;j++) { cin>>n; for(i=0;i<n;i++) cin>>a[i]; dequeq; dequep; c=0; p.push_back(a[0]); q.push_back(a[0]); a[n]=LLONG_MIN; for(i=1;i<=n;i++) {

if(a[i]>a[i-1])
        {
            q.push_back(a[i]);


        }
        else
        {
            q.pop_front();
            p.pop_front();

        }
        if(p.size()==0)
        {
            if(i!=n)
            {
            for(x=0;x<q.size();x++)
            {
                p.push_back(q[x]);
            }
            }
            q.push_back(a[i]);
            c++;
        }

    }
    if(p.size()!=0)
    cout<<c+1<<"\n";
    else
        cout<<c<<"\n";
}
return 0;

} Can someone help, why my code for problem D failing?please provide a test case where it fails?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the time complexity of Hungarian algorithm?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody give a neat, clear, and detailed explanation for the B problem (understandable for beginners)

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

    See the problem in a string is 00 or 11 coming somewhere. Now if you choose the substring like it has one 0 at one end and 1 at another. Like in the string if you choose and substring with end like above. 1110100100 like here 11/1010/0100 the substring 1010 if rotated will give 1101010100 . If we choose the substring with ends like these we can reduce the count of 11s and 00s with 2.

    And see after rotating the substring the count of 11s and 00s is reduced exactly by 2. So till after rotation we still have some 11s and 00s left we can again use a substring with such ends and rotate which will again reduce conut by 2. Just in case we are left with something like 0110 we will need one more switch and so the given algo works

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

And we can always reach this lower bound, by pairing 00 with 11 or with left/right border of s What Does This Mean Can Someone please elaborate

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

    See the problem in a string is 00 or 11 coming somewhere. Now if you choose the substring like it has one 0 at one end and 1 at another. Like in the string if you choose and substring with end like above. 1110100100 like here 11/1010/0100 the substring 1010 if rotated will give 1101010100 . If we choose the substring with ends like these we can reduce the count of 11s and 00s with 2.

    And see after rotating the substring the count of 11s and 00s is reduced exactly by 2. So till after rotation we still have some 11s and 00s left we can again use a substring with such ends and rotate which will again reduce conut by 2. Just in case we are left with something like 0110 we will need one more switch and so the given algo works

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For Problem C, i used greedy approach by looking at the tag which is on the problem statement. But greedy actually don't work. In that case, are people above 1900 misleading with tags or is there actually a greedy solution for problem C ? Please let me know. Thanks.

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

    I suppose that it's rather difficult to write a right greedy solution for this problem. I tried to write some of them but with different ideas, also i tried to combine but it didnt work, too

    So after that I hoped to find greedy solution in top50 of the round but nobody did it. only dp and graph. So I suppose there is no greedy solution

»
5 weeks ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Hello! Can somebody send the classical venger algorithm code? P.s I saw the venger algorithm in solution, but, to tell the truth, it was difficult to understand it for me. Thanks!

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The B solution is so precise.I learn a lot from it!

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain the first approach of B. Please.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain the logic of DP in C problem (beginner friendly). Not able to understand the editorial properly . Thanks !

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

    You can have a look at my submission..It is commented and easy to understand I guess.

    C
    //Think simple yet elegant.
    #include <bits/stdc++.h>
    using namespace std;
    #define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define ll  long long
    #define all(v) v.begin(),v.end()
    #define ff first
    #define ss second
    #define pb push_back
    #define mp make_pair
    #define pi pair<int,int>
    #define REP(i,n) for(int i=0;i<n;i++)
    const ll maxn=100005;
    const ll mod=1e9+7;
    
    int main(){
    	fast;
    	int q,n,i,j,k;
    	cin >> q;
    	while(q--){
    		cin >> n;
    		vector<int> t(n);
    		for(i=0;i<n;i++)cin >> t[i];
    		//dp[i][j] -> min cost of taking out a total of i dishes uptil j minutes.
    		//We take out the current dish i at time j -> dp[i][j] = min(dp[i][j],dp[i-1][j-1]+cost);
    		//The "cost" should also be optimal as such. Else there is no point in doing dp knowing that some better cost exists.
    		//In this case such an optimal cost exists when we sort t.
    		//We dont take out the current dish i at time j..so we have processed i-1 uptill time j AND j-1. -> dp[i-1][j] = min(dp[i-1][j],dp[i-1][j-1]);
    		//ans would be min(dp[n][x])
    		sort(all(t));
    		vector<vector<int>> dp(n+1,vector<int>(2*n+1,1e9));
    		dp[0][0] = 0;
    		for(i=1;i<=n;i++){
    			for(j=1;j<=2*n;++j){
    				dp[i][j] = min(dp[i][j],dp[i-1][j-1] + abs(t[i-1]-j));
    				dp[i-1][j] = min(dp[i-1][j],dp[i-1][j-1]);
    			}
    		}
    		int ans = 1e9;
    		for(j=1;j<=2*n;++j)ans = min(ans,dp[n][j]);
    		cout<<ans<<"\n";
    
    	}
    }
    	
    
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can Someone help me to find what is wrong with this solution 97843215 for problem E

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

G let me review the AC automaton... but TLE on test 70 :(, maybe cuz the pointers in my ugly code spend too much time...

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

    Passed! I used a heuristic method: maintain a pointer "nex", which is the closest node in the fail tree that is the end of some $$$s_i$$$. When initing the fail pointer of AC, the nex pointer can be inited by the way. Then, we can jump faster. I don't know whether the worst complexity is still $$$O(q\sqrt n)$$$, but it works.

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

For problem G, why is "Thus, that's bounded by the square root of the total length." true? (Actually, I'm also confused by what's meant by "that").