ch_egor's blog

By ch_egor, 2 years ago, translation, In English

Thanks for the participation!

1649A - Game was authored by Jeffrey and prepared by gop2024

1649B - Game of Ball Passing was authored by low_ and prepared by low_ and gop2024

1648A - Weird Sum was authored and prepared by cookiedoth

1648B - Integral Array was authored by grphil and prepared by shishyando

1648C - Tyler and Strings was authored and prepared by Tikhon228

1648D - Serious Business was authored and prepared by ligaydima

1648E - Air Reform was authored and prepared by grphil

1648F - Two Avenues was authored by I_love_myself and prepared by isaf27

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +62
  • Vote: I do not like it

| Write comment?
»
2 years ago, # |
  Vote: I like it +37 Vote: I do not like it

It would also be interesting to see a tutorial on how to recreate test 61 from Div1C (the one that breaks ++ans without taking mod at the end).

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

    really really curious about this case. I didn't use such algorithm so didn't meet this problem.

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

    I'm not an author, but if I needed to generate such test, that's how I would do it

    Essentially you just need to find some group of possible tests such that there exists a test with a needed property and you can calculate an answer in $$$O(1)$$$, then you can generate random tests of this type until you find the one that satisfies the condition.

    For example, in this problem, consider $$$s = [2] \times a + [1] \times b$$$, $$$t = s + [1]$$$. Then it almost works, except the answer is $$$\binom{a+b}{a}$$$, which can't be zero. So instead of this $$$t$$$, take a string, which is lexicographically previous: $$$[2]\times (a-1) + [1] + [2] + [1]\times b$$$. Then the answer is $$$\binom{a+b}{a} - 1$$$ and now you can generate random $$$a$$$ and $$$b$$$ until you get answer $$$0$$$.

    Also maybe there is a faster way to find $$$a$$$ and $$$b$$$ such that $$$\binom{a+b}{a} = 1$$$, or maybe there is another type of tests where the formula is easier and you can directly find parameters for it without random generation, but it's not needed here

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

      Thanks for the writeup! I've finally got around to trying this approach myself. After five minutes of random generation, the smallest value I got was 114 for a=4706, b=11894. Maybe I should've run it in C++ instead of Python, but 114 is good enough anyway: we can just call prev_permutation 114 times and obtain the test. :)

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

        Since the expected number of random generations is $$$\frac{mod}{2} \approx 5\times 10^8$$$, it's definitely better to pick faster language. For example, this code in C++ performs $$$10^9$$$ iterations in around 30 seconds in ideone and gives $$$a = 54993$$$, $$$b = 97144$$$

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

If you are/were getting a WA/RE verdict on any of the problems from this contest, you can get a small counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table to increase/decrease the constraints.

Div 2

Div 1

If you are not able to find a counter example even after changing the parameters, reply to this thread, mentioning the contest_id, problem_index and submission_id.

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

    This is great! Helped me find why my D submission was failing. Just one line change and AC :_)

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

    loved it brother

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

Can I ask that why we can prove the statement in Div2B ?

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

    Consider the $$$i$$$ corresponding to maximum $$$a_i$$$. By letting $$$i$$$ pass the ball to any other person, and these people then pass back to $$$i$$$, we can maximize the $$$i$$$'s passes. And if even in that case, the passes don't meet his requirement, one ball can definitely not complete the task, and the extra ball we need is the rest passes required. However, if we can use all the passes or even the passes is not enough, we can turn to another person and keep the process, which will make one ball acceptable.

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

      Excuse me but can I ask that for the condition when the maximum is not enough, by saying turn to another person,do you mean the the maximun person among all the people that are left after eliminating the first one? In this case don't we have to prove that the rest of the people still requires the condition that the maximum is not enough?

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

        if $$$max(a) \times 2<sum(a)$$$, we also let $$$i$$$ that has maxinum $$$a_i$$$ pass to any other person called $$$j$$$, then let $$$j$$$ pass to a person neither $$$i$$$ nor $$$j$$$. We continue to do that until $$$max(a) \times 2=sum(a)$$$, then do what he said, the whole process also only cost one ball.

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

          Now I get it,Thank you so much!

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

