JaySharma1048576's blog

By JaySharma1048576, 9 months ago, In English

I hope you enjoyed the round. Here is the editorial. Do provide your feedback on each problem so that we can improve upon them the next time.

2A. We Got Everything Covered!

Author: JaySharma1048576

Hint 1
Tutorial
Solution
Feedback

2B. A Balanced Problemset?

Author: JaySharma1048576

Hint 1
Hint 2
Tutorial
Solution
Feedback

2C/1A. Did We Get Everything Covered?

Author: JaySharma1048576

Hint 1
Hint 2
Tutorial
Solution
Fun fact
Feedback

2D. Good Trip

Author: yash_daga

Hint 1
Hint 2
Hint 3
Tutorial
Solution
Feedback

2E/1B. Space Harbour

Author: yash_daga

Hint
Tutorial
Solution
Feedback

2F/1C. Fractal Origami

Author: mexomerf

Hint 1
Hint 2
Tutorial
Why unusual modulo?
Solution
Feedback

1D. Balanced Subsequences

Author: yash_daga

Hint 1
Hint 2
Tutorial
Solution
Feedback

1E. Paper Cutting Again

Author: yash_daga

Hint 1
Hint 2
Tutorial
Solution
Feedback

1F. Anti-Proxy Attendance

Author: JaySharma1048576

Hint 1
Hint 2
Hint 3
Hint 4
Tutorial
Harder bonus tasks
Solution
Feedback
  • Vote: I like it
  • +27
  • Vote: I do not like it

»
9 months ago, # |
Rev. 6   Vote: I like it -23 Vote: I do not like it

I guess people don't like to see what I wrote, and unfortunately I can't delete the comment (no option to do so), Treat this as a DELETED COMMENT.

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

    I don't really get why I was being downvoted initially (and even now)
    I am genuinely interested in knowing that, if someone can politely point out the reason. It will be much appreciated. (will take care about it next time I say something, feel free to see previous revisions).

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

      what was your comment?

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

        You can press the <-Rev. 6
        button to see the previous revisions (i.e. what my comment was).
        Thank you for your time.

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

          now i wonder too what made you have so many downvotes

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

C was tough!!

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

    It seems interesting, it's quite easy when find this greedy way in A but harder in C.

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

I resent working solution on C an hour after AC attempt. Ask questions.

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

JaySharma1048576 dario2994 kevinsogo Are code or explanations available for the 1F bonus tasks?

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

    The moment, when the greats despaired

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

    I can only provide their codes here because I don't fully understand them (My rating doesn’t allow me to understand it).

    dario2994's solution (70 queries)
    kevinsogo's solution (55 queries)
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +24 Vote: I do not like it

      dario2994's solution is roughly what I expected (split into up to 8 equal segments, then reduce to two segments).

      Not sure what kevinsogo is doing for $$$N>4$$$ though — would appreciate a proof regarding the total number of queries if there is one. It's also not clear to me why the find function never asserts false.

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

        It seems you have pinpointed the most crucial part of my code :)

        When I derived this algorithm, I had no proof that find would work, just empirical evidence that I tried it for many random tests and couldn't find a breaking case. (And I guess I proved it for small $$$n$$$ just by checking.) But now after you asked, I spent some more effort proving it, and I think I have come up with something that might work.

        Roughly, it seems to me that we need to show some sort of variation of the Borsuk-Ulam theorem.

        Let's make the array circular, and consider its half-open subarrays $$$[i, j)$$$, with appropriate wraparounds, i.e., $$$i$$$ is to be understood mod $$$n$$$, and $$$0 \le j - i \le n$$$. Note that the complement of $$$[i, j)$$$ is $$$[j, i + n)$$$.

        Then I defined a cost function $$$f$$$ from subarrays to 2D vectors satisfying the following:

        • near-continuity property: $$$|f(i, j) - f(I, J)|_1 \le 2$$$ whenever $$$|i - I| + |j - J| \le 1$$$. (The $$$|\cdot|_1$$$ in the former uses Manhattan distance.)
        • antipodal property: $$$f(i, j) = -f(j, i + n)$$$.
        • boundary condition: $$$f(i, i) = f(j, j)$$$ for all $$$i$$$ and $$$j$$$.

        And the goal is to show that $$$f$$$ has a near-zero, i.e., some $$$[i, j)$$$ such that $$$|f(i, j)|_{\infty} \le 1$$$. (In my code, you can see the definition of $$$f$$$ in the comments: its two coordinates are scost and bcost.)

        We can think about a continuous version of this, where the indices $$$i$$$ and $$$j$$$ are now allowed to have fractional values, and extend $$$f$$$ into a continuous function in a somehow "tame" way. The claim is that this extended $$$f$$$ has a zero. If this is true, then I'd think that the original, discrete version of $$$f$$$ must also have a near-zero nearby (...maybe, haha; alternatively, maybe the proof of the continuous version can be adapted to the discrete one) which is what we want.

        Thus, we seem to need to know the topology of "subarrays of a circular array". Well, I think it's a sphere! Map the subarray $$$[i, j)$$$ to the point on the sphere with longitude $$$\frac{j+i}{n}\pi$$$ and latitude $$$\left(\frac{1}{2} - \frac{j-i}{n}\right)\pi$$$. Then we can check that:

        • This respects the fact that $$$i$$$ only makes sense mod $$$n$$$ (because replacing $$$[i, j)$$$ with $$$[i+n, j+n)$$$ doesn't change things);
        • $$$[i, j)$$$ and $$$[j, i+n)$$$ map to antipodes;
        • empty subarrays $$$[i, i)$$$ map to the north pole, so the boundary conditions are satisfied. (Their complements $$$[i, i+n)$$$ map to the south pole.)

        So Borsuk-Ulam applies, and (the extended) $$$f$$$ has a zero.

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

        Now, for a proof of the number of queries, we have two quantities at every step:

        • The number of indices $$$i$$$ such that $$$a[i] = b[i]$$$. Let's call this $$$S$$$.
        • The number of indices $$$i$$$ such that $$$a[i] \not= b[i]$$$. Let's call this $$$B$$$.

        Here, we only consider "alive" indices, i.e., those that may still contain the target value. Initially, $$$S$$$ and $$$B$$$ are $$$\approx n/2$$$.

        Then, assuming that we are always able to perform a query on a subarray such that:

        • it kills roughly half the $$$S$$$ indices;
        • it splits the $$$B$$$ indices roughly equally into the two kinds;

        then we have the recurrences $$$S_{\text{new}} \approx B/2$$$ and $$$B_{\text{new}} \approx (S + B)/2$$$. (This is what the find function accomplishes; it looks for a subarray that will do this.)

        This then means that the sum $$$S + B$$$ decays with a factor of roughly $$$\phi/2 = 0.8090...$$$ at each step.

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

Can anyone accurately explain what is asked in Div2 D? I am not getting what probabilities do here since it is about summing values. Also at the start of each excursion are we summing all f or just the pair involved in that excursion?

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

    Expectation is one of the core application of probability.

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

    You could sum up all the values time their probabilities respectively to get the expectation value.

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

    They asked us to sum up the pairs involved in the excursion. The question is so poorly worded that I had the same doubt during the contest.

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

    I don't get it either. I get 7/9 but how does it relate to 777777784?

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

      They want you to kind of find exact values of p and q in p/q. There might be a possibility that you simulate the process and find average according to it or something (then you get the approximate answer by remaining well within the constraints or something). They don't want that, they want you to use math to find the expected value and not implement the selection process in it's entirety.

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

        Yeah, so what should I output? It says calculate p/q mod (1e9+7) but p/q is a fraction, and according to my knowledge the modulo operation is only valid between two integer operands. Btw based username :)

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

