Geothermal's blog

By Geothermal, history, 4 years ago, In English

A — Calc

Just directly print the given sum.

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


B — Minor Change

The answer is simply the number of positions $$$i$$$ for which $$$S[i] \neq T[i]$$$. This is because we must make a move fixing each of those position, and each move can only make $$$S[i] = T[i]$$$ for one new position. Thus, we can iterate through the positions and count those where $$$S$$$ and $$$T$$$ differ, printing the total as our answer.

Time Complexity: $$$O(|S|)$$$. Click here for my submission.


C — Tsundoku

We apply two pointers. Iterate over the number of books to be read from desk A in decreasing order, starting with the greatest number of those books we could read without exceeding $$$K$$$ minutes. Maintain the sum of all books to be read from desk A. Then, while we can do so without exceeding $$$K$$$ minutes, add the next book from desk B to the list of books to be read. We can then consider the total number of books read between desk A and desk B as a possible answer, decrement the number of books from desk A, and continue.

The basic intuition is that as we decrease the number of books we read from desk A, the number of books we read from desk B monotonically increases. By processing the number of books to be read from desk A in order, we avoid having to recompute any sums, achieving a time complexity of $$$O(N+M)$$$.

Time Complexity: $$$O(N+M)$$$. Click here for my submission.


D — Sum of Divisors

Let's reframe the problem by considering the total contribution each divisor makes to the answer. For any given $$$i$$$, $$$i$$$ contributes $$$K$$$ to the sum for each $$$K$$$ from $$$1$$$ to $$$N$$$ such that $$$K$$$ is a multiple of $$$i$$$.

Notice that the list of these $$$K$$$ is of the form $$$i$$$, $$$2i$$$, $$$3i$$$, ..., $$$\lfloor \frac{N}{i} \rfloor i$$$, noting that the last term is the greatest multiple of $$$i$$$ less than $$$N$$$. For simplicity, let $$$M = \lfloor \frac{N}{i} \rfloor.$$$ Then, the sum of this sequence is equal to $$$i + 2i + 3i + \cdots + Mi = i (1 + 2 + \cdots + M) = \frac{iM(M+1)}{2}.$$$

Thus, by computing $$$M$$$ and the above product, we can compute each divisor's contribution to the answer in $$$O(1)$$$, giving us an $$$O(N)$$$ solution.

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


E — NEQ

First, let's count the number of ways to choose $$$A$$$, irrespective of $$$B$$$. There are $$$\dbinom{M}{N}$$$ ways to choose the $$$N$$$ integers to appear in $$$A$$$ and $$$N!$$$ ways to arrange them, so we have $$$\dbinom{M}{N} N!$$$ choices for $$$A$$$ in total.

Now, without loss of generality, assume the sequence $$$A$$$ is simply $$$1, 2, \cdots, N$$$, since the number of choices for $$$B$$$ doesn't depend on our sequence $$$A$$$. We want to count the number of sequences $$$B$$$ where there is no position $$$i$$$ such that $$$B_i = i$$$.

We do this using the principle of inclusion and exclusion. By PIE, we know that the number of sequences $$$B$$$ where $$$B_i \neq i$$$ for all $$$i$$$ is equal to the sum over all valid $$$j$$$ of $$$(-1)^j$$$ times the number of ways to create a sequence $$$B$$$ where at least $$$j$$$ positions $$$i$$$ have $$$B_i = i$$$.

Thus, it remains to compute the number of ways to compute the number of sequences $$$B$$$ with at least $$$j$$$ equal positions. There are $$$\dbinom{N}{j}$$$ ways to choose $$$j$$$ positions where $$$B_i = i$$$. Then, it doesn't matter what we put in the remaining positions, so there are $$$\dbinom{M-j}{N-j}$$$ ways to choose the numbers and $$$(N-j)!$$$ ways to arrange them. Thus, the total number of ways to ensure that at least $$$j$$$ positions have $$$B_i = i$$$ is $$$\dbinom{N}{j} \dbinom{M-j}{N-j} (N-j)!$$$.

By precomputing all relevant factorials and their modular inverses in $$$O(M)$$$, we can compute the above product in $$$O(1)$$$ for each $$$j$$$. We then sum these up using our PIE formula, giving us an $$$O(N+M)$$$ solution. Since $$$N \leq M$$$, this is simply $$$O(M)$$$.

Time Complexity: $$$O(M)$$$. Click here for my submission.


F — Unfair Nim