In 1D/2F, why you define $$$dp_i$$$ as the maximum profit for going from $$$(1,1)$$$ to $$$(2,i)$$$, but relax it with $$$\min$$$? I'm completely confused about that. Could anyone please provide a further explanation of the $$$dp_i$$$ qwq

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

    I'm also confused about this place.

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

    Excuse me but when we relax $$$dp_i$$$ by $$$dp_j$$$, maybe we should pay attention to $$$pref_{1,i}-pref_{1,j}$$$, or I misunderstand the algorithm?

    Sorry for my poor English.

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

      Well, seeing your comment make me completely confused now and discover some problems with my idea, so I deleted it.

      But I think the $$$dp_i$$$ may have the similar meaning to the $$$s_i$$$, so the $$$pref_{1,i}-pref_{1,j}$$$ is calculated in the final step?

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

        In my opinion, when we relax $$$dp_i$$$ by $$$dp_j$$$, that means we move from $$$(2,j)$$$ to $$$(2,i)$$$, besides $$$s_i$$$ means moving from $$$(1,1)$$$ to $$$(2,i)$$$, if $$$dp_i$$$ is similar to $$$s_i$$$, then the way we relax $$$dp_i$$$ maybe only unlocked the segment $$$[j+1,i]$$$ ,but didn't moved from $$$j$$$ to $$$i$$$. Sorry for the parhap incorrect grammars.

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

          From my point of view, in the process of calculating the answer, we take $$$f_j$$$ into considering, which represents for the correct sum of 3rd floor and the prefix sum of the 2nd floor. So in the $$$dp$$$, we should maintain the left side of the segment we passed in the 2nd floor to correctly get the final the $$$a_{1,i..j}$$$.

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

            Oh sorry for my mistake, I forgot the $$$f_i$$$! Then your idea to relax $$$dp_i$$$ may be right. Thank you!

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

              Maybe they are right, but I can't be that sure. :(

              Anyway, thank you for discussion with me!

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

    Yes, you are right. We fixed this mistake, sorry.

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

The only case where the resulting string $$$x$$$ can be lexicographically less than $$$t$$$ which we will not count, is when it is a prefix of the string $$$t$$$ but has a shorter length.

CMIIW but for this statement in editorial div 2E/1C why do we need to "not count" this case?

For example when $$$x = "abc"$$$ and $$$t = "abcd"$$$, $$$x$$$ is a prefix of $$$t$$$ and it has a shorter length. But isn't in this case, $$$x$$$ is lexicographically smaller than $$$t$$$?

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

    Maybe you misunderstand the tutorial.

    By saying "not count", he don't mean that the answer don't include the case, but mean that the algorithm can't take the case into considering.

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

I tried to prove problem B during the contest but failed. Until now, I don't know how to prove it. Can anyone help me, please.

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

Plz show editorial code for Problem C (Div.2)

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

in questions : "Game of Ball Passing" who can prove that 2 * max(a) <= sum(a) why answer is 1

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

    Consider this expression as max <= sum — max. Now it's obvious for an optimal solution, if we can complete the passes of the player with max passes, all other players' passes have been completed by that time. So consider the following pattern of passes:

    ____ M ____ M ____ M ____ M ......... ____ M

    The above pattern represents the order in which the ball was passed. Here, M represents the player who made max passes. Now obviously, we will want to have atleast one player make a pass between two consecutive passes by the player M. And we can notice that there are max blanks available to fill in. Also, the value sum-max represents the total number of passes made apart from the player with max passes. Therefore, we can say that if remaining passes(sum-max) >= number of blanks(max), then all our blanks can be filled easily and the entire pattern will represent a single chain of passes. However, if sum-max < max, then some blanks will remain empty, which would mean that the chain of passes broke at that point, and we needed an extra ball to begin a new chain.

    I hope you understood the point. Try working out some examples by this logic and you'll get the logic

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

    Actually, I did not know how to prove, but my gut feeling told that answer is either max(1,2*mx-s) or 0. F****** adhock

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

Remember that $$$O(10^{6}\sqrt{10^{6}})$$$ $$$+$$$ $$$10^{6} * log(10^{6}))$$$ gets AC in 2 seconds with $$$C++$$$ $$$20$$$ ! https://codeforces.com/contest/1648/submission/148611843

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

    Are you sure ? mine didn't get accepted

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

      Don't use push_back for storing the non-duplicate numbers which are in your array because sometimes it may leed to $$$O(n)$$$ in each push_back, Write a vector of size n like this $$$vector <int> a(n)$$$ and read input and then use this code :

      sort(a.begin(), a.end());
      a.erase(unique(a.begin(), a.end()), a.end());
      
      

      This will store the non-duplicate numbers in a good time.

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

      My submission : 150868540 Which has $$$O(C√\overline{C})$$$ doesn't work too, can anyone explain why it fails? Or is it meant to fail since it only accepts $$$O(ClogC)$$$?

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

