YouKn0wWho's blog

By YouKn0wWho, 2 years ago, In English

Thanks for participating in my contest blobheart. I hope you liked the problems. I would love to hear your feedback in the comments.

If you find anything wrong in the editorial which is more likely to happen because I have written a rather long editorial to make you understand the solutions better, then comment below.

Also, don't forget to upvote to pay for the editorial. See you in my next contest!

Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code (1D1D DP)
Code (D&C DP)
Tutorial is loading...
Code
Tutorial is loading...
Code
  • Vote: I like it
  • +517
  • Vote: I do not like it

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

1B was shit

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

    Problems like div2 D(div1 B) which only requires some stupid mathematical observations makes me lose all hope from Codeforces.

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

      The process that worked for me to solve it was:

      • Do a brute force for $$$x < y$$$ case, see all the possible answers for a few hand-made tests.

      • Look at one of an ends of the answers sequence (upper end works).

      • Observe that the number is close to $$$y$$$.

      • Think of the solution in the form $$$n = y - \varepsilon$$$ where $$$\varepsilon$$$ is very small.

      • Then $$$y \bmod n = y \bmod (y - \varepsilon) = \varepsilon$$$.

      • And $$$n \bmod x = (y - \varepsilon) \bmod x = y \bmod x - \varepsilon$$$.

      • The two are equal, so $$$2 \cdot \varepsilon = y \bmod x$$$.

      So, yeah, some amount of observation was required, but it mostly followed from looking at the brute-forced list of all possible answers.

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

        I solved it by very straightforward solution. 133667090

        • suppose, n = ax + r, and y = bn + r
        • then y = abx + (b + 1)r
        • if y < x, then ab = 0, just return x + y

        • else, try to divide ab as two integers and check if the answer is valid

        I don't know why it works. Hope someone can proof it or hack it.

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

          It's correct but you need to carefully check whether the factorization leads to a valid answer. a=floor(y/x), b=1, r=(y-ax)/2 is a solution (since x, y are both even, r will be integer).

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

            That' it! I divided from 1, so always got the answer you mentioned. Thanks.

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

          In the 3rd statement returning (x+y) was just an observation or you calculated. Can you elaborate plz

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

            A view of it:

            • The expression $$$n \bmod x = y \bmod n$$$ is complex.

            • And $$$n$$$ can be up to $$$2 \cdot 10^{18}$$$ according to the statement.

            • But if $$$n$$$ was large enough, the formula will transform into just $$$n \bmod x = y$$$, which is simple.

            • So let us think about large enough $$$n$$$.

            • When $$$x > y$$$, the expression $$$n \bmod x = y$$$ means we can use $$$n = x \cdot k + y$$$ for any large enough integer $$$k$$$.

            • Turns out $$$k = 1$$$ is fine.

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

        Hey Gassa, can you please explain why ymod (y-e) = e ?

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

          Try to imagine it with concrete numbers:
          Let $$$y = 1\,000\,000$$$ and $$$\varepsilon = 5$$$. Then
          $$$1\,000\,000 \bmod 999\,995$$$ is simply
          $$$1\,000\,000 - 999\,995 = 5$$$.

          Generally, the equation
          $$$y \bmod (y - \varepsilon) = y - (y - \varepsilon)$$$
          holds for $$$0 \le \varepsilon \le y / 2$$$.

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

        Hello! I was unable to come up with this kind of solution. What do you suggest to do if I want to solve problems like this in a real contest. Should I take this problem seriously regarding the approach you took like I could understand the things you wrote and they were pretty much justified in them so no doubt in that.

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

        How this statement:(y−ε)modx=ymodx−ε is true? It is only possible if ε is less than x. But how are we sure that ε is always smaller than x;

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

    My div1B experience:

    • struggle >1 hour writing equations to find n with rigurous maths.

    • in the last 15 minutes: look at random particular cases of x and y and try to guess the formula. I actually got AC with a half-guessed formula 1 minute before the round ended... Perfectly balanced guessforces problem

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