.

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

div2D another solution.

let X be the sum over all friendship values and N be the number of pairs (which is n * (n — 1) / 2). now consider taking random pair of people from 1 to k. what is the expected friendship value at iteration 1? obviously, it is X / N. what happens then? with probability p = m / N we will take a pair of friends, so we should add +1 to our X, with probability 1 — p we will take a pair of people who aren't friends, so we add +0 to our X. it means that we should increase our X by p * 1 + (1 — p) * 0 = p and continue iteration.

you can check my submission here: https://codeforces.net/contest/1925/submission/243687166

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

    Much concise and clearer than the tutorial, thank you for your explanation!

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

    Concise and efficient!

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

    great solution

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

    I am suffering trying to visualize how x+p actually does it,more like how is probability theory actually works in such case to make sense. May you suggest any tips/clues to help? Thanks.

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

    Thank you for the great explanation!

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

Can anyone explain the intuition for the GCD properties given in problem B. I got the idea by realizing that for a number k that divides x, you can divide the Ks x/k times over the n spots. Therefore, the answer is the maximum divisor k such that x/k>=n.

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

    It took me a while to see it too. But I guess if you have a,a,a,a,a...a,(x-(num)*a), we want the last term to be a multiple of a. Then you can kind of see that a has to be a factor of k

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

    You can think like this: You want to split $$$x$$$ into $$$a_1,a_2,...,a_n$$$ so as to maximise $$$gcd(a_1,a_2,..,a_n)$$$ subject to the constraints that $$$\sum_{i=1}^{n} a_i = x$$$ and $$$a_i \ge 1$$$ $$$\forall i$$$.

    Let $$$gcd(a_1,a_2,...,a_n) = g$$$, then $$$g \cdot (k_1+k_2+...k_n) = x$$$. Hence $$$g$$$ must divide $$$x$$$. So, you can basically iterate over all factors of $$$x$$$ in $$$O(\sqrt{x})$$$ time complexity, and take $$$max(ans,factor)$$$ if $$$x/factor \ge n$$$, as each $$$k_i \ge 1$$$, so $$$\sum_{i=1}^n k_i \ge n$$$. Where, $$$k_i$$$ is just the residual when $$$a_i$$$ is divided by $$$g$$$.

    Here's my submission for reference :)

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

      what is k in your solution , k1+k2...kn , i didn't understand that

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

        Oops, I missed it in my explanation:

        So, if $$$g$$$ is $$$gcd$$$ of $$$a_1,a_2,...,a_n$$$, that means $$$a_i = g \cdot k_i \forall i$$$ (definition of a divisor). Also, since $$$a_i \ge 1$$$, this gives us the condition $$$k_i \ge 1$$$. I hope, it is clear now :)

        You can ask if you have any other doubts.

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

As the solution of D1C is currently missing, I'd like to explain my solution:

Consider the paper lying flat on a table. The paper has two sides, gray and orange (according to the picture), with gray being originally on top. On every move, the crease lines we make are valleys, but for all layers with orange on top, these valleys actually become mountains once unfolded (since gray ends up on top).

After the first fold, at every point in time and at every point in the paper, there are an equal number of gray and orange layers on top of each other. This is because after the first fold, exactly half of the single gray layer was folded to orange and now there is one layer of both. After every subsequent fold, the balance will stay as all layers are treated equally.

Since an equal length of crease lines is created on each layer of the paper, this means that every round of folds after the first one creates an equal total length of new valleys and mountains. The length of valleys created in the first round of folds is $$$4\cdot\frac{1}{\sqrt{2}} = 2\sqrt{2}$$$. Thus, $$$V = M + 2\sqrt{2}$$$ always holds.

What is the total length of crease lines created on iteration $$$k$$$? Each crease line is $$$\frac{1}{\sqrt{2}}$$$ times the length of a crease line on the previous iteration, but the number of layers of paper doubled. Thus, the total length of created crease lines is multiplied by $$$\frac{1}{\sqrt{2}}\cdot2=\sqrt{2}$$$ every iteration. Thus, on iteration $$$2$$$, the total length of added crease lines is $$$\sqrt{2}\cdot2\sqrt{2} = 4$$$. Exactly half of this, i.e. $$$2$$$, is the total length of added mountains (and also the length of added valleys).

On each subsequent round, we add $$$\sqrt{2}$$$ times more mountains than the previous round. Let $$$x = \sqrt{2}$$$. Now, for fixed $$$N$$$, we have $$$M = 2 + 2x + 2x^2 + 2x^3 +\dots+ 2x^{N-2}$$$ and $$$V = 2 + 2x + 2x^2 + 2x^3 +\dots+ 2x^{N-2} + 2\sqrt{2}$$$.

The remaining part of the solution is boring: We can notice that the value of $$$M$$$ is a geometric sum, we can calculate its value with the formula $$$\displaystyle\frac{a(1-q^n)}{1-q}$$$, where $$$a$$$ is the first term, $$$q$$$ is the ratio between consecutive terms and $$$n$$$ is the number of terms. This also solves $$$V$$$ as $$$V = M + 2\sqrt{2}$$$. We need to represent the values of $$$M$$$, $$$V$$$ and finally $$$\frac{M}{V}$$$ in a form like $$$a+b\sqrt{2}$$$ with $$$a, b \in \mathbb{Q}$$$. To do this, we will have to get rid of square roots in denominators. This can get tedious, so the formula $$$\displaystyle\frac{a+b\sqrt{2}}{c+d\sqrt{2}} = \frac{ac-2bd}{c^2-2d^2}+\frac{bc-ad}{c^2-2d^2}\sqrt{2}$$$ can be very helpful. Exact details are left as an excercise to the reader. Splitting even and odd $$$N$$$ will be useful.

Derivation of the previous formula:

