Nezzar's blog

By Nezzar, history, 8 months ago, In English

Thanks for joining us today! Here is the editorial for today's problems:

1478A - Nezzar и разноцветные шары

Tutorial
Solution

1478B - Nezzar и счастливые числа

Tutorial
Solution

1478C - Nezzar и симметричный массив

Tutorial
Solution

1477A - Nezzar и доска

Tutorial
Solution

1477B - Nezzar и бинарная строка

Tutorial
Solution

1477C - Nezzar и красивая карта

Tutorial
Solution

1477D - Nezzar и тайные перестановки

Tutorial
Solution

1477E - Nezzar и турнир

Tutorial
Solution

1477F - Nezzar и шоколадные плитки

Tutorial
Solution
 
 
 
 
  • Vote: I like it
  • +214
  • Vote: I do not like it

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

Please add comments in code solutions of editorials to make it more readable

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

    The intent of the code is obvious to its writers and other experienced participates. No one will know which lines you don’t understand.

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

      Understandable, but it can be quite tricky to understand for beginners, and I would think that the purpose of the editorial would be to help competitors, beginner or advanced. CP code is notorious for being unreadable.

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

        Then it would make more sense to make editorial code readable rather than to add comments to unreadable code, but I don't see any readability issues in the code of this particular editorial.

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

I thought that the problems were really nice. Kudos to all the authors! :)

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

div1C Furthest Points

Pick an arbitrary point, and in each iteration, select the furthest point from previously chosen point among all available points. Indeed, we can prove the correctness by contradiction.

what the f**k How did I miss that

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

    WHat the fuck!

    i thought this during contest and thought it is way too simple to be a solution to div1C

    I should commit suicide

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

Extremely nice contest! Thank u for your work!

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

Let $$$g_0 = \gcd(x_2,x_3,\dots, x_n)$$$.

Should it be "let $$$g_0 = \gcd(x_2,x_3,\dots,x_{n-1})$$$"?

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

    Thanks! We will fix it later.

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

    How can we write $$$g$$$ using $$$g_0$$$ and $$$x_n$$$. And another question is even if we are able to write $$$g$$$, how can we generate all multiples of $$$g$$$ ?

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

      (0,g) — > (0,g,2g)

      2*(2g)-g = 3g -> (0,g,2g,3g) 2*(2g)-0 = 4g -> (0,g,2g,3g,4g) ....

      But with (0,g0,xn) I can't generate g = xn-g0 for example where s=1, t=1

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

        It's said that $$$g=sg_0+tx_n$$$, and there are multiple pairs $$$(s,t)$$$. An even $$$s$$$ is absolutely existed, so let's regard $$$s$$$ as an even one. With $$$0$$$, $$$x_n$$$, and $$$g_0$$$,it's easy to get $$$\frac{s}{2}g_0$$$ and $$$tx_n$$$, then $$$g=2\times \frac{s}{2}g_0+tx_n$$$.

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

          Can you please explain why there always exits s that is even? By the way why we can substract x1 for every xi and does not Affect the answer?

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

            I'm so sorry! I made a big mistake in my previous replication, $$$s$$$ can be odd! Fortunately, I've already got the true proof. Firstly, it's easily to get $$$pg_0$$$ and $$$qx_n$$$, $$$p,q\in\mathbb Z$$$. If $$$s$$$ is even, we can get $$$g$$$ with $$$\frac{s}{2}g_0$$$ and $$$tx_n$$$. If $$$t$$$ is even, we can get $$$g$$$ with $$$-\frac{t}{2}x_n$$$ and $$$-sg_0$$$. If $$$s$$$ and $$$t$$$ are both odd, there must exist $$$s'=s-\frac{x_n}{g}$$$ and $$$t'=t+\frac{g_0}{g}$$$ also satisfy $$$g_0s'-x_nt'=g$$$ by Bézout's Theorem; $$$s'$$$ and $$$t'$$$ mustn't be both odd since $$$\frac{x_n}{g}$$$ and $$$\frac{g_0}{g}$$$ are coprime and they mustn't be both even; the problem to construct $$$g_0s'-x_nt'$$$ is mentioned before.

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

              if $$$\frac{x_n}{g}$$$ and $$$\frac{g_0}{g}$$$ are coprime then how can you say that $$$s'$$$ and $$$t'$$$ will be of different parity. For example, if $$$\frac{x_n}{g} = 3$$$ and $$$\frac{g_0}{g} = 5$$$ then $$$s'$$$ and $$$t'$$$ will be both $$$even$$$ provided $$$s$$$ and $$$t$$$ were both $$$odd$$$. But thanks for your explanation, as at least one of them must be $$$even$$$.

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

        How can we write 0 on board?

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

          Dont think of it as zero. Note {a+nb,a+(n+1)b} can be used to make a+(n+2)b as follows

          $$$ x_{1}+(n+2)g = 2*(x_{1}+(n+1)g) - (x_{1}+ng) $$$
          $$$ \Rightarrow \space we \space have \space all \{ x_{1}+ng \forall n \in Z\} \space using \space \{x_{1}, x_{1}+g \}$$$

          Now, if we have g divides k and

          $$$ \{x_{1},x_{1}+g\} \space generates \space (x_{1}+(k-x_{1})) $$$

          thus all we need to do is check if x1+g can be written. Now this x1 does not really matters as it will disappear in most eqations,you can write down yourself and see .

          In the problem we can write for any x :

          $$$ x_{i} = x_{1}+(x_{i}-x_{1}) \space and \space operation \space on \space x_{1}+(x_{i}-x_{1}) \space and \space x_{1}+(x_{j}-x_{1}) \space will \space give \space : $$$
          $$$ \\(x_{1}+(V)) , V \space is \space some \space constant$$$
          $$$so \space just \space remove \space x_{1} \space and \space find \space if \space (x_{2}-x_{1}),(x_{3}-x_{1}),... \space can \space generate \space g$$$
»
8 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Can someone point out a mistake in this code? It gives WA on 10021st token. How is that even possible if total queries are 10000? https://codeforces.com/contest/1478/submission/105762283

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

    With q = 10000, test cases t = 9 is also there. So total tokens can be upto 9*10000

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

      and I have no way of getting the case right?

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

        Try this test case.
        1
        1 2
        89

        Expected:YES o/p:NO

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

        it's d = 2, a = 21.

        21 itself is a lucky number.

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

          Okay, Got it Thanks. But now I made a solution using unbounded knapsack/ subset sum where I basically used [d, d+10, d+20, ..] as the array to check if a value can be formed using the set. So for d = 2, and set [2,12,22,..] a = 21 cannot be formed right? But my code got accepted. So what is the catch in that? https://codeforces.com/contest/1478/submission/105780118.

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

            21 itself has 2 in it. I don't get what you say.

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

An alternative solution for Problem Div 2 B — 1478B - Nezzar и счастливые числа

For given d, construct a sequence of elements of length s, that looks like d, d + 10, d + 20, ..., d + (s — 1) * 10 such that d + (s — 1) * 10 is strictly less than d * 10.

Observation 1: For a[i] >= d * 10, it's always possible to construct a[i] as sum of lucky numbers.
Observation 2: For a[i] < d * 10, it's feasible to brute-force any possibilities of representing a[i] as sum of lucky numbers.

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

    This is pretty much what I did (a[i] > 100 => yes, else brute-force).

    So many stupid mistakes trying to get a more clever solution....

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

    Can you please explain this? Observation 1: For a[i] >= d * 10, it's always possible to construct a[i] as sum of lucky numbers. UPD: Got it.

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

    mercurist i read your code in problem B , i think use bruteforces of case vec[i] < 10 * d in this way help code run faster instead use dfs

    bool ok = false;
    			for (int j = 1; j < 10; j++)
    			{
    				if (vec[i] - d * j >= 0 && (vec[i] - d * j) % 10 == 0)
    				{
    					printf("YES\n");
    					ok = true;
    					break;
    				}
    			}
    			if (!ok)
    				printf("NO\n");
    

    Sorry my poor English.

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