It is well known that the second player wins a game of Nim if and only if the bitwise XOR of the numbers of stones in each pile is equal to $$$0$$$. Thus, we want to make the equation $$$A_1 \wedge A_2 \wedge A_3 \wedge \cdots \wedge A_n = 0$$$. By taking the XOR of this equation with $$$A_3 \wedge A_4 \wedge \cdots \wedge A_n$$$, we have $$$A_1 \wedge A_2 = A_3 \wedge A_4 \wedge \cdots \wedge A_n.$$$ We can immediately compute the right-hand side, since it is fixed before we make our moves. Now, we want to find the largest $$$x$$$ between $$$1$$$ and $$$A_1$$$, inclusive, such that $$$x \wedge (A_1 + A_2 - x) = A_3 \wedge A_4 \wedge \cdots \wedge A_n.$$$

We build $$$x$$$ via digit DP, determining the bits of $$$x$$$ from the most significant bit to the least significant bit. Let $$$a$$$ be the maximum possible value of $$$x$$$ thus far such that we have found a bit in which $$$x$$$ contains a $$$0$$$ while $$$A_1$$$ contains a $$$1$$$ (so, we know that no matter what bits we add to $$$a$$$ in the future, it will be less than $$$A_1$$$), or $$$-\infty$$$ if no such value exists thus far. Let $$$b$$$ be the value of $$$x$$$ such that thus far, all bits in $$$b$$$ are the same as those in $$$A_1$$$, or $$$-\infty$$$ if creating this value is impossible. Note that we cannot add a $$$1$$$ to $$$b$$$ if the corresponding bit in $$$A_1$$$ is a $$$0$$$, as this would make $$$b$$$ too large.

Let $$$S = A_3 \wedge A_4 \wedge \cdots \wedge A_n.$$$ If $$$S$$$ contains a $$$0$$$ in any given bit, we know that $$$x$$$ and $$$A_1 + A_2 - x$$$ must either both contain a bit or neither must contain a bit. We can tell which case applies by determining whether after subtracting out all bits we've assigned so far, $$$A_1 + A_2$$$ is greater than $$$2^{k+1}$$$, where $$$k$$$ is the index of the current bit. This is because the sum of all future bits will be at most $$$2^{k+1} - 2$$$, so $$$A_1 + A_2 \geq 2^{k+1}$$$ both enables us to add two $$$1$$$s at position $$$b$$$ and forces us to do so. If we add a bit to both numbers, we add $$$2^k$$$ to $$$a$$$ and $$$b$$$, but set $$$b$$$ to $$$-\infty$$$ if $$$A_1$$$ contains a $$$0$$$ in position $$$k$$$. Otherwise, we don't add anything to either $$$a$$$ or $$$b$$$, but if $$$A_1$$$ contains a $$$1$$$ in position $$$k$$$, we can set $$$a$$$ to $$$\max(a, b)$$$, since now we've found a position in which $$$x < A_1$$$.

If $$$S$$$ contains a $$$1$$$ in any given bit, we know that exactly one of $$$x$$$ and $$$A_1 + A_2 - x$$$ must contain a bit. Thus, we can add $$$2^k$$$ to $$$a$$$, because this will not make $$$a$$$ exceed $$$A_1$$$. If $$$A_1$$$ contains a $$$1$$$ in position $$$k$$$, we can also add $$$2^k$$$ to $$$b$$$, or we can alternatively assign a $$$0$$$ in order to guarantee that $$$x < A[1]$$$, allowing us to set $$$a$$$ to $$$\max(a, b)$$$.

At the end of this process, $$$a$$$ and $$$b$$$ are our possible values for $$$x$$$. Of course, if $$$a$$$ and $$$b$$$ are zero or $$$-\infty$$$, they can't work (the zero case fails because we cannot move every stone from the first pile). Moreover, we also must confirm that $$$a \wedge (A_1 + A_2 - a) = S$$$ in order to use $$$a$$$, and we must check the same equation for $$$b$$$. This is because the total bits we assign throughout our process may not equal $$$A_1 + A_2$$$, since the number of bits we assign is largely determined by $$$S$$$. (One countercase that demonstrates this issue is $$$N=3, A = 7, 5, 6$$$: our solution assigns one bit in position $$$2$$$, one bit in position $$$1$$$, and two bits in position $$$0$$$, but the total of these bits is $$$4 + 2 + 2 = 8 < 7+5.$$$) Then, we take the largest of these possible values for $$$x$$$ and subtract it from $$$A_1$$$ to get our answer.

Time Complexity: $$$O(N + \log A_i).$$$ Click here for my submission.


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