PS, Why is the mod $$$999\,999\,893$$$? Are there some cases where the answer isn't defined modulo $$$10^9+7$$$ or modulo $$$998\,244\,353$$$?

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

    Very intuitive explanation. I saw the question and thought there must be a numberphile videos on this.

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

    Yeah I did the same. I also wrote a struct to store $$$x+y\sqrt{2}$$$ which was very convenient and easy to debug.

    struct node{
    	int x,y;
    	node(){x=y=0;}
    	node(int xx){x=xx;y=0;}
    	node(int xx,int yy){x=xx;y=yy;}
    	node inv(){
    		node z;
    		z.x=x;
    		z.y=(mod-y)%mod;
    		int a=x*x-2ll*y*y%mod;
    		a=(a%mod+mod)%mod;
    		a=poW(a);
    		z.x=z.x*a%mod;
    		z.y=z.y*a%mod;
    		return z;
    	}
    	friend node operator +(node x,node y){
    		node z;
    		z.x=(x.x+y.x)%mod;
    		z.y=(x.y+y.y)%mod;
    		return z;
    	}
    	friend node operator *(node x,node y){
    		node z;
    		z.x=(x.x*y.x%mod+x.y*y.y*2ll%mod)%mod;
    		z.y=(x.x*y.y+x.y*y.x)%mod;
    		return z;
    	}
    	friend node operator /(node x,node y){
    		y=y.inv();
    		return x*y;
    	}
    };
    
  • »
    »
    9 months ago, # ^ |
      Vote: I like it +48 Vote: I do not like it

    $$$999$$$ $$$999$$$ $$$893$$$ is the largest prime number under $$$10^9$$$ under which $$$2$$$ is a quadratic non-residue.

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

      I might be missing something very simple, but why do we want 2 to not be a quadratic residue? Why would the existance of "sqrt 2 under modulo" be a bad thing?

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

        Answer is not defined if sqrt 2 exists (a + b root 2 can be written with other values of b)

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

          But the statement doesn't say "find $$$A$$$, $$$B$$$ for which $$$A+B\sqrt{2}\equiv MV^{-1} \pmod{p}$$$", it says "find $$$A$$$, $$$B$$$ for which $$$A+B\sqrt{2}=\frac{M}{V}$$$". The fractional value of $$$B$$$ is well defined regardless of the modulus used since it is defined by equality, not congruence under modulo. This means that the value of $$$B$$$ under modulo is well defined unless $$$B=\frac{p}{q}$$$, where $$$p, q\in\mathbb{Z}$$$, $$$\gcd(p, q) = 1$$$ and $$$q \equiv 0 \pmod{p}$$$.

          If instead, your argument is that "sqrt 2 doesn't exist under modulo $$$\Rightarrow$$$ it is harder to misunderstand the problem", then I think I can agree with that. But I still wouldn't change the modulus to something non-standard for this reason.

          Or am I wrong?

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

            You are correct, idk the reason either now

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

              Maybe because $$$c^2 - 2d^2$$$ (the denominator) can be $$$0$$$?

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

            This means that the value of $$$B$$$ under modulo is well defined unless $$$B = \frac p q$$$, where $$$p, q \in \mathbb{Z}$$$, $$$\gcd(p, q) = 1$$$ and $$$q \equiv 0 \pmod{p}$$$.

            So let's test this theory. If you take the math to its natural end you will find out that the value of $$$y$$$ such that $$$x + y\sqrt{2} = \frac{M}{V}$$$ is exactly, with no modulo reductions:

            $$$\frac{4a}{2b^2 - a^2}$$$

            Where $$$b = 2^{\lceil n/2\rceil} + 1$$$ and $$$a = 2^{\lfloor n/2 \rfloor} - 1$$$. Since $$$b$$$ is always either $$$a + 2$$$ or $$$2a + 3$$$ it's easy to check that no big prime can divide both $$$a$$$ and $$$b$$$, and thus no big prime can divide both the numerator and the denominator either. So we require $$$2b^2 - a^2$$$ to never be divisible by $$$p$$$ for our modulo of choice $$$p$$$. Assuming $$$b$$$ is nonzero modulo $$$p$$$ this gives

            $$$2b^2 - a^2 \not \equiv 0 \pmod{p}$$$
            $$$2b^2 \not \equiv a^2 \pmod{p}$$$
            $$$\left(\frac{a}{b}\right)^2 \not \equiv 2 \pmod{p}$$$

            So there you have it, as long as $2$ is a quadratic non-residue modulo $$$p$$$ we are guaranteed to be able to compute the answer. Since $$$2$$$ is a quadratic residue for both standard choices $$$p = 10^9 + 7$$$ and $$$p = 998244353$$$, this seems to me like a good enough reason to change the modulo.

            However, you might argue that even if $$$2$$$ is a quadratic residue, that doesn't mean that the answer is impossible to compute. After all, $$$a$$$ and $$$b$$$ are something specific and not whatever you want them to be. So let's go a bit further. I'll focus on the case where $$$n$$$ is even and therefore $$$b = a + 2$$$. Then

            $$$2(a + 2)^2 - a^2 = a^2 + 8a + 8 = (a + 4)^2 - 8$$$

            And so we want

            $$$(a + 4)^2 \equiv 8 \pmod{p}$$$

            To never happen. We know $8$ is a quadratic residue for the usual primes since $$$2$$$ is, so choosing $$$a \equiv \sqrt{8} - 4 \pmod{p}$$$ for either modular square root of $$$p$$$ fails. But wait! $$$a$$$ is not equal to just any number, it must be equal to $$$2^x - 1$$$ for some $$$x$$$. So in fact we need

            $$$2^x \equiv \sqrt{8} - 3 \pmod{p}$$$

            Clearly this is much better, there's nooooo way a power of $2$ just happens to give one of these two random values modulo $$$p$$$ for both of our standard primes. Unfortunately it just so happens that for both $$$p = 10^9 + 7$$$ and $$$p = 998244353$$$ the order of $$$2$$$ modulo $$$p$$$ is $$$(p - 1)/2$$$, and so $$$2^x \pmod{p}$$$ passes through every single quadratic residue modulo $$$p$$$.

            But there's still some hope! There's no reason both values of $$$\sqrt{8} - 3$$$ have to be quadratic residues... Aaaand it's dead, for $$$p = 998244353$$$ and $$$\sqrt{8} = 232390342$$$ we have that $$$\sqrt{8} - 3$$$ is a quadratic residue. But wait! Both of the choices actually turn out to give quadratic non-residues modulo $$$10^9 + 7$$$! Surely these silly authors should have just gone with that instead of their weird modulo...

            Nope, recall that $$$b = a + 1$$$ is only one of the possibilities, we also need to discard $$$b = 2a + 3$$$. Doing similar math we find that the bad case here is

            $$$2^x \equiv \frac{3\sqrt{2} - 5}{7} \pmod{p}$$$

            Significantly less clean than the previous case, but equally solvable. We now need to check the square roots of $2$ modulo $$$p = 10^9 + 7$$$ and see if the resulting expression is a quadratic residue. For $$$\sqrt{2} = 59713600$$$ this turns out to be a non-QR, and for $$$\sqrt{2} = 940286407$$$... wow! also a non-QR! Very unexpected!

            So in summary, while $$$p = 998244353$$$ is a no-go, it turns out that the authors could have safely chosen $$$p = 10^9 + 7$$$ and kept the answer computable. My question for you now is, if you were the author, would you rather go with the non-standard modulo that clearly works, or the standard modulo that basically only works because we won four coin flips in a row and could have easily sent contestants with more number theory experience on a wild goose chase like the one I just sent you on?

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

              My question for you now is, if you were the author, would you rather go with the non-standard modulo that clearly works, or the standard modulo that basically only works because we won four coin flips in a row and could have easily sent contestants with more number theory experience on a wild goose chase like the one I just sent you on?

              Now that I understand the reasoning behind it, I would definitely choose the non-standard modulo.

              Your comment seems a little passive aggressive, possibly because of my comments about "this is not a good enough reason to change the modulo", and I don't really like that. I wasn't trying to critisize the problemsetters' choices of modulo; I was just looking for a good explanation for that, and your comment managed to do that. Before your explanation, I didn't know why having 2 be a quadratic non-residue was desirable — now I know.

              Anyway, thanks for the explanation!

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

                Sorry if it came off that way, it's definitely a good and valid question and I was mostly trying to emphasize that one of the standard modulos working seems very unlikely at a glance.

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