good but all problem are ad-hoc

plz in next contests add algorithmic problems

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

how to avoid getting stuck on A and B in contests ?

UPD : It's genuine question.Do you people get stuck on those problems often and what are the reasons behind that ?

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

    solve them.

    if you feel like you are not making enough progress on a problem then you can try to solve some other problem and come back to that problem after some time.

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

    Start from C

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

    Yes, I too get stuck in critical observation type problems. Any help on how to improve on problems like that(B of today's contest for example) is appreciated.

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

    in some contests, i solved a,b,c in div 2 before, but how is some questions in contests so made that i couldnt solve B on this contest?

    Sometimes, i get accepted on problems where only 3-4k has solved, on this contest, 8k+ solved B but i couldnt

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

    I used to brick my B quite often a few weeks back. I think you're talking about you are expecting yourself to do those questions quickly but you end up doing it wrong or can't get the idea at all. This is what I did, out of contest, I started practicing two problems from easier ranges(one 800-1200 the other 1300-1500 based on comfort level) and noted the time to solve(try to do it right) whenever I was averaging less than 10 mins in the easier range I increased the rating by 100 for those, same for the harder(1300-1500) ones when the avg. is less than 15. In contest, focus on doing it correctly and don't rush it for the next few contests. You will have a good idea of when you're rushing it as now you know very well how much time you take normally in those problems. It took me 4 to 5 more contests after I started practicing this way to eliminate those bad contests and get to a higher rating range.

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

Really nice problems!Though I miss the final time to submit div2F , which leads to a big loss //(ㄒoㄒ)//

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

Can any one help? why this is giving wrong on PRETEST 3,I checked on my local ide, its giving the right answer. A submission

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

I used bubble sort instead of insertion sorting in Div1C, but it seems that only when I sorted the points by their x-positions could I get accepted. Could you please help me find it out?

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

Div1 C was quite beautiful, however it was the same as this problem

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

Randomized approach for D1C(D2F):

There is three points, $$$A,B$$$ and $$$C$$$ on the plane.
Of course, the three points form a triangle.(this triangle's area can be $$$0$$$)
Then, two of $$$\{A \rightarrow B \rightarrow C\ ,\ A \rightarrow C \rightarrow B\ ,\ B \rightarrow A \rightarrow C\}$$$ are nice beatmaps.

For this reason, the following algorithm will work.

  • $$$p={p[1],p[2],...,p[N]}$$$ is a permutation of $$${1,2,...,N}$$$.
  • Shuffle $$$p$$$.
  • for i = 3 to N
  •  for j = i to N
  •   swap($$$p[i]$$$,$$$p[j]$$$)
  •   if($$$p[i-2] \rightarrow p[i-1] \rightarrow p[i]$$$ is a nice beatmap){break;}

Then, What is the probability of find a solution with this algorithm?
The answer is $$$(2/3) \times (8/9) \times (26/27) \times ...$$$
It seems that this value goes $$$\simeq 0.56$$$ (at least $$$n \le 5000$$$).
So, try this algorithm about $$$\frac{1}{0.56} \simeq 2$$$ times, then we can find a solution.

code : 105753764

If there is a hack case, please tell me.
As a music gamer, I like this problem!

  • »
    »
    8 months ago, # ^ |
    Rev. 2   Vote: I like it +33 Vote: I do not like it
    $$$ \frac{2}{3} \cdot \frac{8}{9} \cdot \dots = \frac{3^1-1}{3^1} \cdot \frac{3^2-1}{3^2} \cdot \dots = \left( 1 - \frac{1}{3^1} \right) \cdot \left( 1 - \frac{1}{3^2} \right) \cdot \dots = \prod\limits_{n=1}^{\infty} \left( 1 - \left( \frac{1}{3} \right)^n \right) = \phi \left( \frac{1}{3} \right) $$$

    Indeed, this product converges at $$$\approx 0.56$$$. You might want to read on q-Pochhammer symbol, it may act as a good probability estimate if you're not sure how many times to run the randomized solution.

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

    Can you elaborate how did you get the answer, i.e. probability?

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

      If there are $$$k$$$ points in a set $$$S$$$, the probability that there aren't any point $$$p$$$ in $$$S$$$ such that $$$X \rightarrow Y \rightarrow p$$$ ($$$X,Y$$$ are some points) is a good beatmap is $$$(1/3)^k$$$ ,thinking about the triangle $$$\Delta XYp$$$.
      Then, the probability is $$$(1-(1/3)^1) \times (1-(1/3)^2) \times ...$$$

      The estimation is very rough, so there maybe some hack case...

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

    Actually all of three authors are osu player! :o

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

      I'm also, but I'm an osu! mania player ><
      (By the way, beatmap(s) or beatsmap(s)...? I always think about this when I want to talk about music games(,or rhythm games, music simulation ...?) in English)

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

        I think it's "beatmap(s)" according to English version osu.

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

I thought that the problems were really nice. Kudos to all the authors!

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

In the problem Nezzar and Board, can anyone prove that if we have $$$[0, x, y]$$$ written on board, then we can construct $$$a*x+b*y$$$? What I was able to prove that we can construct $$$a*x$$$ and $$$b*y$$$ individually.

Thanks

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

    Can you explain how to get $$$a*x$$$ that is any multiple of $$$x$$$ if $$$x$$$ is written on the board?

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

      I can explain with an example, let's assume we have $$$[0, x]$$$ written, we want to construct some $$$a*x$$$. Assume $$$a = 2^z - 2^{j_1} - 2^{j_2} .. - 2^{j_k}$$$. We can write $$$a$$$ in this way using the binary expansion. Now let's take an example and see how to construct it.

      Let's say we want to make $$$10*x$$$, $$$10 = 2^4 - 2^2 - 2^1$$$. We can obviously construct $$$2^b*x$$$ using $$$2*x$$$ repeatedly. Now $$$(2^4 - 2^2 - 2^1)x = 2*(2^3 - 2^1 - 1)x$$$, therefore we only want to construct $$$(2^3 - 2^1 - 1)x$$$ or $$$(2*(2^2 - 1) - 1)x$$$. This means we want to construct $$$(2^2 - 1)x$$$. Which can be constructed using $$$2*x$$$ and $$$x$$$. I hope you got the idea.

      So in $$$a = 2^z - 2^{j_1} - 2^{j_2} .. - 2^{j_k}$$$, divide by $$$2^{j_k}$$$ and construct the remaining part which is $$$2^{z-j_k} - 2^{j_1-j_k} - .. - 2^{j_{k-1} - j_k}$$$ recursively.

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

        Ok got it. One easier way would be to inductively generate all multiples of $$$x$$$. we can generate $$$2*x$$$ by simply using $$$y=0$$$. Than if we want to generate an even multiple of $$$x$$$, we can simply use the $$$a/2$$$ multiple and take $$$y=0$$$. for generating odd, eg $$$5$$$, we can take $$$3*x$$$ and $$$y=x$$$. This way we can generate both odd and even mutliples of x.

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

          Yeah, could have proved using induction also. Can you think on that $$$a*x + b*y$$$ now? If $$$a$$$ or $$$b$$$ is even then it is easy. The problem that I am facing is when both are odd.

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

            Me too, $$$g0*s-xn*t = g$$$

            so just need $$$s$$$ is even -> we done.

            But if $$$s=1.$$$ It's hard

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

            Actually, you don't need to construct the both-odd case:)

            You can obtain $$$a$$$ and $$$b$$$ that satisfies $$$ax + by = \gcd(x, y)$$$ by extgcd. If both $$$a$$$ and $$$b$$$ happen to be odd, you can shift those coefficients, so: $$$(a - y')x + (b + x')y = \gcd(x, y)$$$ where $$$x' = \frac{x}{\gcd(x,y)}$$$ and $$$y' = \frac{y}{\gcd(x,y)}$$$.

            Here $$$x'$$$ and $$$y'$$$ are coprime, so not both are even. Therefore you get $$$(a-y')$$$ and $$$(b+x')$$$ that are not both odd.

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

              One of the best proofs ever .. Atleast for me personally. Just wanted to appreciate it.

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

              Awesome proof!!!!!!

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

        Can you please explain why this is failing (https://codeforces.com/contest/1478/submission/106189636)

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

          The sample is itself failing. The logic is also incorrect.

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

            Can You explain why my logic is wrong, I am taking the GCD as written in the editorial and K should be divisible by GCD of all x's is written in the editorial.

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

              Can you prove why K should be divisible by GCD? Also if it is divisible, how does it guarantee a "YES"? Give a proper mathematical proof.

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

      2x-y is the reflection of y w.r.t x. You can do the following to get all multiple of x:

      • Reflect 0 w.r.t to x and get 2x

      • Reflect x w.r.t to 2x and get 3x

      • Reflect 2x w.r.t 3x and get 4x

      and so on

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

    As others have mentioned, the problem reduces to construct $$$x + y$$$ from the set $$$\{0, x, y\}$$$. Can someone come up with such construction? I've been running a simple program for a few minutes and cannot find it.

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

      I can prove that it is impossible.

      All our initial numbers are of the form $$$(nx+my)$$$. Where at least n or m is even.

      Whenever you apply an operation, on $$$(n_1x+m_1y)$$$ and $$$(n_2x+m_2y)$$$, you get $$$(2n_1-n_2)$$$ and $$$(2m_1-m_2)$$$. It is easily provable by induction that both of the terms can never be odd.

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

        Let me challenge red's proof:)

        You can construct $$$\gcd(x,y)$$$ from $$$\{0, x, y \}$$$ without creating $$$x+y$$$.

        Once you have $$$\gcd(x,y)$$$ in your set together with $$$0$$$, you can construct any multiple of it, including $$$x+y$$$.

        We get contradiction with the proof... What's wrong?

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

          $$$x + y$$$ is not always a multiple of gcd.

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

            $$$Gcd(x,y)$$$ means it divides both $$$x$$$ and $$$y$$$. So why will it not divide $$$x+y$$$?

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

              kekw, yeah, don't know what i meant. The thing is x + y = k * gcd = k1 * x + k2 * y, where one of the coefficients is even.

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

          I was just explaining why his code "has been running for a few minutes and cannot find it"

          So you didn't disprove my proof.

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

For ques B whats wrong with this Maths Approach lets say queried number is N and d is given Now For n to be represented as answer will satisfy this equation i guess N = d*x+ 10*y where x ranges from 1 to 10 because if x>11 than it will club into 10*y example d=8 x=12 now it can be 8*2+10*8;

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

    ???

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

      In which order are you calculating x and y?

      take 27 = 7*3 + 6 (fail) 6%7 != 0

      27 = 10^1 + 17 (fail) 17%10 != 0

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

    d = 8, x = 28

    0 + 28 fail

    8 + 20 fail

    16 + 12 fail

    24 + 4 fail

    take d = 8, x=10 => 8*0+10^1 fail

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

A kind of stupid question, but in the editorial code for D1C:

if (1ll*(x[perm[j]]-x[perm[j-1]])*(x[perm[j-1]]-x[perm[j-2]])+1ll*(y[perm[j]]-y[perm[j-1]])*(y[perm[j-1]]-y[perm[j-2]])>=0)

What exactly is that checking?

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

Can someone point out the bug in this submission for Div. 2's C?
The program prints YES for the below test case, while the correct answer is apparently NO...

2
486710859466 486710859466 665228107582 665228107582

The link to my submission: Submission

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

    How did you overcome the error?

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

      The bug was in the below condition:

      //The Bug:
      if(total - past_sum <= 0 || total % 2 == 1)
      {flag = true; break;}
      //The Correct Condition:
      if(total - past_sum <= 0 || (total - past_sum) % (i + 1)  != 0)
      {flag = true; break;}
      
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Check out my explanation of problem C — solution

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

Thanks for the good contest -_-

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

Congratz, maroonrk!

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

We know there are many weird solutions for Div.1C/Div.2F can get AC when their correctness can't be proved. We had tried our best to construct tests already, but some of them are extremely hard to hack. If you come up with an excellent hack, welcome to share it!

UPD:

For example, 105780521, created by kzyKT and developed by us.

Pick a new base point $$$O'$$$ and sort all points by polar angle, then try to check point sequence $$$[1, \frac n2 + 1, 2, \frac n2 + 2, \dots]$$$ (and those permutations can be derived by shifting) or something similar if they can be valid answers. This pattern will make acute angels appear frequently.

if you can't find answer with the current $$$O'$$$, you can try many other $$$O'$$$. Some specially chosen $$$O'$$$ perform literally excellent, like:

  • $$$( \frac {\sum x} {n}, \frac {\sum y} {n})$$$
  • $$$(inf, inf)$$$
  • $$$(inf, -inf)$$$
  • $$$(-inf, inf)$$$
  • $$$(-inf, -inf)$$$

So you will have a high chance to get a valid answer sequence if you check each of these $$$O'$$$.

We spend a long time hacking this solution, but it seems impossible. :(

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

    I tried to hack the following solution:

    Start sequence from $$$[1, 2]$$$, then for $$$i = 3\dots n$$$ try to insert $$$i$$$ at some place at the sequence so that all angles are $$$<90$$$.

    But it can be proved! Indeed, pair of points $$$p[j], p[j+1]$$$ blocks us from inserting point $$$i$$$ in at most $$$1$$$ position — so at most $$$i-2$$$ positions are blocked. However, we have $$$i$$$ possible positions where to insert! (So we can insert all the points this way)

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

      Yes, it's initial solution when triple_a comes up with this problem.

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

    I construct sequence [1,n,2,n-1...], and it seems can be hacked easily :(

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

Alternative Solution for Div2B without DP 1478B - Nezzar и счастливые числа

If ai >= 10d then it is always achievable. Because it is possible to subtract a number with d on the ten's place and any number on the one's place. It is possible to choose the one's place number so that the subtracted result is divisible by d (meaning it can be obtained by the sum of d's).

If ai < 10d, it is only possible to subtract d from it. So after each subtraction of d, check if ai is divisible by d or ai is divisible by 10 (meaning k*10 + d can be subtracted).

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

    I got most of your solution but can u explain more about checking if val is divisible by 10 ?

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

      For example, if d is 7 and the given number is 54.

      It is only possible to decrease 10*k+7 (k is number from 0 to 9 ) if it is almost 54 from 54.

      54 - 7 = 47 (which not divisible by 7)
      47 - 7 = 40 (which is divisible by 10)
      

      Now this means it is possible to remove 40 by adding it up with previous 7. So subtract 40 and 7 at once (40 + 7 = 47).

      54 - (47) = 7
      7 - 7 = 0
      
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It can be shown that the following is necessary and sufficient:

    Either $$$a_i \ge 10d$$$ or $$$a_i = 10k + dm$$$, $$$m > 0$$$.

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

105777562 For Div2C I solved it by getting back the original array a. Basically the same idea as tutorial except one more observation is that d[2n] = 2n*a[n]

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

    Hello, I tried the same approach as you suggested, but I think that I'm missing something. I looked at the example from the problem statement:

    6
    240 154 210 162 174 154 186 240 174 186 162 210
    

    We have that

    d[2n] = 210, 2n = 12 ---> a[n] = 210 / 12 = 17.5
    

    Can you please help me figure out what? Thank you!

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

I like how D had such a clean solution.

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

Problems are good for both beginners like me and also for coders who are excellent in coding. Thank you, CodeForces!

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

Thank you for this editorial and same for the contest tooo!

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

Why k % gcd(x_1, x_2,.., x_n) == 0 won't work in DIV2D/1A? Can someone please explain.

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

How to prove that it's possible in Div1C to take farthest available point on each step?

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

    You can prove it easily. Let's say you pick $$$B$$$ as the farthest point from $$$A$$$ .

    1) If any point is outside the yellow region, it has to have greater distance from point $$$A$$$ than $$$B$$$, which is a contradiction. So there are no points outside the yellow region.

    2) Any point in the yellow region satisfies the condition.

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

    Even the insertion sort option doesn't seem so obvious to me since swapping two elements can effect both of the adjacent angles. Can you prove that?

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

Otherwise, we could subtract x1 for x1,x2,…,xn and k

why? :(

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

    OK, I guess it's because if we have an initial set {a, b, c} and we want to build k, by subtracting a from everything, nothing changes since every number we can build is also shifted by a. Namely:

    {a, b, c} with target k, e.g. we can build 2b-c.

    is equivalent to

    {a-a, b-a, c-a} with target k-a, e.g. we can build 2(b-a)-(c-a) = (2b-c)-a.

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

DIV 2 (A + B) VIDEO EDITORIAL LINK : https://www.youtube.com/watch?v=amNk203dAGQ

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

Congrats HealthyUG for surviving RED. Happy to see you giving contest even after becoming red,hoping for top 100 rank from you in future.

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

Can someone sketch a proof at Div1C for injection sort?

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

In problem D editorial , how subtracting $$$x_1$$$ from all other $$$x_i$$$ won't effect the answer i.e how to prove that if $$$k$$$ can be formed from $$$x_1,x_2,x_3$$$ then $$$k-x_1$$$ can also be formed from $$$0,x_2-x_1,x_3-x_1$$$?

Also can some one explain how we can write down $$$g$$$ by applying operation recursively ?

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

    For an arbitrary interger $$$d$$$, $$$(2x-y)-d=2(x-d)-(y-d)$$$. That's why we can subtract $$$d$$$ from all the elements (including $$$k$$$).

    From the proof of the editorial, we can get $$$g_0$$$ and $$$x_n$$$. Let we prove one fact that if we get $$$x$$$, we can also get $$$qx$$$ for all the intergers $$$q$$$. In fact, we can use $$$x$$$ and $$$0$$$ to make $$$2*0-x=-x$$$, so that we can add $$$2x$$$ and $$$-2x$$$ any times to any one element. (i.e. we can get $$$2*x-(-z)=z+2x$$$ and $$$2*(-x)-(-z)=z-2x$$$ with $$$z$$$) So the fact has already been proved.

    Then we need to discuss about the parity of $$$s$$$ and $$$t$$$ such that $$$g_0s-x_nt=g$$$. If $$$s$$$ and $$$t$$$ are both even, we can just add $$$\pm 2g_0$$$ and $$$\pm 2x_n$$$ to $$$0$$$ some times. If one of $$$s$$$ and $$$t$$$ is odd, suppose that $$$s$$$ is odd, we can just add $$$\pm 2g_0$$$ and $$$\pm 2x_n$$$ to $$$g_0$$$ some times. If both of them are odd, we can just change $$$s$$$ and $$$t$$$ into $$$s+\frac{x_n}{\gcd(g_0,x_n)}$$$ and $$$t-\frac{g_0}{\gcd(g_0,x_n)}$$$. Because $$$\gcd(\frac{x_n}{\gcd(g_0,x_n)},\frac{g_0}{\gcd(g_0,x_n)})=1$$$, they can't be both even and it has already been changed into the situation we have talked about.

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

      Given $$$g_0$$$ and $$$x_n$$$, then we can get $$$g_0 * s$$$ and $$$x_n * t$$$.

      Now $$$x_1 = x_n * t$$$, $$$x_2 = g_0 * s$$$, we can subtract $$$x_1$$$ from all x. We get $$$0, g_0 * s - x_n * t = g$$$. And by induction, we can get $$$q * g$$$. Now we add $$$x_1$$$ back. Because $$$x_1$$$ is divide by $$$g$$$, suppose $$$x_1 = t * g$$$, so we can get $$$q * g + t * g$$$ for all $$$q$$$, that is equal to $$$q * g$$$.

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

      So you proved that $$$g_0s$$$ and $$$-x_nt$$$ can be made individually using the operations . But how to prove that $$$g_0s - x_nt$$$ i.e $$$g$$$ can be made ?

      My major doubt is how Bezout's Theorem used here ? In the editorial it's mentioned that we can make $$$g_0s$$$ snd $$$-x_nt$$$ but how does that proves that any number divisible by $$$g$$$ can be constructed ?

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

        For example, $$$g_0 s=5g$$$ and $$$x_n t =4g$$$, now we could apply our operation to get $$$4g*2-5g = 3g$$$, and recursively we could finally get $$$g$$$, which could generate all possible numbers divisible by $$$g$$$.

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

          Thanks for the example , it cleared my doubt regarding what actually editorial wants to say .

          I have one more doubt , You have shown for one example that how $$$g$$$ can be constructed when $$$g_0s = 5g$$$ and $$$x_nt = 4g$$$ . How to prove in general that if we can make $$$g_0s$$$ and $$$x_nt$$$ then we can also make $$$g$$$ ?

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

            Note that both $$$g_0s$$$ and $$$x_n t$$$ are divisible by $$$g$$$, and their difference is exactly $$$g$$$, therefore we may assume that $$$g_0s=(m+1)g$$$ and $$$x_n t=mg$$$ for some nonnegative integer $$$m$$$, which falls exactly into the same argument.

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

        Please note that we can construct $$$g_0s+x_nt$$$ for all intergers $$$s$$$ and $$$t$$$ according to the proof above.

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

    Or you can argue geometrically. Operation $$$2x-y$$$ means "mirroring" number $$$y$$$ against the number $$$x$$$ because $$$2x-y = x + (x-y)$$$ and ($$$x-y$$$ is a signed distance between $$$x$$$ and $$$y$$$). Well, and subtracting some arbitrary number $$$d$$$ just means shifting whole set by $$$d$$$ to the left or to the right. It's clear that if you can achieve $$$k$$$ in the original sequence, you can achieve $$$k-d$$$ in the shifted one.

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

Nezzar Can you please give more mathematical proof for DIV1-C, how can we prove this with contradiction like it feels natural but how to prove this first method you suggested.

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

    Consider three points $$$A$$$, $$$B$$$, $$$C$$$.

    You are in $$$A$$$ currently. Assume that the furthest point is $$$B$$$, then $$$C$$$ is between $$$A$$$ and $$$B$$$ so $$$\angle ABC$$$ is acute; if $$$\angle ABC$$$ is not acute, the furthest point from $$$A$$$ should be $$$C$$$ instead of $$$B$$$.

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

I didn't understand the editorial of 1477A — Nezzar and Board Can someone please explain the editorial?

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

    I also struggled to understand it. Here's my detailed understanding:

    (1) Note that if you had zero available and another number $$$a$$$, then you can build every multiple (positive and negative) of $$$a$$$. For example, from $$$(0, a)$$$ you can get $$$-a$$$ and from $$$(-a, a)$$$ you can get $$$3a$$$ and so on.

    (2) Note that shifting all numbers $$$x_i$$$ and $$$k$$$ by the same amount, does not change the answer. If you had numbers $$$x_0$$$, $$$x_1$$$ and $$$x_2$$$ and you wanted to obtain $$$k$$$, you could subtract $$$x_0$$$ from everything and every number obtained from this new process is also shifted by $$$x_0$$$. For example, you would get $$$x_0-x_0=0$$$, $$$x_1-x_0$$$, $$$x_2-x_0$$$ and $$$k-x_0$$$ and if you combined $$$x_1-x_0$$$ and $$$x_2-x_0$$$, you would end up with $$$2(x_1-x_0) - (x_2-x_0) = (2x_1-x_2)-x_0$$$.

    (3) Note that since you can get 0 by shifting the input and you can get the multiples of all the remaining numbers, you can basically get every number of the form $$$u(x_i-x_0) + v(x_j-x_0)$$$, which is another way of saying that you can get every multiple of $$$gcd(x_1-x_0, x_2-x_0, ...)$$$, and nothing else. (See Bézout's identity).

    (4) Finally, using the previous observations, if $$$k-x_0$$$ is a multiple of $$$gcd(x_1-x_0, x_2-x_0, ...)$$$ then the answer is "YES". Otherwise, it is "NO".

    Sample Solution: 105781653

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

      Can you prove point (3)? Given [0, x, y], try to construct x+y.

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

      ok, we can write down $$$g_0, g_0s, x_nt$$$. Explain please, how we can write down $$$g_0s-x_nt$$$? if s is even, i understand, but if not

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

        Let's say we want to get $$$x_{n}t$$$ and we have $$$t = 13$$$. Our operation is $$$2a - b$$$. We can set $$$a = 4x_n, b = x_n$$$, so it becomes $$$8x_n - x_n = 7x_n$$$. And then we set $$$a = 7x_n$$$ which we got before, and $$$b = x_n$$$, and it becomes $$$14x_n - x_n = 13x_n$$$. And of course, we can get any $$$kx$$$ being $$$k = (2^{exp})$$$ if we set $$$a = \frac{k}{2}x$$$ and $$$b = x_1$$$ (remember $$$x_1 = 0$$$ because of the shifting). That is to say, we can get $$$2x$$$ with $$$x$$$ and $$$0$$$, $$$4x$$$ with $$$2x$$$ and $$$0$$$, and so on.

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

          i understand how to get $$$kx$$$ from $$$(0, x)$$$, if we have ((k-2)x, (k-1)x) then $$$2*(k-1)x - (k-2)x = kx$$$. Ok we got $$$g_0s, x_nt$$$, what we should do to get $$$g_0s - x_nt$$$?

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

            Bézout's theorem states that there exists $$$x$$$ and $$$y$$$ so that $$$ax + by = gcd(a,b)$$$. So you can say having $$$g_0s-x_nt$$$ that there exists $$$s$$$ and $$$t$$$ such that it equals $$$gcd(g_0,x_n)$$$. Note that you only need to say if it's possible, not how would you get the number on the board. So once you get $$$g = gcd(g_0,x_n)$$$ (I call it $$$g$$$ to be consistent with the naming in the editorial, as $$$g_0 = gcd(x_2,x_3,x_4,\dots,x_{n-1})$$$) by some amount of operations on the board, it means $$$k$$$ has to be a multiple of $$$g$$$ to be possible to write in the board, and you would do it the same way you got all other gcds before. So that's why at the end we check if $$$k \equiv 0 \pmod{g}$$$.

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

              Note that you only need to say if it's possible, not how would you get the number on the board.

              we need prove it. By induction we got $$$g_0$$$,now we need get $$$g$$$. by Bézout's theorem states there're exist $$$s, t$$$ such that $$$g_0s - x_nt = g$$$, but why we can get $$$g$$$, using operatin $$$2x-y$$$ and some numbers already written down on board like $$$0, x_2, \dots , x_n-1,x_n, g$$$, previosly found gcd's and something else.

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

                The editorial describes the process where you get to $$$g_0$$$ as "recursive". And as I far as I understand and was mentioned in the comments, it means first you had to get $$$x_2s-x_3t = gcd(x_2,x_3)$$$ on the board first, let's call it $$$v_1$$$. Then you got $$$v_2 = v_1s - x_4t = gcd(v_1,x_4)$$$, then $$$v_3 = v_2s - x_5t = gcd(v_2,x_5)$$$ and so on. With that method you got to the last step where in the same way you get to write $$$g$$$ on the board. Therefore, if $$$k$$$ is equal to $$$g$$$ or some multiple of it, it can be written on the board.

                Also, thinking it logically, it makes sense. If all numbers previously written are multiple of some number, multiplying them by two and subtracting another of the numbers in an operation, means you'll never have a way to write some number which is not multiple of it. That's even what's in part described in the first direction of the proof in the editorial.

                About making a really formal proof, I'm not used to making them, so unfortunately I'm unable to come up with one. But based on what's said in the editorial, what was commented by other people and with my logic, seems to work for me. If you still feel unconvinced of the correctness of the solution, you can try to prove it by yourself, try solving as many cases as you want to get to a conclusion. After all, I think it's pretty rare to be proving some solution during a contest, and it always depends more if you are convinced of a solution. Of course I'm also trusting that the authors have made all the possible things they could to be sure of the correctness of the solution. But nevertheless if you find some way it doesn't work, you can always point it out.

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

                  omg, it's common words about why this solution correct. I believe that it's correct, but me need a prove of correctness, only one part of it i don't understand. In induction we need to strictly prove base case and jump from $$$n$$$ to $$$n+1$$$, it does not matter that we assumed until $$$n$$$ we wrote down other gcd's not clear how.

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

              $$$g$$$ should be written down on the board, then we can write down k

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

      Great explanation thank you.

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

      Thanks a lot kirjuri. Now I am able to understand the problem.

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

      This is one of the explanation, I could understand better Thanks, buddy

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

      This is so much better than the editorial's explanation.

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

Nezzar For F, it looks like the coefficient of $$$x^{k-1}$$$ in $$$Q_j$$$ should have $$$1/(k-1)!$$$ instead of $$$1/k!$$$.

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

Can someone explain me Div2D/Div1A? I don't get the intution behind the solution in editorial.

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

Missed the part in DIV2C that integers of the array will be distinct. smh.

Can it be solved if elements of the array were not distinct?

Like, $$$d[] = 16, 16, 16, 18, 20, 22, 22, 26$$$

here, $$$a[] = 1, -1, -1, 2, -2, 3, 3, -3$$$

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

    Please read the statement, array a[] should contain distinct numbers.

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

      Yes. I'm just asking if the elements were not distinct could it be solved.

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

        I think it technically can be solved but the code will be extremely diffcult to write or read.

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

          Hey Nanako, check this. For it to be solved with non distinct elements, the statement should be modified as freq(0) is multiple of 2 and freq(i) should be equal to freq(-i) for each i in the A. Then, it would make sense.

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

          can you please tell me what the array $$$a$$$ will be for the following case?
          $$$d = [4,4,4,4]$$$
          why the elements of $$$d$$$ shouldn't be distinct?
          UPD : I just found out my mistake.sorry!

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

Div2D, what is the meaning of sentence "(Otherwise, we could subtract x1 for x1,x2,…,xn and k)"?

We can somehow transform x1 to 0, if yes, how?

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

    You can imagine that he moves base point $$$O$$$ from $$$x = 0$$$ to $$$x = x_1$$$ in $$$x$$$-axis.

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

        The answer depends on the relative positions of $$$x[]$$$ and $$$k$$$ instead of the absolute positions, so substracting $$$x_1$$$ from all elements at the same time won't change the answer, then we get $$$x_1=0$$$.

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

          can you please explain the last line of editorial of Div2 D ,

          Therefore, we could write down $$$g$$$ applying operation recursively.

          I didn't understood how to do that.

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

            According to the editorial you can write down gcd of two numbers. "recursively" means then you can write down gcd of three numbers (by using the previous gcd and another number), and then gcd of more numbers, until gcd of $$$n$$$ numbers.

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

              Isn't that saying that because we can make $$$g_0$$$ and $$$x_nt$$$ and thus we can some how make $$$g_0s-x_nt = g$$$ by applying the operations ?

              In second part of proof we need to show that any number divisible by $$$g$$$ can be written down . If we show that $$$g$$$ can be written down then it's obvious that anything divisible by $$$g$$$ can written down by taking $$$y=0$$$ .

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

                I think it means the same if you understand how to write down gcd of two numbers. The difference is, my explanation is from gcd of two numbers to gcd of n numbers, editorial is from gcd of n numbers to gcd of two numbers (cuz it's induction).

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

                  Ok , so you mean that because for $$$n=2$$$ our statement holds , thus we can say that $$$g$$$ can be created out of $$$g_0$$$ and $$$x_nt$$$ . And thus we can say that all number divisible by $$$g$$$ can be created .

                  So in last part of proof , we are using the fact for $$$n=2$$$.

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

                  Editorial derive $$$g$$$ from $$$g_0$$$ and $$$x_n$$$, and you can also imagine, before that, you derive $$$g_0$$$ from $$${g_0}_0=\gcd(x_2,\dots,x_{n-2})$$$ and $$$x_{n-1}$$$. Keep similar operation then you will realize the whole process is all correct.

                  I can't really get what makes you confused. Maybe learning "What is Induction" would help you.

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

    "substract x1 from x1,x2,...,xn and k"

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

      Lets say we have three numbers a, b, c. How can we construct 0 from them, by using that operation 2x-y?

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

        You convert $$$(x_1, x_2, x_3, k)$$$ into $$$(0, x_2 - x_1, x_3 - x_1, k - x_1)$$$. They are equivalent because $$$2(a - x_1) - (b - x_1) = (2a - b) - x_1$$$

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

    You can see that any solution in the transformed set is a solution in the original set because $$$2x - y$$$ is the reflection of $$$y$$$ over $$$x$$$, and these reflections are invariant to shifts such as in the transformed set.

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

      omg, I thank you all for trying to explain ;) But such sentence with another 3 or 5 new terms is not helpful.

      I understood that for some reason we can shift all numbers by any amount, and for another reason we do shift by x1, so we transform that element to 0.

      Then, for some reason, we can directly use the gcd() of the remaining numbers to check if k is a multiple of it, which determines ans.

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

        Try picking a couple $$$x$$$ and $$$y$$$ pairs and draw them in the number line, along with $$$2x−y$$$. Try to find a pattern there, it might be useful to get an intuition to why we can find a solution using the numbers with a fixed offset.

        The reason we want one element to be $$$0$$$ is because then we can use it allows us to construct some more predictable and useful numbers. For example if we do the operation $$$2x−y$$$ with $$$x=0$$$, the result is $$$−y$$$, and if we do it with $$$y=0$$$ the result is $$$2x$$$, see some discussions above to more details on why this will help solve the problem. Also we can shift by any other number, not necessarily $$$x_1$$$.

        The argument for the gcd I still have not figured it out. This editorial is pretty obscure (not surprising, sadly).

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

        Operation we apply : $$$2x - y$$$ . Suppose we subtract $$$x_1$$$ from $$$x$$$ and $$$y$$$. Then $$$2*(x-x_1) - (y-x_1) = 2*x-y-x_1$$$ . So you can see that final answer is subtracted by $$$x_1$$$.

        Thus converting to $$$k$$$ from $$$x$$$ and $$$y$$$ is same as converting to $$$k-x_1$$$ from $$$x-x_1$$$ and $$$y-y_1$$$.

        I showed for only one operation but it's not hard to see for multiple operations.

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

1477B - Nezzar и бинарная строка can be solved without a segment tree. The idea is to keep subarrays with equal digits in a set. The complexity of the operations for each move is $$$O(\log(n))$$$ amortized.

AC submission: 105757658

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

105785851 Why does this brute force sol work for div2 B? Shouldn't it give a TLE in the worst case?

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

    Many numbers contain $$$d$$$ so it won't spend too much time finding a valid answer. I think this sol is also a correct sol.

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

problem D editorial proves the solution but doesn't gives any intuition behind coming up with the solution . Can some one tell their lane of thought which brought them to the solution ?

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

    I can offer my thinking process in this problem.

    Noticed that $$$2x-y=x+(x-y)$$$, so actually for a $$$x$$$ we can move it to $$$x + k \cdot dis(x, y)$$$ for any $$$k$$$ and available $$$y$$$. Then according to Bézout's Theorem, I found that $$$x$$$ can be moved to any $$$x + k \cdot \gcd(dis(x, others))$$$.

    A fun observation is, in $$$2x-y$$$, coefficients are $$$2,-1$$$ and the sum of them is $$$1$$$. Actually, I think it seems impossiable to solve if we change it to $$$3x-y$$$, but $$$3x-2y$$$ or $$$3x-y-z$$$ or something seems much more solvable. I can't explain it well because my English suck, sorry.

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

      Hey Nanako

      I found that X can be moved to any X+K*gcd(dis(X,others)).

      how you found that!?

      What if the k*gcd is smaller than the diffs we can add !?
      Example:
      K=52
      arr=[7, 27, 42] so the gcd(diffs)=gcd(20, 15)=5
      42 + 2*5 = 52
      to get 52 we need to add 2*5 to 42, but we can't do that using the real diffs (20, 15) I know we can get it using some (subtractions , additions) of these diffs but I'm not sure how I can think about it intuitively.

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

        Sorry for replying lately. I guess it will become more and more intuitive after you solve more and more problems about Bézout's Theorem and ex-gcd (Chinese nickname of Extended Euclidean algorithm? lol) and other number theories. :)

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

    Given x and y, we can get $$$x + t * (y - x)$$$ for all t. So this is an arithmetic sequence. We draw it on an axis.

    Now given another number z. We find a closest point on the axis and draw the new arithmetic sequence produced by z and the closest point. If the distance of z and the closest point divides $$$y - x$$$, then all points is just one arithmetic sequence which is $$$z + t * distance(z, closest point)$$$. Otherwise, we can find another two more close points and produce more points. You can see that only when the distance of two closest points divides both $$$y - x$$$ and $$$z - x$$$ and $$$z - y$$$, the process will stop. So $$$z + t * gcd(y - x, z - y)$$$ can be produced.

    You can draw it on a paper and get the intuition.

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

1477A — Nezzar and Board

Explain me how we can write down $$$g_0s-x_nt$$$ which is equal $$$g$$$?

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

video editorial for problem D, if theres anyone whos stuck! https://www.youtube.com/watch?v=yYxQ9_EL69Q

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

    i still don't understand, how from (0, a, b) get $$$a * s - b * t = gcd(a, b)$$$ using $$$2x-y$$$ operation

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

      If s is even, then we can get a * s/2 and b * t first, then $$$2 * (a * s/2) - b * t$$$ is $$$gcd(a,b)$$$. If s is odd, then we can get $$$2 * (a * (s+1)/2) - b * t$$$ is $$$a + gcd(a, b)$$$. Given a and $$$a + gcd(a, b)$$$, by induction, we can get $$$gcd(a, b)$$$.

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

        thaks, i undertood) Really is it so obvious, that it's not required to point in editorial? Only how to get $$$gcd(a, b)$$$ from $$$a$$$ and $$$a+gcd(a, b)$$$ took me 5 minutes. We can get $$$a - gcd(a,b)$$$, than $$$a - 2*gcd(a,b)$$$ and so on until we get $$$gcd(a, b)$$$.

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

for 1478B, here is my solution https://codeforces.com/contest/1478/submission/105779176 in a bit different style than author ;) , although I fucked up during the contst!:(

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

For problem B I assume that $$$x$$$ can be represented as $$$ x = y + w.d $$$. Then, $$$ y = x - w.d $$$ and just check that $$$y$$$ has at least one digit equal to $$$d$$$. By brute force I concluded that $$$w$$$ is at most $$$9$$$ because for $$$x >= 10.d $$$ the answer is always YES.

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

The system test of problem C is weak! Some people use double and sqrt to calculate distance, it can be hacked, like this, but it passed the system test.

I noticed this and resubmitted my code, after the contest, I know that the original code could pass, if I didn't resubmit, I'll be International Master! ):

update: This seems to work only for GNU C++17 (64).

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

Could anyone help me about this https://codeforces.com/blog/entry/87299 ? Thanks!

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

In problem D of div2, why always subtracting x1 from all other numbers works? Means the cases can't be there such that we need to subtract x2 from all the numbers and take gcd after that?

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

    k is a linear combination of all x. And you can see that sum of coefficients is always 1. So subtracting x1 from all x results in subtracting x1 from k.

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

For anyone not knowing what WLOG means in editorial for Div.2 C,
WLOG = Without Loss Of Generality.

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

Very nice problems!

I like div.1C very much.

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

For Div2 B how can N=21 and D=2 gives answer yes?

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

    If you are talking about taking some ai = 21 and d = 2, then 21 itself is a lucky number as it contains d = 2 in its representation already and doesn't need to be expressed as sum of other lucky numbers, So, answer is YES.

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

    21 itself is lucky number.

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

Can someone tell the mistake in the following code of mine for Div2B: 105802694 For each integer i from 1 to 9 I stored the smallest integer 1<=j<=10, that give the unit digit (i*j)%10 when multiplied with as a[i][(i*j)%10] = j So if the number in query (say c) had a unit digit l that can be found in a multiple of d, I check if c is greater than or equal to the minimum multiple of d that gives that unit place. If yes, then I output YES as I think all such numbers can be represented using lucky numbers. Else, I output NO as d in unit places has minimum effect, so if we have even one d in tens place, then it becomes greater than c. Now if the units place l in c cannot be found in a multiple of d, then I check if c/10 is greater or equal to d. If yes then I print YES else no, as d cannot even come in tens place then. Can I get a testcase where this fails?

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

    Your mistake is that you forgot to put a continue after cout << NO << endl in the first if block of your code :)

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

Problem B :

say d = 7, so 70->79 already lucky, we can generate 80->89 as follows

72 + 17 = 89
71 + 17 = 88
70 + 17 = 87
79 + 7 = 86
78 + 7 = 85
77 + 7 = 84
76 + 7 = 83
75 + 7 = 82
74 + 7 = 81
73 + 7 = 80

similarly, we can generate 90-99 from 80-89 and so on ......

so, any number >= 10*d is lucky

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

Nezzar please explain DIV2C

Why in you solution following code gives $$$a_1$$$ in $$$b[n-1]$$$?

for (int i=1;i<n;++i) {
    b[n-1]-=2*i*d[i];
}

And why are you checking this condition b[n-1]%(2*n) in the end?

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

    Bazalt If you are clear with this part, can you please explain the divisibility check ( (b[i-1]-b[i])%(2*(n-i) )and the d[i] array?

    for (int i=1;i<n;++i){
                if (b[i-1]==b[i]||(b[i-1]-b[i])%(2*(n-i))){
                    cout<<"NO\n";
                    goto cont;
                }
                d[i]=(b[i-1]-b[i])/2/(n-i);
            }
    
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      As Nezzar says, $$$d_{2i} - d_{2i - 2} = (2n - 2i)(a_i - a_{i - 1})$$$. He did not prove that, but he give example for i = n; You can easily find it, probably with induction.

      And in this code, which you show he just calculating array of $$$a_i - a_{i - 1}$$$ for all possible i, he named it d[i] array. Before that he just using divisible check for 2n — 2i.

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

can any tell me why i am getting WA on 2nd TC

my solution for prbolem B (Div 2)

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

Nanako Can you please explain the relation in the editorial of Div2 C ? This one.. "More importantly, we have the following relation:".

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

    Main observation is, when there are $$$n - x$$$ elements smaller than the current position and $$$n + x$$$ elements bigger than the current position, if you move left for 1 unit length, $$$\sum |curpos - a_i|$$$ will increase $$$2x$$$.

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

I found this contest really nice (especially div1 D). Thanks for the contest :)

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

Chinese round! Unfortunately I still can't take part in due to the time (.

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

On div2 D,

if((arr[0]%gcd) == (k%gcd)) printf("YES\n"); ... => WA

if((k-arr[0])%gcd == 0) printf("YES\n"); ... => AC

I really wonder why this thing happens.

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

I approached Div2 B as follows: (let input be n)

  1. Consider the largest multiple of d <= n (call it x)
  2. We need to add exactly (n — x) to x.
  3. The goal is to subtract some multiple of d from x and add some 'lucky' number, such that (lucky_number — multiple_removed) = (n — x)

Brut force on this got accepted. Here's my solution.

I would like to know if there is any hack possible on my approach.

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

div2C symmetric array

I tried another approach:

Assume that the "d" array (the sum array) and the "a" array (initial array) are sorted. I redefined the "a" array so that it would only contains positive numbers.

Since the two arrays are sorted $$$a[n - 1]$$$ and $$$d[n - 1]$$$ would become the largest element of respective array. I observed that if we choose any index i (0 <= i < n), then the sum $$$|a[n - 1] - a[i]| + |a[n - 1] - (-a[i])|$$$ would become $$$|a[n - 1] - a[i]| + |a[n - 1] + a[i]| = a[n - 1] - a[i] + a[n - 1] + a[i] = 2a[n - 1]$$$ (since a[n — 1] is the largest element). This applies to every other index 0 <= j < n — 1.

Then a[n — 1], or the largest element of the "a" array (initial array) can be calculated using this formula: $$$d[n - 1] = a[n - 1] * 2(n - 1). $$$ By expanding more, I could also prove that: $$$d[n - 2] = 2a[n - 1] + 2(n - 2) * a[n - 2].$$$

Hence I could restore the initial array with following formula: $$$d[j] = \sum\limits_{i=j+1}^{n - 1}{2a[i]} + 2j * a[j]$$$, with j being the index in the sorted array. Furthermore, since all d[j] % 2 == 0 from above formula, I could throw away any cases that had any d[i] that is odd.

The problem is I can't make sure if the array constructed was right or wrong. So I tried calculating everything again from the constructed array, and also noticed if any element in that array was 0 it was wrong. Can anybody pls check it out lol

105799882

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

    I used the same approach and got AC. To check if $$$a_i$$$ is correct, I checked that it was positive and it hadn't been found before.

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

In Div2 C how are we checking that whether a[0] can be made form d[0]. The a and d I am refering to are problem statement a and d.

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

Div1 D is awesome . Thank you!

It took me about 4 hour to come up with the solution . A very nice problem !

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

Nezzar and lucky number can be done in O(1) Solution: Observation1: x>= 10*d , it is always possible. Observation2: for x<10*d, let h be a multiple of d, If((h%10==x%10) && (h>=x)) => Yes Else => No

Solution: 1) make array of size 10 nad initialise with -1. 2)For i (0 to 9) K=d*i If arr[k%10]==-1 , arr[k%10]=k 3) if (arr[x%10]!= -1 && arr[x%10]>=x) => Yes Else if (x>= 10*d) => Yes Else => no

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

