YouKn0wWho's blog

By YouKn0wWho, 5 weeks 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
  • +527
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +302 Vote: I do not like it

1B was shit

  • »
    »
    5 weeks 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.

    • »
      »
      »
      5 weeks 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.

      • »
        »
        »
        »
        5 weeks 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.

        • »
          »
          »
          »
          »
          5 weeks 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).

          • »
            »
            »
            »
            »
            »
            5 weeks 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.

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

            I solved the equations and got ab = floor(y/x), r(b+1) = y(mod(x)) I made the mistake of taking a=1 and b=floor(y/x). Logic_zys Why is this wrong?

            PS: Got it I guess. Is it because in this case r = y(mod(x))/(b+1) which isnt always necessarily an integer.

        • »
          »
          »
          »
          »
          5 weeks 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

          • »
            »
            »
            »
            »
            »
            5 weeks 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.

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

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

        • »
          »
          »
          »
          »
          4 weeks 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$$$.

  • »
    »
    5 weeks 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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I actually enjoyed doing the math, but for problems like this there's usually an unfair advantage as one can easily guess the solution.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I got it WA because of a silly mathematical mistake. Today's questions were focused on mathematics and observation more. It does not require any kind of logical and implementation.

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

#mathsforces #adhocforces

»
5 weeks 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.

»
5 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

Nice contest and hope to see you again .

»
5 weeks 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

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

Editorial be like:

Meme
»
5 weeks ago, # |
  Vote: I like it -14 Vote: I do not like it

Div2 A — Simple math

Div2 B — Simple observation

Div2 C — Pain

Div2 D — More Pain

Spoiler
»
5 weeks 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

  • »
    »
    5 weeks 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

»
5 weeks 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.

»
5 weeks 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.

»
5 weeks 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

»
5 weeks 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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you make this more detailed please?

  • »
    »
    5 weeks 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)).

»
5 weeks 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.

»
5 weeks 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).

»
5 weeks 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)$$$.

  • »
    »
    5 weeks 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 (

»
5 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

Enough Math for today. errrrrr

»
5 weeks 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)$$$

»
5 weeks 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.

»
5 weeks 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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    A priority queue is an overkill. A simple thing as you said select greedily from the right and delete it, it will be looking O(n*n) in nature but you will be iterating and cross one element not more than 20-21 times(because we also remove the particular element). So asymptotic complexity will be (20*n). My code: https://codeforces.com/contest/1604/submission/133691492

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

      I'm still not convinced that the complexity is O(20*n). I think it can be in O(1) time. You just have to check the first 22 numbers. If there is even a single number that is not removable, then you're done, and the output is "NO". Otherwise, all the numbers are removable. Here, you are also done. The only way that the rest of the list is not removable is if all the numbers are greater than 22! which they're not since they're upper bounded by 10^9.

      I think the editorial offers an O(n + 22^2) only because it takes O(n) to read in the original array.

      My submission O(1): https://codeforces.com/contest/1604/submission/135795122

»
5 weeks ago, # |
  Vote: I like it -68 Vote: I do not like it

math

»
5 weeks ago, # |
  Vote: I like it -70 Vote: I do not like it

math

»
5 weeks ago, # |
  Vote: I like it -74 Vote: I do not like it

every

»
5 weeks ago, # |
  Vote: I like it -62 Vote: I do not like it

where

  • »
    »
    5 weeks 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???

»
5 weeks 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).

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Where will the money be donated?

    • »
      »
      »
      5 weeks 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.

      • »
        »
        »
        »
        5 weeks 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)

      • »
        »
        »
        »
        5 weeks 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.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        TeamSeas

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

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

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

    And Honey when you solve it within a minute.

»
5 weeks 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.

»
5 weeks 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.

»
5 weeks 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?

»
5 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

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

  • »
    »
    5 weeks 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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I think DIV2 C is more difficult than DIV2 D. D was based on observation and can be guessed also. I actually enjoyed the contest. Thanks for fast editorial :)