| Write comment?
»
4 years 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).

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

for D my running time was around 1300ms yours 140ms great learn something new thanks.

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

Writing the editorial would have took more time than to solve all problems for you.

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

For E: NEQ it should be $$$\binom{M}{N}(N!)$$$ which happens to be the same as $$$MPrN$$$

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

We do this using the principle of inclusion and exclusion. By PIE, we know that the number of sequences B where Bi≠i for all i is equal to the sum over all valid j of (−1)j times the number of ways to create a sequence B where at least j positions i have Bi=i.

Can somebody explain this line as to why we are multiplying (−1)j ?

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

    Geothermal Can you help ? or provide any resource ?

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

    We know the number of ways of building A.

    Now here we considered how many ways to build B for a single way of a.. Then answer will be, number of ways build a * number of ways build b. So for buildings B Firstly we generate (array B)all the ways using M number.
    Thats means we calculate the number of ways where number B(i) = i is (0, 1, 2, 3... n). But we need only the ways where number of B(i) =i is 0. So, now we have to remove ways where number B(i) = i is (1, 2, 3... n) but here we delte number of ways where B(i) = i ( 2,3....n times) twich. So, we have to add them... For this reason here (-1)^j used.

    Consider my poor english, for better generate all the sequence in a paper for small n and m (2,3)

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

thanks @geothermal.

btw ,where can i practice more problems like E?.

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

    Most ABCs have at least one combinatorics problem; they’re probably the best source if you want to practice lots of similar problems.

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

    I guess you might try solving the combinatorics and inclusion-exclusion problems from this blog. Not necessarily similar to E but high-quality problems.

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

since the number of choices for B doesn't depend on our sequence A.

Geothermal Can you elaborate it more please ?

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

    In the second step, $$$B_i=i$$$ means $$$B_i=A_i$$$. So no matter what $$$A$$$ looks like, we can always satisfy $$$B_i=A_i$$$.

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

Can somebody explain the solution for problem E, I am not able to understand it.

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

@Geothermal why #pragma GCC optimize ("O3")
#pragma GCC target ("sse4") are used?

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

for problem c,if we iterste over two arrays by considering the min value of two pointers ,y is it giving wrong answer?

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

    consider 2 arrays and k=120 arr1 = [60,120], arr2=[60,20,30] answer is 3 (60+20+30). then find your answer.

    we don't know where to go actually when both the values are equal.

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

F could be easily solved by using https://www.geeksforgeeks.org/find-two-numbers-sum-xor/ . we just make a number by using only fixed bits and mark the optional bits in a boolean array .. and then we can greedily put those optional values to achieve the answer.

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

    But Dp solution is very cool

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

    In your submission to this problem, you used one condition, could you please tell me why did you check for this condition.. ~~~~~ S=a[0]+a[1]; x=totalxor^a[0]^a[1]; if(s%2!=x%2) answer=-1; ~~~~~ what role does parity of sum and XOR plays in this question?

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

I didn't understand the explanation of problem D. My approach was finding primes and then the number of divisors of that prime and then just iterating all powers of that prime and gives increment the value of the previous number of divisors count. This continued till 10^7 and the rest for the rest of the value I used prime factorization to find the number of divisors but the solution gives TLE.

How can I reduce the running time with some changes in code?

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

    "...and then the number of divisors of that prime."

    Cant be a lot ;)

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

For E why is it assumed that A and B both have the same set of elements say m>2*n we can choose completely disjoint sets of elements for both sequences with N!*N! possible solutions I am sure I have misinterpreted something but cannot figure out what. :-(

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

    From where did you see that it is assumed?

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

    That's not assumed. Do you understand what we're doing PiE over? I can phrase in a different way:

    Take WLOG $$$A_i = i$$$ for $$$1 \le i \le n$$$ as in the editorial above. Then, let $$$S_i$$$ be the set of sequences for $$$B$$$ satisfying the second condition ($$$B_i \neq B_j$$$ when $$$i \neq j$$$) and with $$$B_i=i$$$. Then clearly we want to work out

    $$${M \choose N} N! - |S_1 \cup S_2 \cup \cdots \cup S_N|$$$

    as this is the number of valid $$$B$$$ sequences (assuming $$$A_i=i$$$ for all $$$i$$$). We can work this out via PiE (since the sizes intersections of various $$$S_i$$$ sets are easy to work out), and then we just multiply by $$${M \choose N} N!$$$ as that's the number of possibly $$$A$$$ sequences.

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

I feel C wasn't quite clear.

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

    I solved it using a different method.

    First, calculate the prefix sums of both the arrays. Now assume that we can take $$$X$$$ books in total from desk A and B. How do we check if its true?

    We know that we take the books as some prefix of A and some prefix of B. So the possibilities are take ($$$0$$$ books from A, $$$X$$$ books from B), ($$$1$$$ book from A, $$$X-1$$$ books from B),($$$2$$$ books from A,$$$X-2$$$ books from B)... ($$$X$$$ books from A, $$$0$$$ books from B).

    Now if the sum of any of those combinations is $$$\leq K$$$ then we know that its possible to take $$$X$$$ books. Now we simply find the maximum $$$X$$$ by binary search. We can binary search on X because if we can take $$$X$$$ books, we can also take $$$X-1$$$ books.

    Time complexity is $$$O((N+M)log(N+M))$$$

    My submission: https://atcoder.jp/contests/abc172/submissions/14805133

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

E)
For anyone having a problem with understanding the inclusion/exclusion principle for derangement can have a look at The last section is Derangment for N elements,