In Div1.A why can we assume $$$x_1=0$$$? I can't understand.

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

For Div1B (Nezzar and Binary String), could someone explain how the 3rd sample input test is possible? I've been thinking a while but I'm quite confused.

10 6
1111111111
0110001110
1 10
5 9
7 10
1 7
3 5
6 10

If we follow the editorial, we should work backwards starting at 0110001110, we need 6-10 to be the same before the last night's inspection so it becomes 0110011111. Then we need 3-5 to be the same so it becomes 0100011111. Then we need 1-7 to be the same so it becomes 0000000111. Then we need 5-9 to be the same and it becomes 0000000001. Finally we need 1-10 to be the same so it becomes 0000000000, but this is not 1111111111, so it doesn't seem to be possible?

Edit: Thanks Nezzar, I wrote the math for this out like 5 times on notebook paper and kept getting the same result, I have no idea how I missed that query every time..

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

I'm confused by some of the implementation in Div1 D. I think the dfs function creates the spanning tree of the complement graph, is this right? The loop with while(d.size()) seems to do the decomposition into stars, but if I'm not mistaken it doesn't use the same method described in the editorial. What I get from this is that you choose an unassigned node from d in idx, then choose one of it's neighbours f to be the center of your star graph? Why this particular ordering of vertices in d?

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

    Sorry if it causes any inconvenience. Codes were written by me while tutorial for d1D was written by Nezzar.

    Approach to decomposite spanning trees into stars in the code was to choose an arbitrary leaf in the tree, find its neighbor vertice $$$u$$$, and choose all neighbor vertices of $$$u$$$ with degree $$$1$$$ to form a star. It can be shown that the remaining graph after deletion of this chosen star is still a tree with more than $$$1$$$ vertices or empty.(Therefore, we could decompose tree into stars applying this method recursively.)

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

      That makes sense, and is very simple. Thanks!

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