Someone pls help me with my submission for C div 2 ... pls help me with the test case being failed ..

i am just checking for every character till kth place , ahead of its first index there must be present at least n-1 characters of each type for an answer..

243690556

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

    If you are just checking for n-1 occurences of each character ahead it might fail for abcaaabbbccc , n=4 , k=3 a,b,c, all have n-1 occurences ahead of them, but the string can't make all subsequences. I have not checked your code, but this might be the problem in your approach

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

    oh,Your approach is the same as mine during the contest, both wanting to use this method to check if there are n abcs This kind of arrangement string. However, this idea is problematic

    For example, aaabbbcccaaabbb

    You will find that there is no substring like CBA, but the result obtained using the above approach will be YES.

    So the correct way should be to use greed to check.like this

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

    I think I might used a similar approach and just came to know what was the problem with this approach. if I understand correctly you are checking that if the freq of the character you have right now is let's say x then every character must be present n-x times in its suffix, but the problem is that we are not considering the order of the characters in this approach, that's why this will give the wrong answer.

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

?

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

Hi for D cant we just directly put the values and answer in O(1).

Using pnc we get expected value = [((k*f)*(nC2) + (k*(k-1))*m/2]/(nc2)^2 ?

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

    I was getting wrong answer for test case 6. I think the limits just go boom. Can someone check the code and point where is the thing going wrong?

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

      Do all the math in this problem with long long instead of int. Otherwise you WILL have overflow in the multiplications.

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

I have a dp solution for 2C/1A.

Let dp[i][c] be the largest n such that any string of length n ending with c is a subsequence of s[1…i].

We have two relations

dp[i][c] = dp[i-1][c] for c != s[i]

dp[i][s[i]] = max(dp[i-1][s[i]], min(dp[i-1][c]) + 1); c = a, b, …

Now we know the answer is “NO” if and only if there exist c such that dp[m][c] < n. Choose that c as the last character in our answer, and continue doing this again. Now we can construct the solution from the back, then reverse it to get the answer.

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

    I also came up with same idea but got stuck at printing the non occuring subsequence . But finally again tried an hour ago and solved it.

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

Can anyone explain the formula in Div2D?The tutorial is like not writing it.

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

    Expectations can be tough to think about. Here is a mathematical proof for Div2D [Note that it requires basic understanding of probabilities and expectations]:

    Let pair 1 occur $$$X_1$$$ times, pair 2 occur $$$X_2$$$ times $$$\dots$$$ pair $$$m$$$ occur $$$X_m$$$ times in the $$$k$$$ excursions. Let $$$F(X_i, i)$$$ be the total contribution of $$$i-th$$$ pair to the total friendship. Hence, if total friendship is $$$F_{tot}$$$

    $$$F_{tot} = F(X_1 , 1) + F(X_2 , 2) + \dots + F(X_m, m)$$$ subject to $$$X_1 + X_2 + \dots + X_m = k$$$. Here, each $$$X_i$$$ is a random variable which takes value in the range $$$[0,..,k]$$$.

    Clearly, $$$E[F_{tot}] = E[F(X_1,1)] + E[F(X_2,2)] + \dots + E[F(X_m, m)]$$$ using linearity of expectation [even though $$$X_i$$$'s are contrained]. This is the power of linearity of expectation.

    What is $$$E[F(X_i, i)]$$$ ?

    If $$$i-th$$$ pair occurs $$$x$$$ times in the excursion. So, the contribution is $$$f[i] + (f[i] + 1) + ... + (f[i] + x - 1)$$$. Which can be simplified to $$$ f[i] * x + x * (x - 1) / 2$$$.

    It is easy to find $$$E[F(X_i,i)] = \sum_{x=0}^{x=k} F(x, i) P(X_i = x)$$$ = $$$\sum_{x=0}^{x=k} (f[i] * x + x* (x - 1) / 2) * P(X_i = x)$$$.

    How to simplify this?

    For each $$$f[i]$$$ the answer is just $$$\sum_{x=0}^{x=k} (f[i] * x + x* (x - 1) / 2) * P(X_i = x)$$$ = $$$f[i] * \sum_{x=0}^{x=k} x*P(X_i=x) + \sum_{x=0}^{x=k} x*(x-1)/2 * P(X_i=x)$$$

    Note that $$$P(X_i = x) = {k\choose x} * \frac{{(totalPairs-1)}^{k-x}}{totalPairs^k}$$$ .Idea, is that there are $$$k$$$ places. You have to reserve $$$x$$$ places. In each of the $$$x$$$ places, where you place the pair the probability is $$$\frac{1}{totalPairs}$$$ and in the remaining $$$k-x$$$ places where you don't, the probability is $$$\frac{totalPairs-1}{totalPairs}$$$. You can then multiply be $$${k \choose x}$$$. And, also $$$totalPairs$$$ is $$${n \choose 2}$$$.

    So, for each $$$f[i]$$$ the answer can be expressed as $$$f[i] * A + B$$$ where $$$A$$$ and $$$B$$$ can be precalculated as they don't depend on $$$i$$$.

    This gives the proof behind expression used in the editorial.

    Submission: here

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

      Even though I'm not the original OP, Thankyou so much for this!

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

Div2 is pretty good for me, though why is Div2C reused as Div1A? I think that's a pretty cheap move, you know...

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

my submission Logic I am trying to make blocks which have k smallest character greedily.

It's failing on test case 2, can anyone tell me what's wrong with my logic, code is self explanatory

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    int pos = find(all(v),1)-v.begin();
    ans += pos+'a';
    

    bro this part is wrong you should add last character of the block but you adding the first character from block which has count 1,let for k=3 block is "abbc" you should add 'c' but you adding 'a'. replace above two lines with

    ans += s[i] ;
    
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you, but adding s[i] means that this character will definitely have a frequency of 1, but I am adding the character that also have a frequency of one,so how does it affect the final answer.This part is not clear by me. Can you please explain this, or just give me counter test case it would be much helpful.

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

        Let n=2 , k=3 , s="abbcab" In this 1st block will be "abbc" and 2nd block which is incomplete will be "ab" In 1st block you adding 'a' instead of 'c' , because 'a' also have count 1 and find function returns iterator of first matched element. Your logic giving ans "ac" but it is present and ans should be "cc".

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

In div2B "The maximum GCD that can be achieved is always a divisor of x" . Can anyone please explain why is that? I'm not getting this point.

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

    gcd(a1,a2,a3...an)=gcd(a1,a1+a2,a1+a2+a3,...,a1+a2+a3..+an) so at the end we get sums of all sub problems which is just x so answer is gcd(a1,a1+a2,....,x) so ans is always divisor of x .

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

    Consider an array of numbers $$$a_{1}, a_2, ..., a_n$$$.

    Let $$$g$$$ be the greatest common divisor (gcd) of all these numbers.

    Since every number is a multiple of $$$g$$$, we can express each number as follows:

    $$$a_1 = g * k_1$$$

    $$$a_2 = g * k_2$$$

    ...

    $$$a_n = g * k_n$$$

    where $$$k_1, k_2, ..., k_n$$$ are positive integers.

    The sum of these numbers is:

    $$$a_1 + a_2 + ... + a_n = g * (k_1 + k_2 + ... + k_n) = x$$$

    Therefore, $$$g$$$ should be a factor of $$$x$$$.

    And here all $$$k_i$$$'s are positive integers so $$$\sum k_i \geq n$$$ hence we have to find smallest factor of $$$x$$$ that is greater that or equal to $$$n$$$ ,say $$$f$$$

    Then $$$x/f$$$ is our required $$$g$$$

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

Why div2 D must take the probability modulus, and can not be expressed as a decimal like normal problems, and give a precision requirement?

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

Why so many math problems

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

For 1D,I have a easier solution.243652894

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

    By the way; it is 2D. Can you please explain your solution?

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

      We can treat each pair of friends separately. Regardless of the pair of friends, the probability of selecting them is $$$p=\frac{1}{\frac{n(n-1)}{2}}$$$.

      At the jth excursion, if the ith pair of friends is selected, then its contribution to the answer is $$$f_i+q_i$$$, where $$$q_i$$$ is the expected value of having selected the ith pair of friends earlier, and we get $$$q_i=p\times(j - 1)$$$. Then if we are not sure if the ith pair of friends was selected (the probability of selection is $$$p$$$), the contribution of the ith pair of friends to the answer in the jth tour is $$$p(f_i+p\times(j - 1))=pf_i+p^2(j - 1)$$$.

      Combining the contributions to the answer from the i-th pair of friends in the kth excursion, the

      $$$\sum_{j = 1}^k pf_i+p^2(j - 1)$$$
      $$$=pf_ik+\sum_{j = 1}^kp^2(j - 1)$$$
      $$$=pf_ik+p^2\times\frac{k(k-1)}{2}$$$

      After the contribution of the ith pair of friends to the answer has been counted, the answer is obtained by adding up the contributions of each pair of friends to the answer.

      $$$\sum_{i = 1}^mpf_ik+p^2\times\frac{k(k-1)}{2}$$$
      $$$=pk\times sum_f+mp^2\times\frac{k(k-1)}{2}$$$

      This is the result.The time complexity is $O(t\log MOD + m)$.

      Look here.It's my new solution.243708880

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

In Problem "2D. Good Trip" Tutorial,

Shouldn't it be "x Choose k" inplace of "k Choose x"?

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

Can someone help me in finding what did i do wrong in 2C

243641202

i was trying to make the ith letter x by checking is every combination of previous letters is possible or not

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

For Div2D, each excursion increases the expected friendship value of every (non-zero) friendship pair by $$$\dfrac{1}{p}$$$, where $$$p$$$ = $$$\dfrac{n(n-1)}{2}$$$. So the expected friendship value of the $$$i$$$-th pair after $$$j$$$ excursions is $$$f_i + \dfrac{j}{p}$$$. So the expected friendship value of the pair picked after $$$j$$$ excursions (i.e. for the $$$(j+1)$$$-th excursion) is $$$\sum\limits_{i=1}^{m}\dfrac{1}{p}{(f_i + \dfrac{j}{p}})$$$.

Using this, we can come up with a straight-forward formula for the answer:

$$$\sum\limits_{j=0}^{k-1} \sum\limits_{i=1}^{m} \dfrac{1}{p}{(f_i + \dfrac{j}{p})} $$$

Which simplifies to:

$$$ \dfrac{k\sum\limits_{i=1}^{m}{f_i}}{p} + \dfrac{k(k-1)m}{2p^2} $$$

Code : 243709626

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

For C I created a dynamic programming solution : Can someone verify as I am getting TLE on test 3..

dp[i][L] = 1 (if we can make all possible strings of length L using characters 'starting' from index i) else 0 Now we can loop over every character find the smallest index greater than i where it occurs using a character-set map . Say,the smallest index greater than i is ind, (if it doesnt occur we can make dp[i][L] =0) . So, if dp[ind+1][L-1] is true that means we can make all strings possible starting with the character I am currently checking.

As the time complexity is 26*26*O(m) , it wont pass however I was interested in its correctness.

243709963

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

    İf you still interested in the solution you can see my submission list I made the same mistake if you need any help you can ask me

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

Why does the submission for 2C TLE? 243710719 Isn't the time complexity $$$O({m^2}n + mnk)$$$ which should pass within the time limit?

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

    The sum of m over all test cases is mentioned to have an upper bound of 10^6 so it wont pass

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

Problem B

Can someone kindly explain why the condition for the loop is i*i<=x?

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

    we want to check divisors $$$\le \sqrt{x}$$$. for each divisor $$$d \le \sqrt{x}$$$, we also check $$$x / d$$$, because it will be another divisor of $$$x$$$, and we don't need to check any divisor $$$\gt \sqrt{x}$$$, all of them were already checked.

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

    To Reduce TC:

    if i is a factor then x/i is also a factor, similarly for sqrt(x).We need to loop till sqrt(x) because all factors after it had already been taken [ by (x/i)]

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

i thought in div2c we have to print string which contains all the subsequence which is not present in original string

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

Can some please explain why the following solution doesn't work for problem C

~~~~~

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

Observation in div2. D: all the sums of expected values of every friendship increases in a pattern: if n = 3, m = 1 and there is a bond of 1 between 1 and 2, in the first turn the expected value is 1 * 1/3 = 3/9. In the second turn, 2 * 1/9 (increased) + 1 * 2/9 (still) = 4/9. On the next turns it goes like 5/9, 6/9 and so on. The contribution of every bond can be calculated in O(1).

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

Solution for Div-2 C is giving wrong answer in test case: 1 4 3 12 abcaccabcabc

Output: NO aaaa

As it is clearly visible 'aaaa' is a possible subsequence

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

243618528 can someone point out as to why this is failing on pretest 2? My thought process was that since we need atleast n occurences of a character in a string to count that , also there could be a case where a character may not be present in the string at all. So i found which characters among the first k were present.

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

There should be at least one testcase in the pretest which can cause TLE or a large testcase should be added on the pretest. I got passed in the pretest section of B simply on the first attempt and didn't came with another try for optimized solution, which caused tle on the system testing.

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

problem B is a subproblem of problem 803C - Maximal GCD.

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

E's solution k got declared as int while the bound is <= 1e12. Even in the test case there is some test with k >= 1e10. I submitted the code and it actually worked ?

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

Hi, I don't know if it's legitimate to ask for this but yesterday I got a tle on the div2 E 243653603

However, submitting the exact same code in C++ 64bits makes it ac (in 1sec). 243744788

Please, would it be possible to get a rejudge ? Also if anyone knows why C++ 64 bits is that much faster, I'll gladly take it (the last time I used C++ 64 bits, I got tle because of it...).

Thanks by advance for the help

JaySharma1048576

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

    Iirc when you're doing many operations with 64-bit integers, 64-bit compilers are significantly faster. I believe 64-bit compilers are faster (or at least not slower) most of the time. Where did you get tle with 64-bits and ac with 32-bits?

    Also, this has happened to quite a few people before and I don't think anyone has gotten a rejudge, so you're probably out of luck.

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

      Thanks for your answer, it sounds like a reasonable explanation.

      In this problem 1250B - The Feast and the Bus I got tle in C++ 64 (243748301) and ac in C++ 17 (243748727). I also have a friend who got tle for similar reasons on a shortest path problem I think ? I'll try to find it but it was a long time ago

      By the way, if the runtime can change that much, during the testing phase, can't they try to submit solutions in both C++ 64 bits and 32 bits to avoid such things happening ?

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

What is wrong with my logic for div 2D?

Each of the $$$m$$$ pairs of friends has a probability of being chosen $$$\frac{2k}{n(n-1)}$$$ times over the $$$k$$$ excursions. Then, the expected value can be calculated by summing $$$\frac{(2f_i+(\frac{2k}{n(n-1)}-1))(\frac{2k}{n(n-1)})}{2}$$$ for all $$$1 \le i \le m$$$. (This is by using sum of arithmetic series).

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

    You are looking for the probability of a pair being chosen a fixed number of times (probability that the pair gets selected i times).

    What you are doing is just like, wrong

    I would recommend you to learn a bit about expected value (definition, linearity) and to do things more formally. You want E(S) where S is the sum of friendship values of all k pairs chosen for the excursions.

    S = X1 + ... + Xm where Xm is the sum of friendship values of pair i (over all the excursions it was chosen for).

    By linearity: E(S) = E(X1) + ... + E(Xm)

    Now, to compute E(Xi) you can fix how many times the pair i has been chosen and you end up with a simple sum to compute (which is a bit similar to what you sent, except you need some binomial coefficients for the probabiltiy).

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

      First of all, thank you for the reply. Sorry, but I don't understand what you mean by "fix how many times the pair i has been chosen". Could you provide an example of calculating $$$E(X_i)$$$ using "binomial coefficients for the probability"?

      Thank you very much.

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

        So let's consider pair i.

        $$$E(X_i) = \displaystyle\sum_{j = 0}^{k} {val(j) \cdot P(X_i = j)}$$$ (I technically skipped a step here, but overall it's just partitioning the events depending on how many times the pair i was chosen).

        And $$$val(j) = f_i + ... + (f_i + j - 1)$$$ (which has a closed form that you pointed out in your original comment)

        Now, you are looking for $$$P(X_i = j)$$$ which actually follows a binomial law.

        If you don't know what that is, I'll just try to explain intuitively: - you have probability $$$p = \frac{1}{\frac{n \cdot (n - 1)}{2}}$$$ for the pair i to be chosen at a fixed excursion

        • so if you fix the $$$j$$$ excursions at which the pair i is chosen, the probability to be chosen exactly at these excursions is $$$p^{j} \cdot (1 - p)^{k - j}$$$

        • you have $$$\binom{k}{j}$$$ ways to chose the $$$j$$$ excursions at which the pair will be chosen

        So overall, $$$P(X_i = j) = p^{j} \cdot (1 - p)^{k - j} \cdot \binom{k}{j}$$$

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

Problem D can also be solved in $$$O(m)$$$. See here.

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

2 line Solution for Div 2D

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

C is really hard for me. Frustrated : (

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

2D has a direct formula.

Let $$$d=\frac{n\left(n-1\right)}2$$$, which denotes the number of pairs of children, and $$$s=\sum_{i=1}^mf_i$$$, which denotes the sum of friendship among each pair of friends in the beginning.

In each round, the probability of choosing a pair who are friends is $$$p=\frac md$$$.

Then, after $$$i$$$ rounds, the expected value of increase is $$$ip$$$, so the expected value of sum of friendship among each pair of friends is $$$s+ip$$$. Then, the expected value of friendship of the chosen pair in the $$$i$$$-th round is $$$\frac{s+ip}d$$$.

Therefore, the answer will be $$$\sum_{i=0}^{k-1}\frac{s+ip}d=\frac{ks}d+\frac{mk\left(k-1\right)}{2d^2}$$$. It can be calculated using constant time.

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

    Great solution. I didn't notice that sum of $$$k$$$ is bounded in the problem statement. So although I came up with an $$$O(m+k\log p)$$$ ($$$p$$$ is the modulo) solution, I didn't think it could pass and did not submit. So I tried to transform my original formula (which is similar to the expectation of a binomial distribution) into a direct formula through an algebraic way during the whole contest. Of course I failed. Now I realize that I should use an alternative explanation to form another simpler formula instead of transforming the original formula directly.

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

I have just done D to upsolve, should have read that in contest. I recently solved a problem 1761F1 - Anti-median (Easy Version) and used this as a subproblem to get sequences in which there will definitely exists a k regular bracket as subsequence. :(

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

Anyone using sqrt decomposition to solve div2 problem E? I divide the sequence into $$$\lceil\sqrt n\rceil$$$ blocks, with each block at most $$$\lceil\sqrt n\rceil$$$ length (the last block is cutoff to a lower size). Then for each insertion of harbour, I find its left harbour $$$l$$$ and right harbour $$$r$$$ and then update the blocks in $$$[l,r]$$$; for each query $$$[l,r]$$$, I also retrieve the information in blocks in $$$[l,r]$$$. I think it should cost $$$O(q\sqrt n)$$$ and should get passed. However I got time limit exceeded: https://codeforces.net/contest/1925/submission/243770890. Could anyone help?

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

    $$$\Theta\left(q\sqrt n\right)$$$ is too large for this problem because $$$q\sqrt n=164316767.25154984$$$ and the constant is not small enough.

    It is much better to process a problem with interval assignments and interval queries using a segment tree which has time complexity $$$\Theta\left(n+q\log n\right)$$$ than a block array which has time complexity $$$\Theta\left(n+q\sqrt n\right)$$$.

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

    My AC square root decomposition code: 244297448

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

I have to admit this was a great contest. Unfortunately in Div 2 B i forgot to check sqrt(n) and only checked everything else , noticing this costed me 40 minutes but im glad i solved it anyway.

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

Can anyone please explain div2E?

Thanks in advance.

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

Can anyone give a counterexample or explanation why this solution doesn't work? https://codeforces.net/contest/1925/submission/243789503

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

Nice explanation

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

Can somebody please provide an inductive proof for Case 2 of 1D?

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

Problem E: My submission (WA on test 8)

My approach:

▶ Calculate the initial cost for each N ship and build a segment tree on it.

▶ Say a new harbour is built at position $$$z$$$ and value $$$v$$$. Say The nearest left neighbour is $$$(x, v_1)$$$ and the nearest right neighbour is $$$(y, v_2)$$$. Then the cost of ships in the segment $$$(x + 1, z)$$$ is decremented by $$$(v_1 * (y - z))$$$, and the cost of ships in the segment $$$(z + 1, y - 1)$$$ gets multiplied by $$$(v / v_1)$$$.

▶ I used lazy propagation for range multiplication/division and addition.

Can someone point out the mistake?

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

    Take a look at Ticket 17298 from CF Stress for a counter example.

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

    how are differentiating whether addition was performed first or multiplication ?
    order matters here right?

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

      I am storing the lazy values $$$(M, A)$$$ for each node of the segment tree, which means that we must multiply the value at that node with $$$M$$$ first and then add $$$A * (r - l + 1)$$$ (r — l + 1 is the length of the segment covered by node) to it, i.e., $$$(val * M + A * (r - l + 1)$$$. Now let's say we are pushing the lazy information of a node, say $$$(M_1, A_1)$$$ to its child with lazy information $$$(M_2, A_2)$$$ then we can observe that $$$(val * M_2 + A_2 * (r - l + 1))$$$ becomes $$$(val * M_1 * M_2 + (A_2 * M_1 + A_1) * (r - l + 1))$$$. Hence, we can accordingly modify the lazy_multiply and the lazy_add values. ( NOTE: The identity for lazy_multiply and lazy_add are 1 and 0 respectively. Since we also need to do the division operation, there is also a lazy_div for each node in actual implementation. )

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

        t[l].lazy_add = (t[l].lazy_add / t[id].lazy_div) * t[id].lazy_mul + t[id].lazy_add
        You are rounding values here. t[l].lazy_add may not be divisible by t[id].lazy_div

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

          Observation: $$$A_i$$$ is always of the form $$$val_i * xyz$$$ and t[id].lazy_div is always a divisor of $$$val_i$$$ so there will be always an exact division.

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

    it works i do it in same way. code

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

      Thank you for letting me know that it's correct.

      How did you handle division without a lazy value for division? And why did you take mod? The original problem wasn't asking us to print the answer modulo M.

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

        I guess the problem in your solution is that the lazy division values can overflow if multiple updates are stacked on top of each other without pushing further. tmpzlp's solution uses a big prime modulo larger than the largest possible answer, and this solves all of your problems:

        • Since the modulo is larger than the largest possible answer, the value reduced modulo will be correct.
        • Since the modulo is prime, we can perform division via multiplication by modular inverse. Now we don't need a separate lazy division variable (since division is now multiplication) and the values won't overflow since we reduce them in modulo, though __int128 needs to be used for multiplication.
        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Got it. Thank you, sir. Btw, such a cool usage of __int128 ^w^

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

Can anyone explain in 2B, why we need the condition n <= i? I'm not knowing what case it works for

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

    We are just walking from 1 to sqrt(x)

    When x divides i, that means there are 2 divisors of x, not just one -> i , x / i

    The first condition handles the first divisor and the second handles the second

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

      so the factors of x that are greater than sqrt(x) are just the same product we have seen before sqrt(x) but written vice versa?

      like if we have seen (a*b) before square root it's the same numbers repeating again but in reverse like b*a?

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

How to solve Div2E/Div1B? Still waiting for the editorial :\

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

    My solution:

    For each harbor I keep the sum of distances of every ship between this harbor and the next harbor. I can do it using a std::set maintaining the positions of all available harbors. Now i put the mentioned value for a harbor at position x inside a Fenwick tree ( the xth number in the Fenwick tree, if there is a harbor at position x, contains the value of that harbor). Now let's talk about answering each query, in each query i First take the sum of all values of harbors inside that segment. It's really easy to see that there are some ships in the segment that I'm not counting their distance but I should, and there are some ships outside that I'm counting their distance but I shouldn't. I can calculate these missing/extra values using the std::set we maintained above. It is a bit mathy, so I recommend taking a look at my implementation to understand it better: 243623915

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

      Your method doesn't require lazy propagation. Great.

      Can you please tell me if this approach will work? (Although it is a bit messy to implement)

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

Can anyone tell me what's wrong with my code on Problem C. I compared it with the editorial and think they are the same, but I got WA. https://codeforces.net/contest/1925/submission/243847499

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

For the Div2 D, for considering the incremental sum of pairs, why they have assumed that for a excursion only 1 pair can be repeated and they only accounted that pair repeated k x times, and multipled the whole by m? Why can't 2 or more pairs be a part of excursion considering that sum and probabilites would change and the final solution would also, right?

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

Can someone tell me how to determine the time complexity of div 2 b?? according to the constraints if feels like O(n) solution to work since n<=1e8 but my O(n) solution gives tle?? here is the solution 243588276

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

    You have to consider the number of test cases also

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

      I haven't had any problems like this before and i have never considered the number of test cases before as well, is this because in most problem there is a statement like:- "It is guaranteed that the sum of n and sum m over all test cases does not exceed 1e5 and the sum of k over all test cases does not exceed 2⋅1e5." While this question didn't??

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

Please help me in identifying the mistake in my code. Do you have any counter example for this? Getting wrong answer on test case 3639 of test 2. Submission

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

Will we see $$$1B \; 1C\; 1E$$$ solutions?

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

    The editorial for 1C has been added. Unfortunately, there was an Indian ICPC Regionals contest the very next day of this contest and all three of us were judges for that contest. We didn't get any time on Sunday to write the formal tutorials in the editorial and the author of 1B and 1E was busy today. Hence, the delay.

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

I think there is a little mistake in the constants in d1F editorial.

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

    Yeah, you are right. I probably messed up something while writing the editorial. But it was an editorial-only bug. The constraints in the problem are correct and according to the better bounds found by you. You can check that $$$\log_{1.116} 10^5 = 104.8$$$ which is according to the value of $$$x$$$ and not $$$y$$$.

    And yeah, the solution works only after rounding. There is a buffer of just $$$1$$$ query between the constraints and the calculated bound so you have to be quite precise.

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

      Actually, surprisingly my solution with the incorrect constant passes the tests when always rounding down (243937391), even though theoretically it should fail. I guess it is hard to kill solutions with slightly suboptimal constants at high values of $$$n$$$, as sometimes you'll get lucky and get 3 queries when the worst-case is 4.

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

unable to understand why they are doing this in div2B

if(n<=i){ ans=max(ans,x/i); }

edit: nvm for anyone with the same doubt check this explanation https://codeforces.net/blog/entry/125137?#comment-1111266

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

Problem C's solution was very nice, but may be very difficult to prove. But, it made me wonder if authors prove their "greedy" solutions or not? And this is NOT to criticize the editorial. I was wondering if there have been cases where an author came up with a problem, which had an obvious greedy solution but later came out to be wrong because someone came up with a test-case where it didn't work. Maybe experienced participants can tell.

Otherwise, if every author proves their greedy problem I believe they should post their proofs as well. It will benifit others a lot. Since, greedy is something which doesn't come naturally to everyone and a lot of competetive programmers struggle with it. If something reduces to some standard greedy, then it's okay. But in other cases a proof should always be present in my opinion. That would at least guarantee that someone doesn't hack the author's solution

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

    I was wondering if there have been cases where an author came up with a problem, which had an obvious greedy solution but later came out to be wrong because someone came up with a test-case where it didn't work.

    This probably happens every now and then during the problemsetting process — usually this would be noticed during stress testing. But sometimes shit happens and these mistakes aren't caught, even with stress testing. For example Codeforces Round 846 (Div. 2) had a problem C with an intended greedy solution, but it turned out to be incorrect. The round got unrated and the problem was deleted as it was unsolvable with the given constraints.

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

    Well, I do have a proof for 2C/1A. It is easy and intuitive so I felt it unnecessary to explain in the editorial.

    Let the counter-case we are building using the greedy until we reach the end of $$$s$$$ be $$$t$$$ and the final counter-case be $$$c$$$. There are two things that must be proven:

    1. If $$$\lvert t\rvert < n$$$, then $$$c$$$ is not a subsequence of $$$s$$$.
    2. If $$$\lvert t\rvert=n$$$, then all possible strings of length $$$n$$$ formed using the first $$$k$$$ English alphabets are a subsequence of $$$s$$$.

    Firstly, notice that the greedy algorithm divides the string $$$s$$$ into some blocks with each block (except possibly the last one) containing all the first $$$k$$$ English alphabets and where the last character appears exactly once in the block in the end.

    So, if you are aware of the well-known greedy algorithm to check if a given string $$$a$$$ is a subsequence of another string $$$b$$$ or not, you can notice that the first character of $$$t$$$ must match to the last character of the first block of $$$s$$$ since there is no better choice for it, the second character of $$$t$$$ must match the last character of the second block of $$$s$$$ because there is no other choice between the first chosen character and the last character of the second block and so on. Now if $$$\lvert t\rvert < n$$$, the first character that is in $$$c$$$ and not in $$$t$$$ is not present in the last remaining block (possibly empty) of $$$s$$$. So, the string subsequence matching algorithm fails and $$$c$$$ is not a subsequence of $$$s$$$.

    Now, if $$$\lvert t\rvert=n$$$, we already know that $$$t$$$ is a subsequence of $$$s$$$. Now, the $$$i^{th}$$$ character in $$$t$$$ is the last character of the $$$i^{th}$$$ block of $$$s$$$, If you replace it with any other character, it will still be present in the $$$i^{th}$$$ block of $$$s$$$ since these blocks contain all the first $$$k$$$ English alphabets. So, no matter what changes you do to the string $$$t$$$, it will still remain a subsequence of $$$s$$$. This proves the second part.

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

Can someone help me guessing test case where this test solution failed [submission] I have tried all test cases that everyone has commented in the comment boxes

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

In DIV2C / DIV1A while building the counter-case, why is it always optimal to pick the first character as 'the one whose first index of occurrence in the given string is the highest'?

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

    We can show that this construction will fail iff the string s is good (as defined in the problem)

    Construction succeeds => string is not good

    Construction fails => there exist at least n contiguous blocks with each block containing at least one instance of the first k chars. (ex. w = aabcbbcab can be grouped into [abc][abc]b). This form allows you to generate any subsequence of length n, so the string is good.

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

Your reason for special modulo at problem 2F/1C is preposterous at best. B is a rational number outside of modulo. What you are doing is childish smh.

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

Will-be-added-soon forces.

The contest was over about 4 days ago. However, the tutorials of 1E and 1B are still not updated. Just showing the code is confusing and meaningless.

Are you already forgotten this important Codeforces contest?

plz update it as soon as possible.

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

    Hi, sorry for the delay, the editorial for all the problems have been added.

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

can somebody explain to me how do we get 7/9 on third sample of problem div2 D

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

Problem A and B were nice.

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

Hello A_G, Can you please explain your solution for D — Good Trip. Also it'll be helpful if you can explain how you are calculating and using inv array. Thanks!

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

A simpler version of Div2C 1925C - Did We Get Everything Covered? on leetcode.

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

I never reached the first hint for 2B, this was my step to solution:

$$$g = gcd(a_1, \dots, a_n)$$$
$$$g \cdot (\frac{a_1}{g} + \dots + \frac{a_n}{g}) = x$$$
$$$\frac{a_i}{g} \geq 1 \rightarrow s = \sum_{i=1}^{n} \frac{a_i}{g} \geq n$$$
$$$ g \cdot s = x$$$

Searching for biggest g where s >= n.

»
9 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it
Similar Problem To Problem C Without Constructing Solution 

C. Strong Password

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

This formula can (probably) make div1E much easier:

Fix k. Let f(m,n) be the solution (expected number of cuts to make (m,n) -> (m0,n0) such that m0*n0<k). Then (if m*n>=k) f(m+1,n+1)+f(m,n)=f(m+1,n)+f(m,n+1). (How to prove? hint: try brute forcing to find f(m,n) then do basic algebra)

All we have to do left is try to handle base cases and reduce (m,n)

Sorry for my messy code (too many corner cases to cover, even had to generate random tests to catch all of them ;-;)

Happy Lunar New Year everyone ;)

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

Can somebody please explain to me what is trivial factorization?

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

In tutorial of 1/E, there seems to be a duplication in the multiplication of probability and I'm very confused. For example, in the first case I wonder why the conditional probability of lines from $$$reqv+1$$$ to $$$m-1$$$ is $$$\frac{1}{n+reqv} + \cdots + \frac{1}{n+m-2}$$$ instead of $$$\frac{1}{reqv+1} + \cdots + \frac{1}{m-1}$$$. Can someone help me?

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

"Keep adding this character to the counter-case until its length becomes n . This is a valid string which does not occur as a subsequence of s " can any one explain why this always true .

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

I don't know if anyone has noticed that 1D is very similar to the first example (algorithm P) of Knuth's TAOCP-4A-7.2.1.6. I think if you read it, the topic might become easier to understand.

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

Can somebody explain the third test case answer: (7/9)? I want exact calculations. I don't get, how they got this answer.

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

Problem B Can someone kindly explain the implementation showed in the solution?

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

    Its like getting all divisors of x then among then getting the first number smaller or equal to x/n

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

Better solution for 2D. Good Trip:

If you use (xC2)*(kCx) = (kC2)*((k-2)C(x-2)), contribution of excursions becomes (kC2)/d^2. which can be calculated in constant time. So complexity is just taking inputs: O(m)

https://codeforces.net/contest/1925/submission/261739022

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

I solved 2D in O(t) time using linearity and arithmetic sum formula.

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

In div2 C why this approach is failing? The approach:i am mantaining a hashmap of char vs freq so now i traverse the string trying to take every char from first k char as my first char of string of NoAnswer then if other chars have freq more than or equal to n-count where count is the first char that has occured how many times

if at any time my condition fails that means answer is no with string as all chars same till a point then the char which failed the condn

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

No disrespect ,but atleast prove the goddamn claim you made in problem C, i mean it could be intuitive to you as author but there are low rated participants in these rounds too or if you dont consider them dont bother writing DIV2 rounds.

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

I am not getting in the case 1 How c(n + m, m) can give all valid sequence.

In terms of the final solution, you are saying that you will end up with a list of n+m symbols, and then whichever is smaller of those will determine the number of pairs possible.

To turn it into an actual number, there are n+m symbols and C(n+m,n) = C(n+m, m) = C(n+m,k) ways to arrange them. So the problem essentially says any arrangement works. Suppose we have two ( and two ), i.e. n=2, m=2, k=2.

The ways to arrange those symbols net of duplicates is 6: (()), ()(), ))((, )()(, )((), ())(.

I think only two of those allow constructing a subsequence of two balanced pairs. namely the first two. Which is not what formula gives.

yash_daga JaySharma1048576 mexomerf can you Please help with this ?

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

how can people even implement something like 2E/1B in under two hours?

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

good evening community

how to build the intuition similar to that of "https://codeforces.net/contest/1924/problem/A" problem explained in the editorial.

also how to think these type question?

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

I know I am little bit late but can anybody explain me why am I getting wa here:

https://codeforces.net/contest/1924/submission/284378497

My logic seems correct to me

»
20 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

For $$$E$$$ lazy segtree isn't required normal segtree is enough