awoo's blog

By awoo, history, 10 months ago, translation, In English

1845A - Forbidden Integer

Idea: BledDest

Tutorial
Solution (awoo)

1845B - Come Together

Idea: adedalic

Tutorial
Solution (adedalic)

1845C - Strong Password

Idea: BledDest

Tutorial
Solution (awoo)

1845D - Rating System

Idea: BledDest

Tutorial
Solution (Neon)

1845E - Boxes and Balls

Idea: BledDest

Tutorial
Solution (awoo)

1845F - Swimmers in the Pool

Idea: adedalic

Tutorial
Solution (adedalic)
  • Vote: I like it
  • +114
  • Vote: I do not like it

»
10 months ago, # |
  Vote: I like it +41 Vote: I do not like it

i learnt a lot from this contest. Thanks a lot for such a educational one.

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you share your learnings

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

    please enlighten me what you learnt?

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

    This is a very interesting competition. No matter how you look at the Harbour Space University competition, they are all very interesting. Every awoo competition and its teams are useful. Thank you awoo and your team!!!

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

I could just solve 2 questions but the the problems were really educational. Thanks for the preparation.

»
10 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Maybe you shoule've set n,k <= 2500 or sth for problem E, because this way many were able to make the n^2k pass while others (myself included) didn't even try it even with the idea in mind

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think the problem is that even with the current constraints, solutions that run in O(N×K^1.5) aren't guaranteed to pass.

    During the contest I submitted a O(N×K^1.5) solution that used a std::unordered_set which was too slow (admittedly, std::unordered_set is known for having a high constant factor). After the contest I rewrote it to use only arrays, but even then it still takes 4.773 seconds, which is quite close to the 5 second time limit: 211663856.

    Honestly there isn't a lot of fat to trim there. So I don't think they could have increased the bounds by much without failing reasonable solutions.

    Is the problem in its current form even solvable in a language other than C++? Maybe Java?

    • »
      »
      »
      10 months ago, # ^ |
      Rev. 6   Vote: I like it +8 Vote: I do not like it

      I tried submitting your code. Submission 2, 5 use #define int int64_t while submission 1, 3, 4 don't. I am not very sure as to which compiler should be used for which cases but from my past experience it feels like using 64-bit compiler for 64-bit maths is better.

      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh interesting! I had no idea that the “G++17” compiler ran in 32-bit mode, and I had been avoiding the “G++20” compiler because it mentioned ”winlibs” and I don't know what it meant so I was afraid it was Windows-specific somehow.

        It sounds like I should switch to using G++20 for all my submissions from now on! Thanks for the tip!

        • »
          »
          »
          »
          »
          10 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I am not able to understand anything about E the statement seemed simple but I am not able to understand anything about E can you please help ?

          • »
            »
            »
            »
            »
            »
            9 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Take a look at 211973366.

            This solution won't pass because it's too slow, but that's not the point. It is intended to show how to enumerate all the possible sequences that can be constructed with at most K moves, recursively.

            Once you understand this principle, the challenge is to rewrite the recursive solution as an iterative dynamic programming solution that runs within the time and space limits. This is fairly mechanical. If you don't know how to do this, you should read a dynamic programming tutorial first.

            • »
              »
              »
              »
              »
              »
              »
              9 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I still don't understand. Can you help? So you say that the sum of excess must be 0 at the end, but even in the example you've given at the start of your submission the sum is -1 + -2 + -1 + 0 + 0 + 1 + 0 = -3 which is not 0, although the numbers of balls in goal and in A are equal. Do I miss something?

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

                It's the final value of excess that must be zero, not the sum of the values. excess represents the number of balls pushed to the right (if positive) or borrowed from the right (if negative).

                I'll give you two detailed examples to explain the logic of the recursive solution (and them I'm giving up!)

                Let's say we want to transform A=[1,1,0,0] into B=[0,0,1,1]. Imagine the boxes are lined up in a row and I'm physically moving from the left to the right of the array, trying to make things right, keeping track of how many balls I have to carry from left to right (which is the minimum number of swaps I can do, since a swap moves a ball from bin i to i+1 or vice versa).

                Initially, I'm at index 0. A[0] = 1 but I want it to be B[0] = 0, so I pick up the ball (I now have 1 ball), and then I move to the right (moving 1 ball with me).

                I'm at index 1. A[1] = 1 but I want it to be B[1] = 0, so I pick up that ball too (I now have two balls), and then I move to the right (moving 2 balls with me).

                I'm at index 2. A[2] = 0 but I want it to be B[2] = 1. Luckily I have two balls, so I put one of them down here, and then I move to the right (moving 1 ball with me).

                I'm at index 3. A[3] = 0 but I want it to be B[3] = 1. I still have 1 ball left so I put it down, and then I move to the right, and I'm at the end of the array with no balls left.

                excess represents the number of balls I move to the right at each step, so excess = [1,2,1,0] and the total number of times I had to move a ball one space was 1 + 2 + 1 = 4.

                In that example, I only had to move balls to the right. What if I need to move balls left, let's say by transforming A=[0,0,1,1] to B=[1,1,0,0]? It's clear the optimal solution is to move the balls at A[2] and A[3] two spaces to the left each. I can use the same algorithm as above if I introduce the idea that I can borrow balls from the right. It looks like this:

                Initially, I'm at index 0 and A[0] = 0 but I want it to be B[0] = 1. Since I don't have a ball, I remember that I need one and move the right (I'm 1 ball short that I need to move from box 1 to 0).

                I'm at index 1 and A[1] = 0 but I want it to be B[1] = 1. Since I still don't have any balls, I remember that I need another one and move the right (I'm 2 balls short that I need to move from box 2 to 1).

                I'm at index 2 and A[2] = 1 but I want it to be B[2] = 0, so I pick up the ball. That's one of the balls I can pass to the left (throwing it in box 0), but I'm still 1 ball short as I move to the right.

                I'm at index 3 and A[3] = 1 but I want it to be B[3] = 0, so I pick up that ball. That's the last ball I needed to pass to the left (throwing it in box 1). So now I can move to the right (at the end of the array) and I have no balls left nor am I short any balls, so I've found a solution.

                In this example, excess = [-1,-2,-1,0], the negative numbers representing the number of balls I was short. Just like before, the total number of times I had to move a ball one space was |-1| + |-2| + |-1| = 4, except the balls moved to the left instead of to the right.

                (I didn't prove that this algorithm is optimal, but it's not too difficult to convince yourself that it is.)

                If the above explanation isn't enough to understand the problem, I suggest you let it go for now, practice on other problems, and come back to it later.

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

                  Thank you very much for such a detailed explanation. Now I get it

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

yaya, nice to see the nk^1.5 solution, was wondering about that from seeing all the fast submissions

»
10 months ago, # |
  Vote: I like it +111 Vote: I do not like it

I had a different solution for E that runs in $$$O(n^2 \sqrt{k})$$$ and is adapted from the slow dp:

Let $$$m$$$ be the number of balls and let $$$pos_i$$$ be the position of the $$$i$$$th ball. Then, we can calculate $$$dp[i][k][j]$$$, the number of ways to put the first $$$i$$$ balls in the first $$$j$$$ bins, the cost is $$$k$$$. I order like $$$i, k, j$$$ for cache purposes. This is just a standard dp, where the transitions are $$$dp[i][k][j] = dp[i][k][j-1] + dp[i][k-|pos_i-j|][j-1]$$$.

We can observe the following fact: the position of the $$$i$$$th ball is limited to the range of $$$[pos_{i-\sqrt{k}-1}, pos_{i+\sqrt{k}+1}]$$$, where negative indices are filled with 0 and indices above $$$m$$$ are filled with $$$n$$$. This is true because if the ith ball went beyond this range, at least $$$\sqrt{k}+1$$$ balls would have to move at least $$$\sqrt{k}+1$$$ distance.

This optimization is important because the distance between balls is roughly $$$n/m$$$, so the size of the average range among the balls is $$$\sqrt{k} \cdot n/m$$$. Over all of the balls, and over all costs, the total number of positions we will look at in our dp will be $$$O(m \cdot n \cdot (\sqrt{k}\cdot n/m)) = O(n^2 \sqrt{k})$$$.

For the implementation, we can store a table $$$range[i][k] = [pos_{i-\sqrt{k}-1}, pos_{i+\sqrt{k}+1}]$$$, which is the range of $$$j$$$ that $$$dp[i][k][j]$$$ is calculated for. The dp values before this range are 0, and the dp values afterward are just the dp value of right endpoint of the range. This allows us to avoid traversing all $$$j$$$ from 1 to $$$n$$$ for every $$$i, k$$$, and only traverses the ranges that we care about.

Submission: https://codeforces.com/contest/1845/submission/211638320

»
10 months ago, # |
  Vote: I like it +1 Vote: I do not like it

can C be done using digit DP?

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

Why I am getting WA on D? Can someone Help me? Tried 2 different approaches.

Approach 1 : https://codeforces.com/contest/1845/submission/211638397

Approach 2 : https://codeforces.com/contest/1845/submission/211644844

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

    In both the approaches, you are trying to find the highest possible net rating before the last time there is a drop (i.e., a[i] is negative). However, this might not always give the correct answer.
    Consider the test case:
    1
    4
    3 -2 7 -1
    Here, the answer would be 3, since by fixing k=3, you can achieve a final rating of 9. However, your approach returns k=8 as the answer, due to which the final rating would be 8 only.

»
10 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Why is the explanation for B so sub quality? No definition for bounding box, "since d(X,B)+d(X,C) is constant and equal to d(A,B) if X is in the bounding box. " Randomly stating facts

sad

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

    Another idea for B is to split the problem regarding the X-axis and the Y-axis and take the minimum out of the specific coordinates for the axis and add it to the answer if both are walking in the same direction. (after you've made A the origin).

»
10 months ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

Here's another solution for C. The idea is to count the #of unique valid passwords of length m in the password database. Then if the #of unique valid passwords is less than the total #of valid passwords, there is guaranteed to be at least one password that we can use for our answer. You can count the #of unique valid passwords of length m in the database using dp.

211486674

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

    i couldn.t understand your dp states and transition in your code. if u have time will u please explain edit: got it thanks

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

    great observation

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

Does anyone know of a good resource that explains how to use FFT to solve problems like 1845F - Swimmers in the Pool from scratch, i.e., without assuming I already know what a FFT is and how it applies to problems like this?

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

What's wrong in my solution for problem D, please help: https://codeforces.com/contest/1845/submission/211663257

»
10 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Some key observations in problem D:

  1. The value of K is one of the prefix values of the array (As it is clearly mentioned that, to get benefited player must achieve achieve a minimum of score 'K')
  2. We can go over all prefixes of the array and for each prefix value we again can compute the maximum score (N^2 solution)

From now on we try to reduce the complexity from N^2 to N

  1. The suffix of array having all positive elements will always contribute positive to the answer , for example, A = [-1, -1, 2, 2] then the suffix [2,2] (last two elements) will always be added to the answer no matter what prefix we choose (As there are no negative elements after them to reduce its value back to k)
  2. Lets call this suffix as confirmPos. Now the array can be divided into continuous subsegments based upon the signs of elements.
  3. Lets focus on two subsegments A, B. Such that Array = [....., A, B, confirmPos]. Now its clear that all elements in B are negative and all elements in A are positive let, pos = sum(A) & neg = sum(B)
  4. There are two cases
  • pos + neg < 0, this will contribute negative to the answer, so for the next iterations, neg = neg + pos; pos = 0.
  • pos + neg > 0, which essentially means their total contribution to the answer is always positive no matter what prefix we choose (As we are going backwards in array, we know there is nothing negative to reduce this value further more). Thus we can consider them as confirm positive thus, for next iteration, confirmPos += pos + neg; pos = 0; neg = 0;

These observations derive the fact that for index i

maximum answer by keeping k as pref[i-1] = pref[i-1] + max(0, pos + neg) + confirmPos

sorry for poor english, I tried my best to explain what I understood from the problem :)

Submission Link

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

    Nicely explained ! A question w.r.t editorials explanation in particular for D, they say the pfirst point where value goes less than k and last point where it goes below k is the sub segment we need to remove. But whatever that first point is which determines if the value goes below k, does that not also change what was the next point at which the value would go below k again ,I.e since we capped it to k subsequent positive operations would take the value higher and maybe it won't fall below K as it previously did ? Don't we need to simulate and see ?

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Nvm I figured it out , it relies on the fact that at the end of minimum subarray the rating is still K (else it wouldn't be min subarray it can be empty though), and the prefix before min subarray is maximum so you would want to retain that , also note minimum subarray has to be negative(sum total of it) so once you make sure you avoid this subarray the suffix left will only increase the rating from max prefix which you found to something bigger which is max possible at the end, so K will be max prefix.

      TL;DR avoiding minimum subarray sum will make sure prefix before it is preserved and only increase till the end.

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

Can anyone help me to remove the RE in 3rd Question

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

    It seems the ind might be -1. Try with the following case:

    1
    1
    2
    22
    22
    

    I have added an assert into your code and also fixed the indentation.

    Submission with Assert
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hello Sir, Can you explain these things to me or from where I can learn them; Basically, I never heard of "mdash" you used!!

      Thank You for your solution

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

        Those are formatting errors when I added the code in the comment. I have fixed them. Please have a look again. That's your code and I just added an assertion.

        • »
          »
          »
          »
          »
          10 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          the code is still giving WA

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

            That means the code is not giving RE which you originally requested, isn't it? Check your code, find out for which cases your code is not generating correct inputs and read the editorial if necessary. Have a great solving!

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

Hi can anyone explain why binary search on k does not work for D? I kept thinking of counterexamples but I cannot seem to find any.

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How will do you a binary search on k , it doesn't guarantee that if you would increase k it would only lead to maximum sum, it can so happen binary search skips parts on range of k which would contribute to maximum sum

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can someone please explain why using kadane's algorithm for Q. D. 'Rating System' is wrong? or is my idea correct but wrong implementation?

    My submission

    Thank you

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

      Kadane's algorithm is in fact right for the D problem.

      However, in your solution, you have made the mistake while selecting the value of K. By Kadane's algorithm, you are trying to find the most negative subarray in the given array. You can then select K to be the value before the start of that subarray. Your solution will fail when you get multiple negative subarrays. eg:

      1 8 -5 100 -5 -10 4 -10 -10 -10

      your mn will be set to -5 at the start and then the value to starting will be 3 instead of 2 and the solution will give wa.

      You can check this solution for Kadane's: 211474733

      Hope this helps.

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

Can someone please explain why using kadane's algorithm for Q. D. 'Rating System' is wrong? or is my idea correct but wrong implementation?

My submission

Thank you

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

Can anyone explain binary search solution to C?

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

I think the questions in this game are very good

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

Why the time limit of problem E is 5s?

211713164 My solution is $$$O(n^2k)$$$,it only executed 1029ms

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

Could someone explain the solution of second problem?

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    think of it this way, each of them has to travel a certain distance in the x plain and some dist in the y plain, and the order doesn't matter as long as at the end of the day each of them travels the dist. (x and y are independent). so it's optimal to take the common x distance and the common y distance and add one to it which is the initial square.

    if you took physics you can relate to vectors.

    here is my submission i hope it helps.

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah, it helped thanks a lot.

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

      Thanks! I struggled with this one, but your solution really makes a lot more sense than the editorial to me.

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

What's wrong in my solution for problem D, please help: https://codeforces.com/contest/1845/submission/211663257, which test case it is failing and what is the problem with my submission, pls help

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

Here is another idea for D: consider the following question: what the rating change will be (if we can simplify it) after applying a list of rating changes a[1], a[2], ... , a[n]. Observe that:

  • if a[i] is 0, delete it.
  • if a[i] and a[i+1] are both positive or both negative, merge them to a single item.
  • if a[i] is positive and a[i+1] is negative, merge them too.
  • if a[i] is negative and a[i+1] is positive, the change depends on k, so we keep both a[i] and a[i+1] unchanged.

After applying transformation above on initial rating changes list, the size of result list will be at most 2. So we can enumerate every index i, to check:

  • define rating is R[i] after rating changes from beginning to a[i];
  • set k = R[i];
  • with fixed initial rating and fixed k, apply following rating changes (a[i+1], a[i+2], ... , a[n]) to get final rating.
  • update overall result.

To get simplified rating change list for each index i, we can calculate backwards from index n to index 1.

Some of the results will be invalid, since for some R[i], the rating on previous steps may reach k (=R[i]) and then drop below k (=R[i]), so use R[i] as initial rating with k=R[i] is actually wrong. But in such cases the result got from the step that "reach k" will always be better, so we can just ignore such (wrong) cases.

»
10 months ago, # |
Rev. 6   Vote: I like it +3 Vote: I do not like it

Can someone please tell me why my solution is so slow, although it is accepted? I used $$$dp[i][j][k]$$$ =number of ways to store first $$$i$$$ balls in first $$$j$$$ boxes such that minimal cost for it is $$$k$$$. Transition looks like:
$$$dp[i][j][k]=dp[i][j-1][k]+dp[i-1][j-1][k-|pos[i]-j|]$$$ , there $$$pos[i]$$$ is position of $$$i$$$th ball on the beginning. Solution would be sum of $$$dp[m][n][i]$$$ for each $$$i$$$ of same parity as $$$k$$$,where $$$m$$$ is the number of balls. Also I used that for $$$i$$$th ball set of possible positions $$$j$$$ on which we can move it belongs to interval $$$[pos[i-\sqrt{k} -1],pos[i+\sqrt{k}+1]]$$$.
In this comment https://codeforces.com/blog/entry/117791?#comment-1042133 was explained why time complexity should be $$$O(n^2\sqrt{k})$$$. Most of solutions have runtime up to $$$1000ms$$$, but mine is more than $$$3700ms$$$, so I would be grateful if someone can tell me why is it so? This is my submission: https://codeforces.com/contest/1845/submission/211839395

$$$\textbf{Upd}$$$ I got it, only need to change from long long to int

»
10 months ago, # |
Rev. 2   Vote: I like it +18 Vote: I do not like it

I want to add something about problem F.

I didn't really understand what the P.S. in the tutorial for this problem means, maybe it is exactly what I want to say, then I am sorry.

I just wanted to say that I think that Möbius transform is too hard of a concept for situations as described in the problem. Here we have a situation where we have some array $$$a_i$$$ consisting of sums of answers over all divisors of $$$i$$$, and we would like to get the actual answer array $$$b_i$$$. So we know $$$a$$$ and we know that $$$a_i = \sum_{j \vert i} b_j$$$. In situations like this indeed one could use Möbius but it is not actually needed.

Let's imagine that instead we actually have the array $$$b$$$, and we would like to calculate the array $$$a$$$. How would we do it? Well, for every number just go through all the divisors and sum up the corresponding $$$b$$$ values. As going through dividends is easier, we would probably do that instead. And if we want to recalculate it in-place, we need to go in the decreasing order of $$$i$$$ to not add things many times. The code would look something like this:

for (int i = n; i > 0; i--) {
    for (int j = 2 * i; j <= n; j += i) {
        b[j] += b[i];
    }
}

If you found my explanation not so clear, I just want you to realize that this is a very natural and obvious way to do the job we want. If you were asked to do this, you would come up with exactly the same solution. Just add the value to all dividends but be careful with the order (the same way as with the knapsack problem).

Now we have an algorithm that transforms the array $$$b$$$ into the array $$$a$$$. "And what? We want the opposite!" you will say. Exactly! We want to do exactly the opposite. Just imagine in your head that you have the array $$$b$$$ and run this algorithm. Step-by-step. And now comes the key idea: just imagine that you have a weird time machine that allows you to reverse time. If you reverse time, the algorithm will run in the opposite direction and it will go back from the array $$$a$$$ to array $$$b$$$. This is exactly what we want! Now it remains to understand how to code an algorithm that reverses the time. It is easy. We should just undo all the actions in the reversed order. If we have a cycle, we should reverse it. If we add something, just subtract! Here is the solution:

for (int i = 1; i <= n) {
    for (int j = 2 * i; j <= n; j += i) {
        b[j] -= b[i];
    }
}

You may notice that I did not reverse the inner cycle. I didn't do it because the actions that are performed inside this cycle are independent of each other: we just subtract $$$b[i]$$$ from all its dividends. You can actually think about this as just one single action that we reversed. I did it because it is just a bit more complicated to go through dividends in descending order, and it is actually not needed here. And now we indeed have an algorithm that transforms the array $$$a$$$ into the array $$$b$$$! And no math is needed! We just used a very generic idea. The beauty of it is that we don't even need to understand what the algorithm we are trying to reverse does. It is a very manual low-level job: reverse and inverse all the actions.

Yes, indeed you can analyze it and understand that it does exactly the same thing as the Möbius transform, but well... Yes... But I claim that this is more understandable, easier to reproduce, less magical, and you don't need to calculate the $$$\mu$$$ function.

Some more notes: this idea of reversing time can be used in many settings. The most common one is DSU with rollbacks. You just remember all the things that changed and undo the actions. But here we actually performed all these actions, and after that reverse them. In our situation, we only imagine that these actions were performed. So in the DSU with rollbacks we can do any actions we want, for example, we do something like updating parents of some vertices: $$$p_u = v$$$, and remembering what was the old parent of $$$u$$$ (well, in this case, it was $$$u$$$, so we don't need to remember it, but whatever). And later we can just go back and replace $$$p_u$$$ with the old value. Our situation is different: we don't know what was the old value, and we want to find it. For it to be possible, the actions that we perform should be inversible. So, for example, in our case, we add one number to another number. It is an inversible action: we can just subtract back to undo it. But if the action is, for example, assignment or taking the maximum of two values, it is not inversible, and we would not be able to do our trick if we had such actions. This idea is similar to the fact that prefix sums allow us to find sums and bitwise xors of segments but not minimums and bitwise ors.

You may argue that DSU with rollbacks only somewhat uses the same concept. It is not exactly the same. And I would agree. But there are other situations where we can use exactly the same idea. FFT, Walsh-Hadamard transform, sum over subsets (SoS-dp), sum over supersets, etc. If you look closely, for all of them, if we already know the convolution one way, the inverse can be obtained without knowing anything about the math behind these algorithms by simply reversing the time. And actually, the thing that we wanted to calculate can be called a sum over divisors. All these are some transformations that can be used for convolutions. FFT can be used for $$$+$$$-convolution, Walsh-Hadamard for xor-convolution, sum over subsets for or-convolution, etc.

And at the end of this long comment, I will leave you with two simple exercises: - if all of these transformations before could be used to get a convolution, what kind of a convolution does our transformation give? - use the method we discussed to get an inversed sum over dividends. What convolution does it give?

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I was talking about the following: suppose, you have a task:

    Build all fractions $$$\frac{1}{i}, \dots, \frac{a_i}{i}$$$ for each $$$1 \le i \le n$$$ and calculate the number of unique fractions. Looks like you can't calculate it with pretty tricks without using Mobius.

    This trick works here because

    $$$a[\left\lfloor \frac{i}{d} \right\rfloor] = \left\lfloor \frac{a[i]}{d} \right\rfloor$$$
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Has anyone solved D using binary search ?

»
9 months ago, # |
  Vote: I like it +10 Vote: I do not like it

In F tutorial, what's the "easy system of equation" mentioned in the second paragraph?

  • »
    »
    9 months ago, # ^ |
    Rev. 4   Vote: I like it +8 Vote: I do not like it

    Not sure whether to call the below a system of equations since it’s just one equation. WLOG assume $$$v_i > v_j$$$.

    For the case where they are moving in the same direction, between two times that people meet, person $$$i$$$ must have traveled $$$2l$$$ more than person $$$j$$$, giving the equation $$$xv_i - 2l = xv_j$$$

    For the case where they are moving in opposite directions, the sum of the two distances must equal $$$2l$$$, giving $$$xv_i + xv_j = 2l$$$.

    I guess both cases also count the times when the people meet at the endpoints of the pool.

    I personally prefer to visualize it as two vertices (one for each end of the pool) and two arcs connecting the two nodes. Meeting in the opposite direction will correspond to one person swimming clockwise and another swimming counterclockwise, while meeting in the same direction will correspond to both people swimming clockwise.

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

For problem A, I tried to use a greedy solution since that's the first thing that came up to my mind, but it turns out to not work at all, because of testcases like 5 4 1 makes the code returning NO even though there's a solution to that one, which is 2 3.

This problem took me wayyyyyy too many times, and it took me 8 submissions to even know what's wrong with it.

For problem B, I have thought of distance calculation, but I can't connect a link between the two, so I ended up not using that and stuck on it, mostly because I have lost a lot of energy from solving problem A.

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

Can anyone tell me why my solution gives WA for problem D. 211601552

Thanks You

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

Can someone help me in this interactive problem, couldn't figure out why I'm getting a TLE. https://codeforces.com/gym/101021/problem/1

My submisision: 212177668

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

Can someone elabortae more on the greedy approach for problem C. Specifically, I don't understand how it allways leads to the correct answer.

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

    Consider a string, num the password database.

    Our objective is to select digits in such a way that we surpass the length of the password database, len(num). When faced with multiple options for choosing digits, it is optimal to take the digit which's index is right most among all the available options.

    This strategy increases the likelihood of selecting digits that eventually result in exceeding the length of num.

    consider the case

    88005553535123456

    2

    40

    56

    here for the first selection here we can take index 4 or 14 [0 based indexing], it is optimal to take 14 . Because the next index we will be selecting is will be right from 14 which has a higher possibility to surpass the length of password database in the next selection.

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

      but wont greedy fail for tc ?
      670
      2
      61
      70 answer should be yes as 61 ,71 can be made giving no in greedy

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Answer is yes if password is not a subsequent of password database. Since 71 is not present as a subsequent ans of greedy is yes

        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          understood was making a mistake that string A digits are lower limit while String B digit are upper limit

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

Does anyone know how to solve D using DSU? It has the DSU tag.

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

who can explain why this solution for problem D is not correct https://codeforces.com/contest/1845/submission/213144708

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

The way I originally solved should not pass since it is $$$O(N^2K)$$$, but it passes anyways :). Simply do what the editorial says naively, but either take the string $$$s$$$ or the complement of the string $$$s$$$, whatever is faster. (So define balance as either # of ones or # of zeroes depending on which is smaller). And this halves the runtime more or less, enough to get it to pass.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you tell me what is meant by balance in the editorial

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think by balance, the editorial means # of ones (not really sure). At least, that was the DP state I used.

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

I tried solving B,but got WA.Can anyone help me with the edge case? MY Submission ID : https://codeforces.com/contest/1845/submission/213485309

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

The solution to problem D is the Maximum subarray problem using Kadane's algorithm

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

Can someone explain the intuition of using binary search to solve the problem D?

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

Can somebody explain the editorial of B in better detail? I am having trouble understanding it.

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

Can someone explain me the transitions in problem E

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

Is there a way to solve C recursively without getting TLE?

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

explanation for the B problem plz

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

Can someone explain to me in more detail why in problem C, the running time is O(m + nD) in the editorial? I understand the reduction from O(m + nD) to O(nD). "O(m) comes from the outer loop over digits that you can't really get rid of" this part I am not sure of.