For div1F, the $$$m$$$-th coefficient of $$$Q_j$$$ should be $$$\frac{1}{m!}(1 - q_{m,j})\left(\frac{L_j}{L}\right)^m$$$

and the OGF of $$$k! \sum_{n \geq 0} \binom{n + k}{k}C^nx^{n+k} = k! \frac{x^k}{(1-Cx)^{k+1}}$$$

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

Can someone clearly explain what happened in Nezzar and board?

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

In Div 2 C editorial,

"And observe that |ai−an|+|ai+an|=2an is a constant independent of index 1≤i≤n."

Why is this the case?

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

A much better solution for div2 B than DP is that if the number is $$$ \geq 10*d$$$ then it is always possible, otherwise we can observe that the only numbers less than $$$10*d$$$ that contain $$$d$$$ are, $$$10 + d, 20 + d, 30 + d, \dots$$$ Hence, if a number is feasible then it can be represented as: $$$10*x + d*y$$$ where $$$x$$$ and $$$y$$$ are variables.

I'm livid I didn't come up with this during the contest lol.

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

In Problem C : Can anyone explain why the biggest element in array d is always 2*n*(biggest element in d) supposing arrays d and a are sorted then a[n]*2*n=d[n] why?

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

    Each element has a positive and negative value. Supposing the positive value is $$$ x $$$, and the absolute difference to $$$(y, -y)$$$ would be $$$| x - y | + | x + y | $$$. Similarly, for $$$ -x $$$, that would be $$$ |-x - y | + |-x + y |$$$, which is also $$$|x - y| + |x + y|$$$.

    For $$$|x - y| + |x + y|$$$, we have two different cases. For $$$x > y$$$, $$$|x - y| + |x + y|$$$ would be $$$ 2 * x $$$. For $$$x > y$$$, $$$|x - y| + |x + y|$$$ would be $$$ 2 * y $$$. Now we know that $$$|x - y| + |x + y|$$$ = $$$2 * max(x, y)$$$.

    For each $$$ d[i] $$$, it is the sum of each absolute differences from $$$a[i]$$$ to all integers. Combined with the previous finding, we got

    $$$ d[i] = \sum_{j=1}^{2n} max(abs(a[i]), abs(a[j])) $$$

    Supposing the max element is $$$a[n]$$$. As $$$a[n]$$$ is greater than other elements, Then, we have

    $$$ d[n] = \sum_{j=1}^{2n} a[n] $$$

    Therefore, you got $$$d[n] = a[n] * 2 * n $$$.

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