getting tle on test 9 for problem E help https://codeforces.com/contest/1649/submission/148661424

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

For problem B(div2), how to prove "If max(a)⋅2≤sum(a), we can always prove that we can only use one ball."?

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

I'm trying to understand the editorial to div1D, could someone explain to me what the term 'relax' means? More specifically, I'd like more detail at:

"The calculation of dp is as follows: for all i look through each segment, which ends at i, and relax $$$dp[i]$$$ with $$$\max_{l−1≤j<i}dp[j]−k$$$ . It can be calculated using segment tree."

Is this done in complexity N^2 * log(N) ?

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

Testcases of div2 D seems to be weak, $$$\mathcal{O}(n\sqrt C)$$$ combined with randomization could get Accepted

Could anyone provide a hack? I can't find one myself. Thanks a lot

submission: https://codeforces.com/contest/1648/submission/148684614

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

The tutorial 1D/2F is confusing. For example, why it write $$$dp[i]+f[j]+k$$$ at first line last part, then relax the answer by $$$dp[i]+f[j]-k$$$?

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

    And when we relax the overall answer, how can we get the $$$k$$$? Besides both $$$i$$$ and $$$j$$$ are uncertain.

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

in D1 D/D2 F, I understood the above part , but after calculating all the DP,

in last part editorial says "So we can bruteforce the rightmost segment in our answer and relax the overall answer with

$$$maxl≤i≤j≤r$$$
$$$dp[i]+f[j]−k$$$

."

How do we calculate

$$$maxl≤i≤j≤r$$$
$$$dp[i]+f[j]−k$$$

without making it O(n^2) with all values of

$$$i<=j$$$
$$$pair(i,j)$$$
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Not sure if you figured it out. I finally understood by reading other's submission (https://codeforces.com/contest/1648/submission/148574211).

    Let's state the sub-problem this way: given two arrays $$$a$$$ and $$$b$$$, we are to answer queries $$$(L,R)$$$ with $$$max_{L<=i<=j<=R}{a_i+b_j}$$$.

    Suppose we already have a segment tree, and on each tree node (corresponding to interval $$$[l,r]$$$), we maintain three values: $$$maxa$$$ (the maximum of $$$a$$$ in this interval), $$$maxb$$$ (the maximum of $$$b$$$ in this interval), $$$max$$$ ($$$max_{l<=i<=j<=r}{a_i+b_j}$$$). $$$maxa$$$ and $$$maxb$$$ can be calculated straightforwardly.We will come to $$$max$$$ later.

    Now let's consider how to answer queries, and this is the tricky part. It's using the property of the recursion. In the example below, we are answering the query $$$[0,6]$$$ on the given tree. Boxes next to the tree node mean the interval, green means it's not matching the whole interval on the node, and red means it is matching. You can see we process, in order, $$$[0,3]$$$, $$$[3,5]$$$, $$$[5,6]$$$. So we can maintain a running variable, of the maximum values of $$$maxa$$$ seen in the nodes we already processed. The pseudocode is:

    void query(
      int c /*index*/,
      int cl, int cr, /*the interval of the node*/
      int l, int r /*the interval to query*/
      int& runningMaxa,
      int& result
    ) {
      if (cl + 1 == cr || (l == cl && r == cr)) {
        result = max(result, v[c].max);
        result = max(result, runningMaxa + v[c].maxb);
        runningMaxa = max(runningMaxa, v[c].maxa);
        return;
      }
      int mid = (cl + cr) / 2;
      if (l < mid) {
        query(c * 2, cl, mid, l, min(r, mid), runningMaxa, result);
      }
      if (r > mid) {
        query(c * 2 + 1, mid, cr, max(l, mid), r, runningMaxa, result);
      }
    }
    

    When we are at node $$$[3,5]$$$, at this moment, $$$runningMaxa$$$ is the maximum of $$$a$$$ in $$$[0,3]$$$. So the above logic give us $$$max_{0<=i<=j<=3}{a_i+b_j}$$$, $$$max_{3<=i<=j<=5}{a_i+b_j}$$$, and finally $$$max_{0<=i<=3, 3<=j<=5}{a_i+b_j}$$$. You can see it's exhaustive for all possible pairs.

    Query Example

    And for maintenance of $$$max$$$ on nodes, you just do the same as querying when propagating from child to parent.

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