#mathsforces #adhocforces

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

Great Contest! Was able to solve 3 and 4th went off in nick of time.

Completely Mathforces

And thanks for the fast editorial.

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

My DIV2B didn't get AC though it's the same as you described

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

Editorial be like:

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

For 1603A - Di-visible Confusion we can also go from the end of an array and try to remove each item, and after each removal repeat the process. If you passed the whole array and didn't find an element to remove, the answer is NO. It can be shown that in the worst case you will pass each element no more than 21-22 times (you proved it in the editorial), so this solution is also possible.

The only sad thing about this solution is that you need to calculate an actual index of your element, and in order to do that you may need Fenwick tree.

Solution: 133626329

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

    I think we do not need a Fenwick tree in this solution: simply shift each element after the removed one. (The complexity is good since each element is shifted at most 21 times.)

    Code: 133622802

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

    P-A Ignore

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

In the editorial for problem C it is written that "must be divisible by at least one integer from 2 to i+1", I guess it should have been "not divisible by". thanks. btw, great contest.

UPD: It is updated now.

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

did anton also write the Thanks to Anton for writing editorial for this problem.

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

These cringy math symbols are going to give me nightmare tonight

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

Whoa, i've got a simple solution for div.1 C, though i don't know how to prove its correctness (so maybe it's wrong).

We use brute force set r from n to 1, and move l to the left, when minimal hasn't changed we skip it.

And it passed (right now)!!!

133667648

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

    I think this solution is actually provable, cause every iteration you increase the value of one of the elements of cut array. And since there are O(sqrt(i)) possible values of cut[i] the total number of iterations is O(n*sqrt(n)).

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

Was this submission hackable? It's technically wrong because there might be overflow but I think all integers coming from this overflow have 9 digits or more, so none could divide the numbers, which is unfortunate.

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

I solved Div1F with a different formula: the answer is

$$$ \sum_{l=0}^{k-1}({\binom{n}{n-l}}_{2} \cdot \prod_{i=1}^{l}(2^k - 2^i)) $$$

where

$$${\binom{n}{k}}_{2} = \frac{(1-2^n) \cdot \dots \cdot (1-2^{n-k+1})}{(1 - 2) \cdot \dots \cdot (1 - 2^k)}$$$

is a gaussian binomial coefficient (https://en.wikipedia.org/wiki/Gaussian_binomial_coefficient).

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

I have an $$$O(n\log^3 n)$$$ solution for D1D which sadly I wasn't able to debug during contest because of wasting time on A:

Just use segtrees to optimize calculating $$$f(n,K)$$$. Precalculate $$$g(n,k)$$$ which is the number of $$$l$$$s such that $$$gcd(n,l)=k$$$, and mainting a segtree with range add and range minimum. When we encounter $$$n$$$, we insert $$$f(n-1,k-1)$$$ into segtree, and go over all $$$n$$$'s divisors $$$d$$$ and add $$$[1,d]$$$ by $$$g(n,d)$$$.

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

    My solution is similar to you.

    And it is the only problem I do during the contest.I submit with another account (

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

Enough Math for today. errrrrr

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

Alternative solution for Div1A/Div2C:

  • notice, that it is always beneficial to erase last element if possible — it won't ever affect any other number in the array and it have to be removed at some point. Why not now?

  • If you can't remove the last element, then it's beneficial to erase second-to-last element, if possible. The proof is by similar argument to the previous one.

  • ...

  • In other words -- find the first element in reversed array that we are capable of removing. Execute this simple rule in a loop until array is empty (output YES) or no more elements can be removed (output NO).

  • Convince yourself that each element will be checked only a handful of times -- it's pretty hard to select a number that will be divisible by many of the indices $$$i + 1$$$, $$$i$$$, $$$i - 1$$$, ... . As the original editorial proved, it's at most 21 times.

  • Implement code using $$$\texttt{std::list}$$$ and $$$\texttt{std::find_if}$$$ (notice that find_if breaks when it finds first occurence) -- 133627167. Total complexity: $$$\mathcal{O}(21n)$$$

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

It just felt like a math contest or something, I wish I had seen more algorithm-oriented problems.

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

There is another solution to problem C as well:

Start from the end, if the last number is not divisible by (i+1) then erase it as it will not affect other elements. Now, find all the indexes which satisfy the given divisibility condition and store them in a priority queue. It is always good to delete elements (if possible) from the right. Also, calculate the count of consecutive values which will divide the number and we don't need to check this for more than 12-13 times.

Now delete the first element of the priority queue and update the values of all the indexes greater than the current deleted element and you are sure that you will not need to traverse each element more than 12-13 times, so it's fine.

End when the priority queue becomes empty (as this tells that all the divisible elements are removed) and check if all the elements are deleted or not.

My code : https://codeforces.com/contest/1604/submission/133638614

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

math

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

math

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

every

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

where

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

    Sir why you write 500000 comments in 0.9 seconds like a psychobot???

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

Here is how the donation amount looks like:

Div2A - 0.005 * 9529 = 47.645 USD
Div2B - 0.006 * 6274 = 37.644 USD
Div2C/Div1A - 0.008 * (4012+967) = 39.832 USD
Div2D/Div1B - 0.01 * (2273+911) = 31.84 USD
Div2E/Div1C - 0.04 * (27+396) = 16.92 USD
Div2F/Div1D - 0.2 * (1+24) = 5 USD
Div1E - 2 * 8 = 16 USD
Div1F - 2 * 3 = 6 USD

Total - 200.881 USD

FYI I will get 400 USD for this contest. So the donation amount is indeed half of this as I have estimated before the contest, although didn't think that it would be this accurate.

I will update you again when I get the money from Codeforces, more likely after a few months as I haven't received my previous contest's payment yet which happened 3 months ago!

Also, thanks for being a part of this. You have just helped someone who is in need (I mean after I distribute the money).

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

    Where will the money be donated?

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

      I will update you when I get my payment. I will mostly distribute them to some poor people from the street. If you have some suggestions let me know.

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

        just a suggestion try to donate to someone asking for help in ketto or something like that(means who r suffering from medical crises)

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

        It's fine. I feel like it is the best way to do it, having no third parties involved will make sure that the money will be given to those who really need it.

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

        TeamSeas

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

    It's actually cool that the guess was so close!

»
2 years ago, # |
  Vote: I like it +56 Vote: I do not like it
Unpopular Opinion
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +38 Vote: I do not like it

    And Honey when you solve it within a minute.

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

Can you provide a proof for D&C Div 1 D time complexity? I belive you should rely on the properties of this specific dp, because otherwise you can make a test where at the bottom level you would have something like $$$opt_i = i - \frac{n}{2}$$$, which would lead to $$$O(n \sqrt n)$$$ time complexity for one layer.

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

The Editorial is quite long, it would be nice if you had used spoiler type as u did for code.

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

PS: I GOT FST!

For Div.2 C what I did was for every $$$i$$$, finding the nearest $$$j$$$ such that $$$j + 1$$$ is not divisible by $$$a[i]$$$ and pushing the index $$$i$$$ to $$$mp[i - j]$$$. Here, $$$mp$$$ is a map of vectors. $$$mp[d]$$$ eventually stored the indices that become erasable after $$$d$$$ elements from their left gets erased.

Obviously we need to start by erasing some element in $$$mp[0]$$$. Here, starting with the rightest element $$$x$$$ is the optimal because minimum number of elements gets negatively affected from this operation. So we erase $$$x$$$ from $$$mp[0]$$$. After erasing $$$x$$$ we have to check whether there are new erasable elements to the right of $$$x$$$ and such elements can only be in $$$mp[1]$$$. Thus we check whether the rightest element of $$$mp[1]$$$ (let's call it $$$y$$$) is bigger than $$$x$$$. If not, we have to keep erasing from $$$mp[0]$$$. If yes, it is a good idea to first erase $$$y$$$ along with the indices that get erasable after erasing $$$y$$$ (It is a recursive process). Only after that we can continue with erasing from $$$mp[0]$$$.

Eventually all the vectors should become empty in $$$mp$$$. If they are empty then the answer is "YES", otherwise the answer is "NO".

Here is some in-contest ugly code but it failed the system test :( 133669599

What the code does is there is a function solve(k, iterator) and k means the rightest element we have deleted before calling this function and the iterator basically finds the most recent non-empty vector waiting for their elements to get erased. Can anybody help me what is wrong with my solution?

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

Why Itst_boyfriend's submissions are being shown out of contest?

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

    i think his code matched with others unfortunately and he was removed from the contest

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

In Div2 D, in case of (x<y) why can't n be (x+y)/2. For example, if x=2 & y=4, n can be 3 which is equal to (2+4)/2. In this case, n%x = 1 and y%n is also 1. Can anyone tell me the case where this condition fails. Thanks in advance!

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

Seems like the solution of maths question paper.

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

Here is a simpler solution to div1C:

Assume that we want to calculate the extreme value of $$$a_1, a_2, \dots, a_i$$$. Let $$$t[j]=$$$ how many numbers $$$a_j$$$ is divided into, $$$v[j]=$$$ the smallest number $$$a_j$$$ is divided into. We know $$$t[j]=\lceil\frac{a_j}{v[j+1]}\rceil$$$, $$$v[j]=\lfloor\frac{a_j}{t[j]}\rfloor$$$. It can be observed that the extreme value of $$$a_j, a_{j+1}, \dots, a_i$$$ is $$$\sum_{k=j}^i (t[j]-1)$$$.

For $$$i$$$ from $$$1$$$ to $$$n$$$, calculate $$$t[j]$$$ and $$$v[j]$$$ for all $$$j \leq i$$$. When we add a new element $$$a_i$$$ at the back, we can update $$$t[j]$$$ and $$$v[j]$$$ from $$$i-1$$$ to $$$1$$$ by brute force, but we stop the procedure when $$$t[j]$$$ is not changed. It seems to be an $$$O(n^2)$$$ solution, but for a certain $$$j$$$, $$$t[j]$$$ can be up to only $$$O(\sqrt C)$$$ different values, so we only update a value at most $$$O(\sqrt C)$$$ times, the solution is in $$$O(n \sqrt C)$$$ time.

Code: 133689083

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

    My solution (133668323) is similar to this.
    The worst test case for this I found locally is 100000 99999 99998 ... 3 2 1, where the inner loop body is executed ~35 million times. It is a bit more than $$$100\,000 \cdot \sqrt{100\,000}$$$, but still far from that amount doubled, which is the theoretical upper bound. I wonder if there is a more clever test to push the count further.

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

    It may be a dumb question but I don't see why it's ok to stop when $$$t[j]$$$ is not changed.

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

      The values $$$t[j]$$$ and $$$v[j]$$$ together fully define what happens to the left of them.

      For example, when you separate $$$10$$$ into three parts, you know the best way to do it is $$$10 = 3 + 3 + 4$$$. Going to the left of this position, all you need to know is that all the parts have to be $$$\le 3$$$. So, if you have already calculated what is the optimal solution on the left for parts $$$\le 3$$$, there is no need to do it again.

      It's like memoization but without recursive calls.

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

        Sorry I didn't notice the part to the left is still added to the answer when we stop. I wrongly thought we weren't adding it again. I got it now, thank you.

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

    That's a nice solution, imo nicer than the editorial.

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

    I think an important point you didn't mention is that the value of t[j] is non-decreasing for increasing i

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

I have an alternate solution for Div 2C that I personally find easier. I found a simple solution where I simply store an array of numbers to represent how many positions each value of a must be shifted to no longer be divisible by i+1, then I walk through the array and ensure that each value is less than the amount of numbers preceding it in the array. This works because it can be proved that as long as the sequence can be reduced, there is always an optimal move that does not negatively affect any of the other positions, so you do not need to worry about shifting a number from a non-divisible status to a divisible status. Apologies for any confusion as I am not too familiar on how to format comments and I am not too skilled at describing algorithms. My code is here: https://codeforces.com/contest/1603/submission/133704780

Very cool contest! I personally quite enjoyed the observation/logic side... I don't think the maths were too difficult either, although I couldn't figure out 2D for x<y. Thank you for the fun problems.

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

Any intuition behind div2 D in the second part where y >= x

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

YouKn0wWho

Div1 F — The explanation has many off-by-one errors. In particular, the answer for $$$X\neq 0$$$ should actually be

$$$\sum_{i=0}^{k-1}(-1)^i(2^{k-1-i})^n\prod_{j=0}^{i-1}(2^{k-j-1}-1)\cdot 2^{k-i-1}.$$$
if (X) {
	mi ans = 0;
	F0R(i,K) {
		mi cur = pow(mi(2),N*(K-i-1));
		F0R(j,i) cur *= po2[K-j-1]-1;
		cur *= po2[K-i-1];
		ans += (i&1?-1:1)*cur;
	}
	return ans;
} 

Shouldn't $$$n$$$ be $$$k$$$ here?

Let's replace $$$n-t$$$ by $$$n$$$, ...

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

    It's also worth noting that counting the number of length-$$$N$$$ sequences such that the resulting subspace has dimension $$$k$$$ for each $$$k\in [0,K]$$$ is given by

    $$$\#(k)=\prod_{i=0}^{k-1}(2^K-2^i)\cdot \left([t^{N-k}]\prod_{i=0}^{k}\frac{1}{1-q^it}\right)$$$

    This can be computed with the q-binomial theorem (with $$$q=2$$$). After computing these, the answer will be

    $$$\sum_{k=0}^{K}\frac{2^K-2^k}{2^K-1}\cdot \#(k).$$$

    Code: 133694728

    I was not aware that evaluating

    $$$\left([t^{N-k}]\prod_{i=0}^{k}\frac{1}{1-q^it}\right)$$$

    was doable but it seems that rainboy managed to find this link during the contest, congrats!

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

      The formula can be obtained by disturbing the GF. Let $$$F(t)=\prod_{i=0}^k \frac1{1-q^it}$$$, then we have $$$(1-t)F(t) = (1-q^{k+1}t)F(qt)$$$, hence a recurrence.

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

        Not totally sure which formula you are referring to. Could you elaborate on how $$$(1-t)F(t)=(1-q^{k+1}t)F(qt)$$$ allows us to determine the coefficients of $$$F(t)$$$?

        EDIT: Ok, if we define

        $$$c_i=[t^i]\prod_{i=0}^{n-1}\frac{1}{1-q^it},$$$

        then

        $$$c_i-c_{i-1}=q^ic_i-q^{n+i-1}c_{i-1}\implies c_i=\frac{q^{n-1+i}-1}{q^i-1}\cdot c_{i-1},$$$

        from which the result follows. Thanks!

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

          Consider the $$$[t^n]$$$ of two sides of the equation, then it gives a recurrence of $$$[t^n]F$$$.

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

1D : Isn't $$$c(x,2x-1)=x$$$?

All pair like $$$(i,i)\ (x\leq i \leq 2x-1)$$$ satisfy $$$gcd(i,j)>=l$$$.

Upd : And the editorial's difination of $$$c(i,j)$$$ is diffent from statement's.

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

Really Mathforces.

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

Perhaps the editorial for Div1 D,E are the clearest ones I've ever seen.

The problems are truly nice.

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

There is a mistake in the Proof of the observation 3 in problem E. Perhaps the author mistook i as j:(

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

woo, the author's just got so crazy at sqrt that it appears at the overall complexities of three adjacent problems!

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

The Editorial of Div1E is really detailed and easy-understanding.

Thank you!

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

Why my submission is giving wrong answer not runtime error? submission 133743503 , I have checked "assert(ans%x == y%ans && ans <= 2000000000000000000LL && ans >= 1);". Am I missing something ?

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

    You have modified the value of x before your assert function.

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

For 1603C - EXTREME EXTENSION - Extreme Extension, the space can be reduced to O(sqrt(M)) where M = 100,000, the maximum possible input value. This is using the observation that if we have a quotient x/k, then min(k, x/k) ≤ sqrt(x), so instead of a single vector of length M, we can use two vectors of length sqrt(M) (one of the values of k, one for the values of x/k).

The solution still takes O(N sqrt(M)) time.

Code: https://codeforces.com/contest/1603/submission/134607321

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

    I'm a bit confused about all the downvotes. What did I do wrong?

    (Note: edited the above post to show how the problem can be implemented as an on-line algorithm, i.e., without allocating an N-element array upfront.)

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

Excellent Contest. I think observations are important for CP rather than implementing the same algorithms continuously in more or less the same way to solve the questions. All Of CP is actually Mathematics only so I personally liked all the problems.

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

I have a doubt in regards to the editorial for Div1 C. Shouldn't $$$b_{1}=a_{i+1}\mod a_{i}$$$? If we set $$$b_1$$$ to what is mentioned in the editorial, won't the updated value for $$$a_1$$$ be wrong for the array $$$[10, 3]$$$? As far as I understand, the updated value for $$$a_1$$$ should be $$$1$$$ here, but according to the editorial it seems to be $$$2$$$.

Can someone please clarify?

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

    It should be $$$2$$$, because $$$2$$$ is greater and it is possible to achieve this using $$$3$$$(the minimum) operations: $$$[10, 3] \rightarrow [2, 2, 3, 3, 3]$$$. In your case, it is $$$[1, 3, 3, 3, 3]$$$ using $$$3$$$ operations. But if we can achieve $$$2$$$ why bother with $$$1$$$ which is lower?

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

There is a much cleaner solve for div2C/div1a (my solve is 133995726). Basically you find the highest non-divisor of a_i under i + 1 and check if that is less than 2. If any of these are less than 2 then the answer is NO, otherwise it is YES.

The reason this works is because the only time we cannot remove a number is when there are not enough numbers before it to get it to a value where it is not divisible. Otherwise it is enough to just remove the rightmost number that can be currently removed, which will always exist.

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

div1A(2C)can be greedily deleted from the back, and then simulated with the stack?I passed the question like this, but I don't know whether greed is correct

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

Problem 1C, why $$$\sum\limits_{k=l}^r\sum\limits_{i=1}^{\lfloor \frac rk\rfloor}\sum\limits_{j=i+1}^{\lfloor \frac rk\rfloor}=\sum\limits_{k=l}^r\sum\limits_{i=1}^{\lfloor \frac rk\rfloor}\phi(i)$$$?

I think it should be $$$\sum\limits_{k=l}^r\sum\limits_{i=1}^{\lfloor \frac rk\rfloor}\sum\limits_{j=i+1}^{\lfloor \frac rk\rfloor}=\sum\limits_{k=l}^r\sum\limits_{i=2}^{\lfloor \frac rk\rfloor}\phi(i)$$$.

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

I've discovered a much simpler sulotion with $$$n^3\sqrt n$$$ time complexity for problem E.
It's currently the fastest solution on codeforces:Link

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

I have a question with the time complexity of Div1.E.

In the observation 7,the solution improved the time complexity from $$$\mathcal O(n^5\log n)$$$ to $$$\mathcal O(n^3\sqrt{n}\log n)$$$ by only enumerating $$$a_i$$$ from $$$n-2\sqrt{n}$$$ to $$$n$$$. But we still have $$$\mathcal O(n^2\sqrt{n})$$$ states,and the complexity of transfering is $$$\sum_{k=1}^{n-a_1+1}\dfrac{a_1}{k}$$$ ,which is still $$$\mathcal O(n\log n)$$$ . So I think the time complexity is $$$\mathcal O(n^4\log n)$$$ ,and I don't know why my understanding is wrong. Can someone help me sort this out?

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

    I'm sorry that I found the mistake in my understanding. In fact,the complexity of transfering which is $$$\mathcal O(n\log n)$$$ is actually the sum of transfering $$$dp(i,j,1),dp(i,j,2),\dots,dp(i,j,k)$$$ ,so the whole time complexity is $$$\mathcal O(n^2)\times \mathcal O(n\log n)\times \mathcal O(\sqrt{n})=\mathcal O(n^3\sqrt{n}\log n)$$$. Sorry for wasting your time.

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

1D and 1E was so great! I really like it.

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

Problem F is an amazing problem. I have two solutions not listed in the editorial or in the comments.

I will prove the following claim: let $$$f(n,l)$$$ be the number of $$$n$$$-tuples of vectors in $$$\mathbb{Z}_2^k$$$ such that the spanning set of these vectors has size $$$2^l$$$. Then

$$$f(n,l)=\prod\limits_{i=0}^{l-1} \frac{(2^k-2^i)(2^n-2^i)}{2^l-2^i}$$$

First proof, by recursion and bashing. First observe that

$$$f(n,l)=2^l f(n-1,l)+(2^k-2^{l-1}) f(n-1,l-1)$$$

This is true by considering whether the last case increases the spanning set or not.

Now we induct on n and $l$.

Base Case: $$$n=l$$$. Clear.

Inductive Step: It suffices to show that

$$$\prod\limits_{i=0}^{l-1} \frac{(2^k-2^i)(2^n-2^i)}{2^l-2^i}-2^l\prod\limits_{i=0}^{l-1} \frac{(2^k-2^i)(2^{n-1}-2^i)}{2^l-2^i}$$$
$$$=(2^k-2^{l-1})\prod\limits_{i=0}^{l-2} \frac{(2^k-2^i)(2^{n-1}-2^i)}{2^{l-1}-2^i}$$$

We first cancel out the

$$$ \prod\limits_{i=0}^{l-1} (2^k-2^l) $$$

on both sides. This is equivalent to showing

$$$\prod\limits_{i=0}^{l-1} \frac{(2^n-2^i)}{2^l-2^i}-2^l\prod\limits_{i=0}^{l-1} \frac{(2^{n-1}-2^i)}{2^l-2^i}=\prod\limits_{i=0}^{l-2} \frac{(2^{n-1}-2^i)}{2^{l-1}-2^i}$$$

Now we expand the left hand side to get

$$$\frac{1}{\prod\limits_{i=0}^{l-1} (2^l-2^i)} (\prod\limits_{i=0}^{l-1} (2^n-2^i) - \prod\limits_{i=0}^{l-1} (2^n-2^{i+1}))$$$
$$$=\frac{\prod\limits_{i=1}^{l-1} (2^n-2^i)}{\prod\limits_{i=0}^{l-1} (2^l-2^i)} (2^n-1-2^n+2^l)$$$
$$$=\frac{\prod\limits_{i=1}^{l-1} (2^n-2^i)}{\prod\limits_{i=1}^{l-1} (2^l-2^i)} $$$

Dividing both sides by

$$$ 2^{l-1} $$$

yields the desired result.

The motivation for the first proof is that the numbers have a nice form.

Second proof, via polynomial. We first count the number of

$$$ 2^{l} $$$

-element spans (S such that there exist $x_1,\cdots,x_l$ such that $$$S$$$ contains all and only elements of the form $$$v_1x_1 \bigoplus \cdots \bigoplus v_lx_l$$$ for $$$v_i\in {0,1} \forall 1\le i\le l$$$ in $$$\mathbb{Z}_2^k$$$.

On one hand, there are $$$\prod\limits_{i=0}^{l-1} (2^k-2^i)$$$ ways to pick $$$l$$$ linearly independent elements. On the other hand, there are $$$\prod\limits_{i=0}^{l-1} (2^l-2^i)$$$ ways to select the same span.

Now, fix a span. We use inclusion-exclusion to find the number of ways to pick $$$n$$$ vectors such that their span has size $$$2^l$$$. It is not hard to show that this is a polynomial of degree at most $$$l$$$ in $$$2^n$$$ (i.e. the answer for $$$n$$$ is $$$P(2^n)$$$ for some $$$\deg P\le l$$$). Furthermore, for $$$n=0, 1, \cdots, l-1$$$, the answer is 0, which implies $$$P(x)=c\prod\limits_{i=0}^{l-1} (x-2^i)$$$. For $$$n=l$$$ the answer is $$$\prod\limits_{i=0}^{l-1} (2^l-2^i)$$$, implying $$$c=1$$$, as needed.

Now the answer is simply

$$$\frac{1}{2^k-1}\sum\limits_{l=0}^{\min\{k,n\}} f(n,l)(2^l-1)$$$

because the probability that an element is in a randomly selected span of $$$2^l$$$ elements is $$$\frac{2^l-1}{2^k-1}$$$

I tried to format this, but sometimes the dollar signs don't render (they render on the overleaf compiler) and I have to use double dollar signs.

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

I think the editorial has a typo in 1C.

The contribution term near the end currently says $$$i \cdot dp(i + 1, x) \cdot \left(\lceil \frac{a_i}{a_{i+1}} \rceil - 1 \right)$$$. I believe the $$$a_{i+1}$$$ should be $$$x$$$.

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

Here's my algorithm for Moderate Modular Mode.

If x = y, then just print x If x < y, then print (x + y) /2 If x > y, then print x + y

I'm having trouble finding edge cases for this algorithm. Here's my code if needed

143933295

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

For Div2E, I was stuck at the following part --> how do you find the smallest k for which $$$\lceil \frac{a_i}{k} \rceil \leq a_{i+1}$$$. Turns out this is just $$$\lceil \frac{a_i}{a_{i+1}} \rceil$$$. Somehow not that intuitive to me, so I was binary searching and thus getting TLE. Is there some easy ways to work with such kind of inequalities.

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

Hello,
    In Problem 1603B - Moderate Modular Mode for the second case (when x ≤ y), can't we simply take the average ?
Because if n the average of x and y, it will be the same distance from x to n and from n to y ...
Is there any Counter Example ??

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

    This only works if n % x == n — x and y % n == y — n, which is not always true. Consider x = 4 and y = 30, for example. If we use your strategy, n = (4 + 30) / 2 = 17. But 17 % 4 = 1 not 13.

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

Div1 E Complexity seems to be actually $$$O(n^3\sqrt n)$$$ with a constant of $$$\frac{\pi^2}{18}$$$.

By eliminating all unnecessary transits, the result will look something like this:

$$$ \begin{aligned} &\sum\limits_{mn,i,j,k,i_0} [j+ik\le mn] [i_0i\le j]\\ =&\sum\limits_{mn,j,k} \frac{mn-j}{k} \frac{j}{k}\\ =&\sum\limits_{mn,j} (mn-j)j \sum\limits_{k} \frac{1}{k^2}\\ \end{aligned} $$$

The former $$$\sum(mn-j)j$$$ sums up to $$$O(n^3\sqrt n)$$$ because $$$mn\in [n-2\sqrt{n},n]$$$ with a constant of about $$$1/3$$$, and the latter $$$\sum \frac{1}{k^2}$$$ sums up to less than $$$\zeta_2=\frac{\pi^2}{6}$$$. The total constant is therefore $$$\frac{\pi^2}{18}$$$.

I tested it with the following code, in which Cnt=469601774 when n=400 and Cnt=1054688268 when n=500, which matches the result quite well (the actual constant is a little smaller because of other optimizations)

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

i just want to ask , why the solution to div1 A should be like that , i understand the editorial but still didnt get it.