Can anyone please elaborately explain me B ( Lucky number one ) I'm struggling to understand the solution by Dp, I am a newbie so please be considerate, CF is extremely harsh and often hostile to beginners.

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

    Try thinking about it like this: Suppose the number you are trying to check is $$$x$$$, If $$$x$$$ is achievable then it can be represented as $$$x = a + b$$$, where $$$a$$$ is a number with $$$d$$$ as one of it's digits and $$$b$$$ is a number that is also achievable.

    The only possible values for $$$a$$$ are: $$$d, 10+d, 20+d, 30+d, \dots$$$

    The line: dp[10*i+d+j]|=dp[j]; is checking just that! $$$10*i + d$$$ represents all possible values of $$$a$$$ and $$$j$$$ represents any number that is achievable. Hence, if $$$j$$$ is possible then $$$10*i + d + j$$$ is also achievable.

    Hope it helps!

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

      Why "The only possible values for a are: d,10+d,20+d,30+d,…"?

      If d = 4, for example, the lucky number 40 can't be represented in that way.

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

        I was only explaining the DP part. Otherwise for any number $$$x \geq 10*d$$$ is always possible no?

        Thanks for pointing that out though.. could've been confusing for others.

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

could someone explain how for div1 B (1477B), how the second sample test case is impossible?

2 1
00
01
1 2

on the 1st day, the string that is inspected is "00" on the 1st night, you can change 1 character in the inspected string, so can't you change "00" to "01" and finish the test case successfully?

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

Wouldn't X(i) — X(i-1) always = 1? I'm confused...

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

Div2D was a very nice task, but i miss a more detailed editorial's explanation.

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

For 1478D - Nezzar и доска, suppose we have the numbers 0, a, b, c. Then how can we generate 3a — b + 5c? Since we are using Bezout's Identity, then ax + by + cz = d must exist $$${\forall}$$$ x,y,z $$${\epsilon}$$$ $$$\mathbb{Z}$$$

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

I used a greedy approach for problem B and it accepted! Thanks for such a nice clean code for problem B.

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

Problem B got me :((

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

In the Nezzar and Board problem, I find it difficult to understand why "If g = GCD(x1,x2,x3,....,xn) divides k, then YES, else NO" doesn't work, but the given logic in the Editorial does. Also, I am not able to comprehend the proof given. Can someone explain? Thanks in advance!

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

In the solution of 1478B, for the nested loop we can do j = j+d instead of ++j right?