Can someone provide a proof of how Div 2 D has time complexity of C log C according to editorial?

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

    For every $$$r$$$ you check each $$$y \leq \frac{c}{r}$$$. In other words you do at most $$$\frac{c}{1} + \frac{c}{2}+\cdots+\frac{c}{c} = c\cdot h_c$$$ iterations. $$$h_c$$$ is the harmonic series. Search it up, it's a very important series which is almost equal to $$$\log c$$$ as $$$c$$$ grows large.

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

Can someone explain why I am getting TLE in div2 D prob https://codeforces.com/contest/1649/submission/148733037

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

    Don't reassign the whole arrays prefix, exist in the test cases. That's $$$t\cdot 2 \cdot 10^6$$$ operations. That's why there is a bound on $$$C$$$.

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

      Thanks. The changes I did were removed memset(prefix , 0 , sizeof prefix); and did prefix[0] = 0; But it will still give TLE. I then made int exist[1000000+1]; to bool exist[1000000+1]; which passed.

      I still don't understand why changing exist from int to bool got me AC.I know bool takes less memory and is faster than int, but is the difference significant enough to give TLE??

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

One interesting approach & implementation to Div1C/Div2E without segment tree or fenwick tree, using PBDS We don't need to do anything for repetition of elements, we can simply compute the answer considering every number to be unique. What I mean is let's say we want to permute 1 2 2 2 3 3, we can consider this as 1 2a 2b 2c 3a 3b, then once we have permuted which is 6!, we can then divide the answer by factorial of the repetitions, so at every step we need not bother about it and we can do this step just once at the end. So now at any index i in b[i], we will see how many smaller elements we have, and what is the count of same elements. for smaller elements we can place any one from the options, and permute the rest array. and for equal elements we can select any one and find the answer from the next index, this can be done using pbds and for any element we need to know count of elements smaller than it.

Here is my code for the same, you can reply if you want any clarification: 148711861

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

In the problem integral array how can i check for the existence of x in constant time ?

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

    It is done by considering array $$$cnt_x$$$ — the amount of occurrences of $$$x$$$ in $$$a$$$, and prefix sums for that array.

    By using prefix sums.

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

      I'm kind of a noob here, so how can I do that using prefix sum ?

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

        We create an array named sum, and let each $$$sum_i=sum_{i-1}+cnt_i$$$, then this is prefix sum.

        for integers $$$i<j$$$, if $$$sum_{i-1}=sum_j$$$, then there is no numbers in $$$[i,j]$$$, because that means all $$$k$$$ in $$$[i,j]$$$ has $$$cnt_k=0$$$.

        My English is poor, hope it could be understood.

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

The editorial of 1F said

It is possible to recalculate this segment tree with $$$O(n+k)$$$ updates during the dfs tree traversal.

But I don't understand it. Can someone tell me how to implement this? Thanks a lot.

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

    Now I have understood it and got accepted.

    Its main idea is, we maintain the number of chains that cover $$$e_2$$$ but not cover $$$e_1$$$ (then we can calculate the answer for $$$e_1$$$ and $$$e_2$$$ since we know $$$c_{e_1}$$$ and $$$c_{e_2}$$$), and we only need to make sure that this value is correct for $$$e_1$$$ which $$$h_{e_1}=h_{e_2}$$$. So we can show that for some chain there is only $$$O(1)$$$ $$$e_2$$$ that will update the segment tree.

    The Russian editorial has explained the details of how we can find these edges that will update the segment tree. If you are good at Russian or you have a nice translator, I advise you to read the Russian editorial. XD

    Thank isaf27 very much for his guidance.

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

Is there anyone accepted 1D by divide and conquer and minimal path? The complexity is $$$O(n\log^2n)$$$.

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

https://codeforces.com/contest/1648/submission/150657004 Why doesn't this work? I understand that time complexity is worse than editorial, but I probably would've been able to figure that out if I TLE'd; instead, it's a WA on 2933rd token and I have no idea why (for TC 3 too). Isn't this identical logic to editorial, just using sets instead of a precalc array?

edit: nvm, me being a noob in c++