»
5 weeks 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!

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    x=4,y=14. It will fail on lot of cases like this.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I guess (x+y)/2 will only work when y<2x. Suppose y is of the order 3x for example x=2 and y=6. In that case according to your hypothesis n should be (2+6)/2= 4 But n% x= 4%2= 0 and y%n= 6% 4=2 Hope that helps you to realize what (x+y)/2 will not work every time :)

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Seems like the solution of maths question paper.

»
5 weeks 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

  • »
    »
    5 weeks 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.

  • »
    »
    5 weeks 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.

    • »
      »
      »
      5 weeks 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.

      • »
        »
        »
        »
        5 weeks 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.

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

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

  • »
    »
    5 weeks 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

»
5 weeks 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.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank youu, nice contest and nice editorial

»
5 weeks 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$$$, ...

  • »
    »
    5 weeks 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!

    • »
      »
      »
      5 weeks 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.

      • »
        »
        »
        »
        5 weeks 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!

        • »
          »
          »
          »
          »
          5 weeks 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$$$.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain this part of problem B editorial:

If XOR is 0, then there will be an even number of bi’s such that its last bit is 1. But then the sum will be even. But here the sum n is odd, which produces a contradiction.

I didn't understand the part that talks about the last bit.

Thanks.

»
5 weeks 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.

»
5 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

Do you dream to make it mathForce?

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

Really Mathforces.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Div2 D can be solved by elementary maths. If y>=x then, If n%x = r means n=a*x+r. y%n should also be r, so y=a*x+2r, so that (a*x+2r)%(a*x+r)=r. This way n%x=y%n=r. Now a=y/x and r=(y%x)/2, since y=a*x+2r. If y<x then simply x+y is the answer.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

He loves number 69 very much.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The key idea for Div2C: Any number can have at least one element that is not a factor of that element between 2 and 23 under the given constraints that a[I] does not exceed 1e9. It is because LCM(2,... 23)>1e9. So checking the first 23 elements are enough. Therefore, the time complexity is O(23 * 23) in the worst case.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't know why the number 69 exists in each problems test case. In Div2.D there is 420 also. youKnowWho might love those two numbers. 69 & 420

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone plz check my code for c and tell tc in which it fails i tried it with factorial uptil 21 dividing it was failing in 9422th token of pretest 2 plz tell i am confuse =d thnx in advance

»
5 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

Shit Contest. Only Maths. For dumb people like me how I will able to solve such questions.

»
5 weeks 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.

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

Can someone please explain the multiplication of i in E/div2 ?

ans += 1LL * (split - 1) * y * i;

, We need to make (split-1) times on current element a[i]. After which it will be st, now the number of times we need to make it is when i+1 element is x, which is y.

Now this counts up for number of times we make the split, why we multiply it by i ?

UPD : this will be considered for each of prefix. hence we multiply by i.

»
5 weeks 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:(

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Congratulations for being the top contributor.

»
5 weeks 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!

»
5 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

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

Thank you!

»
5 weeks 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 ?

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

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

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

The idea of using the axis to find the solution n is great! (This congruence equation :n modx=ymod n would be more difficult to solve if computed algebraically).

»
5 weeks 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

  • »
    »
    5 weeks 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.)

»
5 weeks 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.

»
5 weeks 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?

  • »
    »
    5 weeks 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?

»
5 weeks 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.

»
5 weeks 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

»
5 weeks 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)$$$.

»
5 weeks 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

»
5 weeks 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?

  • »
    »
    5 weeks 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.

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

@YouKnowWho thanks for writing long — detailed editorial as they are helpful for beginners and strugglers

Thanks

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

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can any one tell me why my code fail in test 2 [https://ideone.com/9wIQ4F] problem c div2

»
3 weeks 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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem Moderate Modular Mode the editorial shows the answer is y− (y mod x)/2 but I haven't understood why this answer is always correct and how we reached this solution can anyone explain pls ?.