Which you can further generalize to M objects and N places ( M >= N ), such that none of the N objects are at their respective position, after which you might be able to easily understand the given editorial.

Thanks!

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

In problem E,how is the precomputation of inverse factorials done in O(M)? Isn't it O(MlogM)?

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

    I did:

    // inv_fac(maxn) = (fac(maxn)) ^ (-1)
    inv_fac[maxn] = modinverse(fac[maxn], MOD);
    // inv_fac(i) / (i + 1) = inv_fac(i + 1) => inv_fac(i) = inv_fac(i + 1) * (i + 1)
    for(int i = maxn - 1; i > 1; --i)
    	inv_fac[i] = mul(inv_fac[i + 1], i + 1); 
    

    This is O(log(maxn) + maxn) = O(maxn).

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

      Cool idea. Thank you. But I think the code of Geothermal has complexity in precomputing inverse factorials as O(MlogM).

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

        We can do that in O(maxn) without log factor also..

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

    The complexity of my code is $$$O(M log MOD)$$$, since the complexity of evaluating modular inverses is logarithmic with respect to the modulus; since $$$MOD$$$ is a constant, $$$\log MOD$$$ does not contribute to the asymptotic complexity of the algorithm. (It adds to the constant factor, of course, but not nearly enough to cause TLE.)

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

It's kind of sad that AtCoder doesn't have a social platform even to post editorials like this so that they have to do it on Codeforces.

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

    Maybe I am misunderstanding something, but AtCoder does provide editorials. It's in Japanese right now, and will be translated and uploaded in 2-3 days.

    If you meant discussion, then I think it's a good decision: most of CP community already communicates on CF and putting effort into a seperate blog (which would not even see huge usage) is frivolous.

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

Love your editorials !!

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

$$$-$$$ I am curious how would one solve problem C if we have 3 desks of books?

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

In F — Unfair Nim, how do we know that for the second player to win the bitwise XOR of all A[i] must be zero?

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

    Quick definition: xor-sum means the xor of all $$$A_i$$$.

    Whatever move the first player makes, the xor-sum will become nonzero, and the second player can always make the xor-sum 0 again. Finally both xor-sum and sum will become zero so the second player wins.

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

      I get this partially, but how can one prove that if the xor-sum is not zero initially, then the second player can not win. And for each player what are the optimal moves?

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

        If the xor-sum is not zero, the first player can make it zero. The optimal move is finding the number that makes the highest bit in the xor-sum 1, and make the corresponding change.

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

Geothermal

Your Approach to E is absolutely clear. In Atcoder's Editorial, they have done this question using a different approach which isn't quite clear. Could you please explain that.

Thanks

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

    What is the point you don't understand?

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

      What does |s| stand for, and what is s?

      Also how did we arrive at (M) P (s) * ((M-s) P (N-s)) ^2

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

In the part of problem E, $$$\dbinom{N}{j} \dbinom{M-j}{N-j} (N-j)!$$$ is actually not the exactly number of ways to make at least $$$j$$$ positions equal because it contains duplication. But I can't find a better way to interpret this. I think one can provide a better interpretation so it will be easier to understand.

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

    he tries to found all permutation of array A, then he found all permutation of B then count all derangements using inclusion exclusion. you can see this for more explanation.

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

I am not clear yet why (-1)^j is used

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

Can anyone explain the idea in case of n = m = 3

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

    I traced it. this is explanation for it. Array A = all permutation of 1 2 3 Array B = [2 3 1, 3 1 2]