Geothermal's blog

By Geothermal, history, 2 months ago, In English,

A — Transfer

First, we compute the resulting amount of water in Cup 1. Observe that this is equal to $$$min(A, B+C)$$$. Let this value be $$$D$$$. Then, the amount transferred from Cup 2 to Cup 1 is simply $$$D - A$$$, so the amount remaining in Cup 2 is $$$C - D + A$$$.

Time complexity: $$$O(1)$$$. Click here for my submission.


B — Uneven Numbers

There are several efficient ways to approach this problem. One is to simply to count the one-, three-, and five-digit numbers less than or equal to $$$N$$$. However, because of the small maximum on $$$N$$$, a more naive approach works. Simply iterate over every value from $$$1$$$ to $$$N$$$, count its digits, and add one to the answer if the count is odd. (We can count a number's digits by repeatedly adding one to the count and dividing the number by ten until it reaches zero.)

Time complexity: $$$O(N \log N)$$$. Note that $$$O(\log N)$$$ is possible with the more efficient approach. Click here for my submission.


C — Build Stairs

We employ a greedy strategy. Process the elements in increasing order, and decrease the current element whenever we can do so without making it less than the last element. (The first element should thus always be decreased.) If at any point the current element must be less than the last element, no matter what we do, the answer is no.

The reason this strategy is optimal is that decreasing an number will make it easier (or at least as easy) to deal with the next element in the list, since any value the next element could have taken will still work when the previous number is lower, and in fact decreasing the previous number expands the range of possible values for the next set. (For example, if we have an element 3, the next element must be at least 3, but if we decrease this to 2, all the same values 3 or higher still work, but 2 does as well.)

Time complexity: $$$O(N)$$$. Click here for my submission.


D — Gathering Children

We first note that we can break up the given string into components consisting of a string of R's followed by a string of L's. Observe that no child will ever leave its component.

We thus solve the problem for each component. Within each component, a child on the left side will continually move to the right, or a child on the right side will continually move to the left, until it reaches the middle two characters, RL. At this point, the child will move between these two positions until the end of the process. With $$$10^{100}$$$ steps, we can see that all children will reach these two positions.

How can we determine how many children will land on the R and how many will land on the L? Note that one of these two characters must be in an odd position (based on its position in the original string) and the other must be in an even position. Because $$$10^{100}$$$ is even and each move changes the parity of a child's position, each child will end up in whichever position has the same parity as its original position. That means that whichever of R or L is on an odd position will get all the children in the component starting in odd positions, while the other will get all the children in the component starting in even positions.

We can implement this by using a two pointers-style technique to track the components.

Time complexity: $$$O(N)$$$. Click here for my submission.


E — Max GCD

First, can we substantially limit the possible answers to this problem? It turns out that we can: our $$$K$$$ moves keep the sum of our elements constant, so the answer must be a factor of our sum. Since our sum is at most $$$5 \cdot 10^8$$$, we can check every value less than or equal to the square root of the sum to compute a list of these factors. Now, we can simply check, for each of these factors, whether it is possible to use our $$$K$$$ operations to make all items in the list divisible by this factor. We then take the maximum of the factors for which this is possible.

To perform a check on a factor $$$F$$$, start by creating a multiset storing the values of the array modulo $$$F$$$. We'll need to decrease some of the values in the multiset and increase others so that all are equal to an element of the list $$$-F, 0, F, 2F,$$$ etc.

The key lemma is as follows: there will always exist a way to turn the smallest $$$X$$$ elements of the multiset, for some $$$X$$$, into $$$0$$$, and the remaining elements into $$$F$$$, in some number of moves. Moreover, this will be the smallest possible number of moves we could use.

In case you're interested, I'll give a proof that this is true after the solution. (The proof is relatively convoluted and hard to follow, which is why I'm emphasizing the rest of the solution first.)

Iterate over the multiset in increasing order. Maintain the number of subtractions required to decrease the elements we've seen so far to $$$0$$$ and the number of additions required to increase the elements we haven't seen yet to $$$F$$$. When these costs are equal, that's the minimum number of moves we need to achieve the factor $$$F$$$. If this minimum is at most $$$K$$$, $$$F$$$ is a possible answer. We can then simply print the maximum value $$$F$$$.

This concludes the solution--for completeness, a proof of the lemma is included below.

To prove existence, note that the sum of the values in the multiset must be $$$0$$$ mod $$$F$$$. Call an element "high" if we'll be raising it to $$$F$$$ and "low" if we'll be lowering it to $$$0$$$. Let the "cost" of an element be the number of additions or subtractions necessary to raise or lower it to its desired value. Call the "high cost" the sum of the costs of all high elements and the "low cost" the sum of the costs of all low elements. Note that the cost of a high element $$$i$$$ is $$$F - i$$$ and the cost of a low element $$$i$$$ is $$$i$$$.

Start with all elements being high. We maintain the difference of the high cost and the low cost. Initially, the high cost is the sum of $$$F - i$$$ over all elements. Since $$$F$$$ is $$$0$$$ mod $$$F$$$ and the sum of all $$$i$$$'s is $$$0$$$ mod $$$F$$$, this sum will be $$$0$$$ mod $$$F$$$. Express it as $$$kF$$$, for some integer $$$k$$$. Note that $$$0 \leq k \leq N$$$. The low cost, meanwhile, will be $$$0$$$, because no elements are currently low.

Suppose that we switch an element $$$i$$$ from high to low. In this case, the high cost will decrease by $$$F - i$$$ and the low cost will increase by $$$i$$$. Therefore, the difference will decrease by $$$(F-i) + i = F$$$. Therefore, if we switch the $$$k$$$ lowest elements from high to low, the high cost will be the same as the low cost. This means that it will take the same numbers of subtractions to deal with the low elements and additions to deal with the high elements, meaning that these subtractions and these additions can be our moves.

We have thus proven that this is doable. Now, we prove that it is optimal. First, note that if we're going to set all elements of the multiset to either $$$0$$$ or $$$F$$$, we minimize our costs by making the least values our low elements and the greatest values our high elements. Moreover, we can observe that it will always be inefficient to set any element to a value other than $$$0$$$ or $$$F$$$, as since our values are all between $$$0$$$ and $$$F-1$$$, moving to one of these other values will pass $$$0$$$ or $$$F$$$ and thus will cost us moves without getting any elements closer to $$$0$$$ mod $$$F$$$.

Time complexity: $$$O(\sqrt{S} + N \log N F(S))$$$, where $$$S$$$ is the sum of the $$$A_i$$$ and $$$F(S)$$$ is the maximum number of factors of any number less than $$$S$$$. While the exact value is hard to compute, it's not hard to see that with $$$N = 500$$$, $$$F(S)$$$ will be small enough to easily pass. Click here for my submission.


F — Enclosed Points

For each point, we count the number of subsets whose bounding rectangles enclose this point. Our answer is the sum of these values.

First, perform coordinate compression, mapping the X and Y-coordinates to integers from $$$0$$$ to $$$N-1$$$. Then, iterate over the points in increasing order of $$$X$$$. Additionally, maintain a segment tree, where each node represents a Y-coordinate and is $$$0$$$ if we have not seen this coordinate yet but $$$1$$$ if we have.

We solve the problem for each point using the Principle of Inclusion/Exclusion. First, the total number of rectangles is $$$2^N$$$, as we can either include or exclude each point from our subset. However, we must subtract the ones that don't contain the current point. For a rectangle not to contain the current point, all of the points in its subset must be above, below, to the left, or to the right of our current point. For each of these cases, let $$$P$$$ be the number of points satisfying its criterion. Then, we subtract $$$2^P$$$ to delete these cases.

However, we've subtracted out some cases twice. In particular, if all points are to the upper-left, upper-right, lower-left, or lower-right of our current point, we've subtracted it out twice (for example, the upper-left case was subtracted in the upper and left cases above), so we need to add $$$2^P$$$ back to account for each of these cases, where $$$P$$$ is the number of points satisfying each criterion.

The only case in which all points in a subset satisfy three or more of our subtraction criteria is the empty set (as no point can be both above and below our current point or both to the left and the right of this point). We added the empty set once in our original count, subtracted it four times, and then added it back four times in our most recent cases. We want it to count zero times, so we need to finally subtract the empty set once to get our final answer for the point.

Now, we need to compute the number of points satisfying these eight criteria. The first four are easy. A point $$$(X, Y)$$$, where $$$X$$$ and $$$Y$$$ are coordinates from $$$0$$$ to $$$N-1$$$, has $$$X$$$ points to its left and $$$N-X-1$$$ points to its right. Similarly, this point has $$$Y$$$ points below it and $$$N-Y-1$$$ points above it.

The remaining four criteria require us to use our segment tree. In particular, the number of lower-left points is equal to $$$query(0, Y)$$$ on our segment tree, as this stores the number of points to the left with Y-coordinates from $$$0$$$ to $$$Y$$$. Similarly, the number of upper-left points is equal to $$$query(Y, N-1)$$$ (or alternatively, simply the total number of left points minus the number of lower-left points). We can then compute the lower-right points by subtracting the lower-left points from the total lower points, and likewise, we can compute the upper-right points by subtracting the upper-left points from the total upper points.

Once we have these counts, we can use binary exponentiation to compute $$$2^P$$$ in $$$O(\log P)$$$ for each $$$P$$$. After we update the answer, we can update the segment tree at $$$Y$$$ to prepare for our next point.

Time complexity: $$$O(N \log N)$$$. Click here for my submission.

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

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

Auto comment: topic has been updated by Geothermal (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Actually we can use the log10 function in the cmath header in problem B.

for (int i = 1; i <= n; i++) 
	if ((int)(log10(i)) % 2 == 0)ans++;
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +34 Vote: I do not like it

    or string conversion :P

    ans+=to_string(i).size()%2;
    
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Yes, that's another fast way to solve this problem. I decided to avoid logs here because I'm always scared of decimal precision issues, taking a WA on B would have killed my penalty, and the digit count code is something I was very familiar with and could thus write extremely quickly. However, using logs is definitely a viable approach here.

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

    Trash algorithm. I can solve it in O(n).

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

Too fast .

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

for problem D sample input 1 i couldn't get this point After each child performed two moves, the number of children standing on each square is 0,1,2,1,1 from left to right.

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

    In the context of the components idea from my solution: The two components are RRL and RL. In the first component, the R in the RL is in an odd position (using zero-indexing, it has position 1) and L is in an even position. There are two elements in even positions in the component and one in an odd position. Hence, the answer for this component is 0 1 2. For the RL, we can similarly see that the answer is 1 1, so our overall answer is 0 1 2 1 1.

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

In B, whats the O(logn) solution ?

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

    int n = scan.nextInt(), len = (n+"").length(), total = 0;

    for(int i = 1; i < len; i+= 2) total += Math.pow(10, i)-Math.pow(10, i-1);

    if(len % 2 == 1) total += n — Math.pow(10, len-1) + 1;

    out.println(total);

    I am pretty sure this is O(LogN)

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

    I implemented O(1) with some ifs, and think this is more natural for this problem. Submission

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

      Oh nice! I think that is the same as the O(LogN) sol without the for loop.

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

Thanks for the editorial Mr. Leeds!

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

Alternative solution for D which I think easier to implement:

Note that for sufficiently large even number $$$2K$$$ time passed, the position of each children will be equal as position of $$$10^{100}$$$ case.

We will try induction-like method : it is easy to compute "if one child is at position $$$i$$$, where will he be after $$$2^t$$$ time has passed" if we know "if one child is at position $$$i$$$, where will he be after $$$2^{t-1}$$$ time has passed".

$$$2^{20}$$$ is a sufficiently large even number, so we iterate through all possible indexes 20 times and compute position[i][t] which is, where one should be if one started at $$$i$$$ and $$$2^t$$$ time has passed.

Submission : My submission

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

    Hi! How can I see that 20 is the number that I want? You just said 2²⁰ is a sufficiently large even number, but I don't understand how to choose this number. Can you explain? Please

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

      Sorry for late reply.

      Actually, any even number larger than $$$100,000$$$ works.

      If the component is RRRR...RRLL...LLLL, Everyone between will eventually get to center RL and go back and forth forever. Since the length is 100,000 everyone can go to "where they would be after infinite amount of time" after 100,000 steps.

      (i.e, 100,000 steps would yield same result as 100,002).

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

        $$$2^{20}$$$ was kind of arbitrary. At first I misread the statement as 1,000,000 and picked $$$2^{20} = 1,048,576$$$ which is slightly larger. Actually $$$2^{17}$$$ is enough :)

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

In E-Max GCD can someone plz explain the line "To perform a check on a factor F, start by creating a multiset storing the values of the array modulo F. We'll need to decrease some of the values in the multiset and increase others so that all are equal to an element of the list −F,0,F,2F, etc." Especially how do we decrease or increase?

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

IN D problem , what happens if they reach the end ?? i cant understand can someone explain ?

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

    For any string a of length n, a[0] = 'R' and a[n-1] = 'L' as given in the problem statement.So it would never reach any of the ends.Pen and paper along with few cases would help you.

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

      ok bro , so i understood that they move l and r and we need to find them how many are standing after $$$\mathbf{10^{100}}$$$ moves right?

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

        Yes, after a bit of testing you will find that the sequence comes to saturation after some operations i.e. it doesn't changes further on even number of moves.So just figure out that.

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

Wish all editorials were as crisp and clear as this one.

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

Perevedite solutions, dam 10 pekti

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

Can someone please check my code for $$$E$$$ and point out the mistake. It's failing 10 out of 84 test cases : Solution

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

F is really difficult to understand for a newbie like me. It will take video tutorial/editorial to understand it. Should I skip this problem at this point?