Please read the new rule regarding the restriction on the use of AI tools. ×

nishkarsh's blog

By nishkarsh, history, 11 days ago, In English

A. Find Min Operations

By nishkarsh

Hint 1
Hint 2
Solution
Code

B. Brightness Begins

By nishkarsh

Hint 1
Hint 2
Solution
Code 1
Code 2

C. Bitwise Balancing

By P.V.Sekhar

Hint 1
Hint 2
Solution
Code

D. Connect the Dots

By P.V.Sekhar

Hint 1
Hint 2
Solution
Code

E. Expected Power

By nishkarsh

Hint 1
Hint 2
Solution
Code

F. Count Leaves

By nishkarsh

Hint 1
Solution
Code
  • Vote: I like it
  • -346
  • Vote: I do not like it

»
11 days ago, # |
  Vote: I like it +325 Vote: I do not like it

whats the point of allowing $$$O(n \cdot 1024)$$$ solutions in E

  • »
    »
    11 days ago, # ^ |
      Vote: I like it -184 Vote: I do not like it

    well, we reduced the bound on A to make sure nlog^2A passes.

    We didn't knew that these solutions existed.

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

      know*

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

      I think $$$a_i < 2^{14}$$$ or something would've been the optimal choice if i am not mistaken $$$O(n \log^2 A)$$$ should pass as long as there is no bad constant factor and the more naive solution wouldn't have passed but i am sure it was hard to predict that such solutions would pop up + thanks for the amazing contest.

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

        It's not hard to expect that the dp 1024n is too easy and obvious to anyone who has solved dp+ev before

        • »
          »
          »
          »
          »
          11 days ago, # ^ |
            Vote: I like it -23 Vote: I do not like it

          Yes it is straight forward but $$$n$$$ is still upto $$$2 \cdot 10^5$$$ so passing shouldn't seem smooth, some people even got TLE.

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

        What is amazing about this contest?

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

      then you just killed the problem

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

    my O(n * 1024) solution passed (4000ms), so I optimized to O(min(n, 1024) * 1024) and it passed 2500ms.

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

      This also didn't seem intended but yeah this solution also exists and it runs in $$$O(\text{max } a_i^2)$$$.

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

      can you please explain your optimized solution for problem E?

      • »
        »
        »
        »
        11 days ago, # ^ |
        Rev. 6   Vote: I like it +10 Vote: I do not like it

        Sure. Here’s how I came up with the optimization:

        1. Notice that if n > 2^10, we have duplicates.
        2. Q: What properties does the XOR operation have that can help with duplicates? A: If we have an even number of duplicates, XOR = 0. If we have an odd number of duplicates, XOR = the number.
        3. We need to precompute two values for each unique number (less than 2^10): pdp[i][0] — the probability of getting value i an even number of times. pdp[i][1] — the probability of getting it an odd number of times.
          Dp base for each number = {1, 0} (100% chance of getting zero times).
        4. How do we calculate these values? Iterate over all values, and for value i (with prob pi), we have two transitions: pdp[i] = { pdp[i][0] * (1-pi) + pdp[i][1] * pi, pdp[i][0] * pi + pdp[i][1] * (1-pi) }. I hope these transitions are clear to understand.
        5. Then, we can reuse the previous solution O(n * 1024), but instead of iterating over all a[i], we will iterate only over unique a[i]. Instead of p[i], use previously calculated probability dp prob_dp[a[i]] for calculating the new dp. Two transitions: if we take an even number of a[i] or an odd number of a[i].

        My solution (rust): https://mirror.codeforces.com/contest/2020/submission/283652607 In my case cnt array is pdp precalculations.

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      it is still O(n*1024) ?

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

    I came up with that solution at my first look at E after solving C, but $$$O(n⋅1024)$$$ would definitely TLE, and I couldn't improve my approach. It kinda makes me feel sad to know that such were ACed now :)

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

      283614074 Brute force solution runs 0.9s. Much less than Time Limit 4s, and quite close to official solution which runs 0.7s. When I come to the problem, I get the idea same as the tutorial. But later I see $$$a_i<1024$$$, so I decide to submit $$$O(1024 \min{\{n, 1024\}})$$$ solution which saves lines of codes.

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

        say n = 1 across test cases , then u can have 2e5 test cases in each loop of 1024 makes the complexity O(1024*t) ryght ?

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

          No. The statement says $$$t \le 10^4$$$, and the worst case is $$$2 \times 10^5 \times 1024$$$, nothing to do with $$$t$$$.

          • »
            »
            »
            »
            »
            »
            10 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            crrct , my point is that O(1024min{n,1024}) solution is not the case ,

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

    I replaced 4 modulo operation with 1 in my solution. And it got passed

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

    yeah, my O(n*1024) passed in 765ms

»
11 days ago, # |
  Vote: I like it +6 Vote: I do not like it

Can anyone explain how did we get the direct formula in B??

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

    Every number has an even number of factors, except square numbers.

    We can prove the first fact by finding a factor a of number n. Then, if n is not a square n/a is another factor of n.

    If n is a square, then we double count sqrt(n), as we count n/sqrt(n) and sqrt(n) which are the same value. This leads to an odd number of factors(every other factor + 1).

    Using this, if a switch is flipped an even number of times, it returns back to 1. If it flipped an odd number of times, it returns to 0.

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

      what is the explanation of n-sqrt(n)>=k?

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

        sqrt(n) gives how many square numbers are there for n, since squares cant be On we need to subtract them to get total lights on and the RHS is since we need to check if ON is atleast k to get the binary search going.

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

      Check the solution discution on YT.

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

      This does not answer the question which was about how to get the direct formula: $$$n=⌊k+\sqrt{k}+0.5⌋$$$

  • »
    »
    11 days ago, # ^ |
    Rev. 2   Vote: I like it -12 Vote: I do not like it

    I have created a video solution for Problem B and Problem A on my youtube channel, you can checkout, it's a simple and intuitive solution

    Video solution for Problem C

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    first, few keypoints to keep in mind are: 1) sqrt(1)->1,sqrt(4)->2,sqrt(9)->3,sqrt(6)->2.44.....square root of numbers tells you that how many perfect square where there before that number. for example sqrt(9)=3, so there are total 3 perfect square <=9 which are(1,2,3).similarly sqrt(6)=2.44..round of to 2 perfet squares before 6 which are (1,2).

    2)now , according to question we need k ones, so why not lets take n=k(for k ones), now we can say there are total sqrt(k) perfect squares. which means if we take n=k there will be total sqrt(k) which will be zero and rest will be 1. hence to make total number of ones =k we have to add sqrt(k) to n so that we get k ones.

    3)example- given k=6. now sqrt(k)=round(2.44)=2. that means total perfect squares before 6 will be 2. that means if we take n=6 then we will get two zeroes and 4 ones i.e 011011 . but according to question we need k=6 ones, hence to add extra 2 ones we do n= k+sqrt(k) i.e n=8 which will give total numbers of one=6 i.e 01101111.

    4) note the 0.5 factor is there to compensate for next perfect square we can get as a zero. in case of 8. therefor n=k+sqrt(k)+0.5.

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

      What a beautiful explanation. Now I understood the whole solution.

»
11 days ago, # |
  Vote: I like it -76 Vote: I do not like it

This was a good round, unless I FST ofc, then it was a horrible round. I think that there should be more problems like this — problems that don't require so much IQ, but $$$do$$$ require coding. These problems are what might be called chill problems.

»
11 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Now after seeing the solution of B problem.... I just want to cry ):

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I was able to figure out that number of ON bulbs after n operations is related to sqrt(n) but was going in opposite track. Here only perfect squares are off and other are ON.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I understood the binary search solution for problem B. But, I am not able to figure out how direct formula $$$n = \lfloor k + \sqrt{k} +0.5 \rfloor$$$ came. Can anyone please explain it?

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

    dont think abt that farmula number of number of perfect squares<=k and add to k(ie (int)sqrt(k)) now we can only cross atmost one more square in b/w [k,k+(int)sqrt(k)] which is ((int)sqrt(k)+1)^2 check for that and add 1 the farmula given directly checks it mathematically

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

      I did a similar approach but got wrong answer. Mind explaining why? This

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

        i think it has problem with sqrt funcuntion like some times it will give root 4=1.999 so it will become 1 so it is good to check if (r+1)(r+1)=k r++;

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

      I am trying to submit binary search solution but I am receiving WA verdict. Even though it is giving correct answer for that test case in my machine. Can you please check what is the problem? https://mirror.codeforces.com/contest/2020/submission/283696903

      Thanks

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

        i think its the same problem with you the sqrt funcuntion gives error at intigers some times

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

          Oh I see, these type of arithmetic errors are really difficult to catch unless you know them beforehand. Thanks a lot Veda_2005

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

    Suppose $$$\lfloor \sqrt n \rfloor = m$$$, $$$m^2 < n < (m+1)^2$$$ (note that n wouldn't be a square, as the square lightbulb itself is closed)

    So, $$$m^2-m < k < m^2+m+1, m-0.5 < \sqrt k < m+0.5$$$ (inequality is true as k is an integer)

    $$$\lfloor \sqrt k +0.5 \rfloor = m = \lfloor \sqrt n \rfloor$$$, $$$ n = k + \lfloor \sqrt k +0.5 \rfloor$$$

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

      Ok, no I understood this formula completely. But, I am not able to understand only this fact that if $$$m^2 - m < k < m^2 + m + 1$$$, then how inequality $$$m - 0.5 < \sqrt{k} < m + 0.5$$$ is true when $$$k$$$ is an integer.

      And, I suppose that there is a typo. It should be $$$\lfloor \sqrt{k} + 0.5 \rfloor = m = \lfloor \sqrt{n} \rfloor$$$, instead of $$$\lfloor \sqrt{k} + 0.5 \rfloor = m = \lfloor n \rfloor$$$

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

        Yes the last one is a typo, fixed. $$$m^2-m < (m^2-m+1/4) = (m-0.5)^2 < k < (m+0.5)^2 = m^2+m+1/4 < m^2+m+1$$$

        As you can see, 1/4 is added for lower bound, 3/4 is removed for upper bound, so the inequality only works because k is a positive integer.

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

          Ok, now I understood this formula. I as just getting confused why only 0.5 constant is used and not any other number. Thanks a lot TanJWcode

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

            Because the upper bound and lower bound is $$$m^2 \pm m$$$, completing the square gives us the constant. $$$(m+a)^2 = m^2+2am+a^2$$$, here $$$2a= \pm 1$$$

            If you're still confused, note that this is a derivation. I'm intentionally deriving $$$n=k+ \lfloor \sqrt k +0.5 \rfloor$$$ from $$$n-\lfloor \sqrt n \rfloor = k$$$

            Some parts of the proof is forced, and there are more natural ways of finding the formula

            Intuition:

            Suppose $$$l^2 \leq k < (l+1)^2$$$, we need at least $$$l$$$ more lights to compensate for the $$$l$$$ squares before $$$k$$$.

            As $$$k+l < l^2+3l+1 < l^2+4l+4 = (l+2)^2$$$, there will be at most 1 square between $$$k$$$ and $$$k+l$$$, and we need to add 1 more light if there is one.

            So if $$$k+l \geq (l+1)^2, n=k+l+1$$$, else $$$n=k+l$$$ . This already is the solution, 0.5 is added to make the solution into a pretty formula

            If $$$k+l \geq (l+1)^2 , k \geq l^2+l+1 > l^2+l+0.25$$$, then $$$\sqrt k > l+0.5$$$

            This means if $$$\sqrt k > l+0.5, n=k+l+1$$$, otherwise $$$n=k+l$$$. The formula follows.

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

    first, few keypoints to keep in mind are: 1) sqrt(1)->1,sqrt(4)->2,sqrt(9)->3,sqrt(6)->2.44.....square root of numbers tells you that how many perfect square where there before that number. for example sqrt(9)=3, so there are total 3 perfect square <=9 which are(1,2,3).similarly sqrt(6)=2.44..round of to 2 perfet squares before 6 which are (1,2).

    2)now , according to question we need k ones, so why not lets take n=k(for k ones), now we can say there are total sqrt(k) perfect squares. which means if we take n=k there will be total sqrt(k) which will be zero and rest will be 1. hence to make total number of ones =k we have to add sqrt(k) to n so that we get k ones.

    3)example- given k=6. now sqrt(k)=round(2.44)=2. that means total perfect squares before 6 will be 2. that means if we take n=6 then we will get two zeroes and 4 ones i.e 011011 . but according to question we need k=6 ones, hence to add extra 2 ones we do n= k+sqrt(k) i.e n=8 which will give total numbers of one=6 i.e 01101111.

    4) note the 0.5 factor is there to compensate for next perfect square we can get as a zero. in case of 8. therefor n=k+sqrt(k)+0.5.

»
11 days ago, # |
  Vote: I like it +18 Vote: I do not like it

In problem B, how do we derive the formula $$$( n = \left\lfloor k + \sqrt{k} + 0.5 \right\rfloor )$$$ from the equation $$$( n - \left\lfloor \sqrt{n} \right\rfloor = k )$$$?

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

    Derivation:

    Suppose $$$\lfloor \sqrt n \rfloor = m$$$, $$$m^2 < n < (m+1)^2$$$ (note that n wouldn't be a square, as the square lightbulb itself is closed)

    So, $$$m^2-m < k < m^2+m+1, m-0.5 < \sqrt k < m+0.5$$$ (inequality is true as k is an integer)

    $$$\lfloor \sqrt k +0.5 \rfloor = m = \lfloor \sqrt n \rfloor$$$, $$$ n = k + \lfloor \sqrt k +0.5 \rfloor$$$

    Intuition:

    Suppose $$$l^2 \leq k < (l+1)^2$$$, we have $$$n = k+l$$$, if $$$n \geq (l+1)^2$$$, we have to add 1 to compensate for that new square. So $$$n=k+l$$$ or $$$n=k+l+1$$$

    $$$n \geq (l+1)^2 , k \geq l^2+l+1 > l^2+l+0.25, \sqrt k > l+0.5$$$

    The formula follows.

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

      I understand the derivation, but I am unsure how $$$m - 0.5 < \sqrt{k} < m + 0.5$$$ follows from the condition $$$m^2 - m < k < m^2 + m + 1$$$.

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

        $$$m^2-m < (m^2-m+1/4) = (m-0.5)^2 < k < (m+0.5)^2 = m^2+m+1/4 < m^2+m+1$$$

        As you can see, 1/4 is added for lower bound, 3/4 is removed for upper bound, so the inequality only works because k is a positive integer.

»
11 days ago, # |
  Vote: I like it +3 Vote: I do not like it

If maxa is sth like 2^20, E will be a good problem. What a pity.

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

A O(1) solution for C exists: if some solution exists both b ^ d and c ^ d will be solutions. This comes from simplifying the truth table.

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

    O(1) solution for B exists toocout << k + (int)sqrtl(k + (int)sqrtl(k)) << endl;

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

      I don't think this is O(1) since sqrt is log(n) time complexity

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

        It's considered to be constant in bit complexity, just as how we consider other arithmetic operations to have constant complexity.

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

    Amazing

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

    if a = 1 then a | b = 1 and a & c = c LHS = 1 — c = !c
    and if a = 0 then a | b = b and a & c = 0 so LHS = b — 0 = b

    a=0 => LHS=b
    a=1 => LHS=!c

    so for each bit where b != d, we can't have LHS = b, so we are forced to set a = 1, otherwise LHS = b != RHS
    and if b = d, then we can simply set a = 0, and a = 1 may also work but no need for this ..
    we get a=0 if b=d and a=1 if b!=d, this is xor, so a = b ^ d

    and for each bit where !c != d <=> c = d, we are forced to set a = 0 to avoid LHS = !c
    , otherwise we can set a = 1,
    so a=0 if c=d and a=1 if c differs from d, again xor, a = c ^ d

»
11 days ago, # |
  Vote: I like it +19 Vote: I do not like it

In problem C simply set a to b xor d and check if it works

»
11 days ago, # |
  Vote: I like it +1 Vote: I do not like it

You put image of editorial C to editorial D. By accident I suppose

»
11 days ago, # |
  Vote: I like it +7 Vote: I do not like it

I got the idea of problem B fast because of 1909E - Multiple Lamps.

The idea
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How was I supposed to solve that B problem, I literally had 0 idea that I will have to build a formulae for that, plus the observation required for the problem isn't normal at all.

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

    Binary search is an alternative solution

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

    Here is how I approached it. First I assumed it to be a dumb problem. And from my past experience and noticing that n and k are not far apart in the samples, and by thinking about prime factorization and number of factors (however I didn't dive into that because I was lazy) I suspect maybe only the first few bulbs are not on. And I printed a table of the first 100 n and k, and quickly realized that k=n-(int)sqrtl(n). Obviously then you may construct some weird formula to do it backwards, but I suddenly came up with binary search and solved it.

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

    I didn't think of establishing a formula when solving this problem, but I found the following pattern by observing the case of n=24: 0110111101111110111111110 Using this rule, the problem is transformed into how many zeros need to be inserted into k ones

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

contest is too math

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

In B no need for a formula, you can just binary search for the answer, it only needs that observation

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

    That observation is too much for me, tell me how much more I need to practice in order to get that B always right.

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

      I saw that observation before in blogs but usually you just need practice to get observations fast, if you aren't sure how to practice correctly I think there's lots of cf blogs on it

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

    I personally guess that formula was a trap for chatgpt cheaters

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

Can someone help me with my code for E. I am finding probability for each bit to be active or not then for all number adding it's contribution to expectation.

Code

z[i][0][j] represent prob in first i element our subset's xor will have j'th bit set

z[i][1][j] represent prob in first i element our subset's xor will not have j'th bit set

then for each number(0-1023) i add contribution number 5's contribution would be simply (z[n-1][0][0]*z[n-1][1][1]*z[n-1][2][0])*5*5

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

    Squaring is not linear so you can't handle bit by bit without doing the editorial's trick, what works is z[i][j] represents probability in first i element that the xor is equal to j

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

      i do understand editorial's way but can't find mistake in my own approch. can you may be give me little example

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

        Oh I didn't understand your solution, it looks like it should work, there might be an implementation mistake somewhere

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

    At first I thought of something similar for this problem. The issue is that the probability of getting a 1 on the ith bit is not independent to the probability of getting a 1 on the jth bit. An example of this may be that given the case:

    1

    3

    5000

    I can either take the 2^0 bit and the 2^1 bit or I can take neither, yet your implementation may give some probability to 2's contribution.

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

    I had the same idea when implementing at first, but the bit-by-bit approach doesn't work because you're trying to use linearity of expectation on a non-linear operation (squaring). If you're given $$$A=[101_2]$$$ and $$$P=[0.5]$$$, then you should have a 50% chance of obtaining $$$0^2=0$$$ and a 50% chance of obtaining $$$(101_2)^2 = 25$$$. However, if you solve bit-by-bit, your solution will conclude that you have a 25% chance of obtaining $$$(000_2)^2=0$$$, a 25% for $$$(001_2)^2=1$$$, 25% for $$$(100_2)^2=16$$$, and 25% for $$$(101_2)^2=25$$$, which should be impossible since you can only xor by full numbers, not just their individual bits.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Let's say you only have one element in the array, 3. I believe your solution produces a non-zero expected value for the XOR to be 1, because the 0th bit is set in 3. But a XOR value of 1 cannot be achieved.

»
11 days ago, # |
  Vote: I like it +32 Vote: I do not like it

The editorial solution for E is too complicated. There is a much easier O(1024 * n) dynamic programming solution which comfortably fits within time limit.

»
11 days ago, # |
  Vote: I like it +16 Vote: I do not like it

Why is Carrot not working !?

»
11 days ago, # |
  Vote: I like it -7 Vote: I do not like it
»
11 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Seems like you didnt consider two much easier solutions in D and E

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

    I have solved D using different approach.I won't say it is easy but if someone wants to see here it it 283680740

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I solved it with approach that if we fix d and a_i % d, the request is just to merge some vertices inside segment, so its just +1 on segment offline

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

Problem D has a much easier $$$O(nd^2 + m)$$$ solution.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello can anyone help me why B submission is getting WA on Test case 8?

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me what I am doing wrong looking at my profile, I am unable to reach pupil

»
11 days ago, # |
  Vote: I like it +1 Vote: I do not like it

$$$O(nd+m)$$$ solution to D: 283633809 We can brute force all edges and run dfs for connected components, since there are at most $$$2*d$$$ edges per node.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can u explain how can a node have at most 2*d edges only

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

      For each d and a particular number a, a can only be connected to a-d or a+d.

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

Can anyone help me debug my code, It failed test case 8. I tried so hard today but not enough :(

Submission:283668245

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

    use sqrtl, because sqrt looses precision with big numbers (i didn't solve B because of that)

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

      I struggled with this as well, until I finally decided to google for "c++ square root of int64" and was able to solve the problem just in time. Then I looked at the tutorial and discovered sqrtl.

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

For C, can someone explain why it is bit independent? I am unable to wrap my head around it

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

    Assume it is not bit independent. Then there must be some i, for which (a|b)'s i-th bit is not set and (a&c)'s i-th bit is set. If (a&c)'s i-th bit is set, then a's i-th bit must also be set. But if a's i-th bit is set, then (a|b)'s i-th set must also be set, which is a contradiction. Therefore it is bit independent.

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

    Subtraction in kth bit place in p - q = r affect other places only if pk is 0 and qk is 1.

    All other cases

    For this case to happen, (ak | bk) = 0 which means ak = 0
    but (ak & ck) = 1 which means ak = 1 which is a contradiction
    Hope the explanation is clear!

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

An alternative solution to the problem D in $$$O(max_d * n + m)$$$

Consider the point $$$x$$$, note that it can only be connected to the $$$max_d$$$ points that go in front of it. We will support $$$dp[x][d] = k$$$, where $$$x$$$ is the coordinate of a point on a numeric line, $$$d$$$ is the length of the reverse step, $$$k$$$ is the maximum number of steps that will be taken from point $$$x$$$ with step $$$d$$$. Then note that we can move from point $$$x - d$$$ to point $$$d$$$ only if $$$dp[x - d][d] > 0$$$. In this case, we will draw an undirected edge between the points $$$x - d$$$ and $$$d$$$. Recalculate the dynamics for point $$$x$$$ as follows $$$dp[x][d] = max(dp[x][d], dp[x - d][d] - 1)$$$

Dynamics base, initially for all $$$x$$$ and $$$d$$$, $$$dp[x][d] = 0$$$. Now for all m triples $$$a_i, d_i, k_i$$$ we get $$$dp[a_i][d_i] = max(dp[a_i][d_i], k_i)$$$

At the end, using dfs, we will find the number of connectivity components

Code of this solution: 283668708

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

In the editorial of F, I think it should be $$$f(p^{ik},d)$$$ instead of $$$f(p^{i}k,d)$$$

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

    might be a rounding issue. generally a good idea to avoid non-integer types unless absolutely necessary

»
11 days ago, # |
Rev. 3   Vote: I like it +15 Vote: I do not like it

Where's the originality?

Problem Codeforces 976 Div2 $$$F$$$ be directly copied from AtCoder Beginner Contest 370 G link: https://atcoder.jp/contests/abc370/editorial/10906

The core idea of both problems is absolutely identical, including the approach of solving them with a convolution technique. The only noticeable difference between the two problems lies in how the function $$$f(prime)$$$ and $$$f(prime^{ki}, b)$$$ is computed. Other than that, the rest of the structure, including the logic and solution techniques, are the same. This raises concerns about originality and fair practice in problem setting across competitive programming platforms.

Problem Codeforces 976 Div2 $$$E$$$ has solution with the most basic dp idea with $$$O(n \cdot 1024)$$$.

As someone who placed officially 12-th in Div 2, I’m absolutely disappointed with how Codeforces 976 Div2 F turned out.

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

..

»
11 days ago, # |
Rev. 6   Vote: I like it +1 Vote: I do not like it

An alternate solution to D which doesn't use DP:

Similar to the solution in the editorial I used a DSU to keep track of components, but to check whether elements $$$i$$$ and $$$i+d_i$$$ are connected, I simply need to check among operations $$$j$$$ where $$$d_j = d_i$$$, and $$$a_j \% d_j = i\%d_i$$$. I used a map to store sets of operations together based on $$$d_j$$$ and $$$a_j\%d_j$$$, and I stored each operation as a pair $$$[ a_j, a_j + k_j \cdot d_j ]$$$.

Now each set of operations can now simply be represented as sets of intervals, and I used a datastructure which I called an IntervalSet which internally uses an std::set to efficiently a insert intervals in amortized $$$O(\text{log n})$$$ and store them efficiently by combining overlapping intervals and query whether an interval is completely included in the set in $$$O(\text{log n})$$$ where $$$n$$$ is the number of intervals in the set. This allows me to simply query whether $$$[i,i+d_i]$$$ is included in the among the operations with $$$d_j = d_i$$$, and $$$a_j \% d_j = i\%d_i$$$ which makes the code very simple.

void solve(){
  int n,m; cin>>n>>m;
  
  DSU dsu(n);
  
  map<pii, IntervalSet2<int>> mp;
  for_(i,0,m) {
    int a,d,k; cin>>a>>d>>k;
    a--;
    mp[{d,a%d}].insert({a, a+k*d}); 
  }
  
  for_(i,0,n){
    for_(di,1,11){
      if (i+di >= n) break;
      if (mp[{di,i%di}].contains({i,i+di})) dsu.merge(i,i+di);
    }
  }
  
  auto groups = dsu.groups();
  cout<<sz(groups)<<nl;
}

My submission: 283669482

PS: I used ChatGPT to help in implementing the IntervalSet class so its not in a great state rn;) and I haven't seen any implementations of such an IntervalSet class, so I would love to learn about any other implementations you guys know about.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

problem B solution without Binary search : solution

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

problem a can be solved by take log?

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

    I also have the same question!

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

    Yep it can be.

    int log(int n, int o) {
        int c = 0;
        int p = 1;
        for (;p <= n; p*=o, c++) {}
        return c-1;
    }
    
    
    void solve()
    {
        int n, o;
        cin>>n>>o;
        int r=0;
        if(o==1){
            cout<<n<<endl;
            return;
        }
        for(;n>0;){
            int t =llround(pow(o, log(n, o)));
            r+=n/t;
            n=n%t;
        }
        cout<<r<<endl;
    }
    
    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I try your solution but it got tle on testcase 3

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

        Hey, did you get the answer? I have been racking my brain around this for a day:

        Check my comment: Comment-1203949

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        hmm really?

        check out this submission, my submission didn't get tle:

        283695273

        • »
          »
          »
          »
          »
          10 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I saw your submission. I used #define endl '\n',endl flushes the output making it slower. and you should also use ios_base::sync_with_stdio(false); cin.tie(nullptr);

          • »
            »
            »
            »
            »
            »
            10 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Hi, I've used #define endl "\n" as well...

              ios::sync_with_stdio(false);
              cin.tie(nullptr);
              cout.tie(nullptr);
            

            Also used these in my main function, please check again :) Highly unlikely that these have anything to do with the WA though!

            • »
              »
              »
              »
              »
              »
              »
              10 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I was replying to thuctapsinh.

            • »
              »
              »
              »
              »
              »
              »
              10 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              About you, I looked at your comment, both of the submission link you put are accepted so I don't really get what you meant.

        • »
          »
          »
          »
          »
          10 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Just want to point out: You are not actually using the log function to find out the highest power of k, instead you have used an iterator to find it out. So not really applicable to my doubt. I have found a similar solution which got AC but the entire point is that why is log() not working

          • »
            »
            »
            »
            »
            »
            10 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            What do you meant by using iterator? I built my own ceiled log function for it.

            • »
              »
              »
              »
              »
              »
              »
              10 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              The for loop inside the log function is what I'm referring to... Nevermind, thanks for the help!

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

                Look at my profile submission, I have tried using your version of the code and it got accepted in GCC 14 and GCC 13 but rejected in GCC 7 that may be the issue.

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

                  How can one figure this out in a contest! :( Though I used C++20 as my compiler in the contest, still gave a WA on Testcase #4... Can you check out my WA code? The logic seems to be right, it still gives a WA

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

          I found out my code got TLE because I miss "#define int long long" line, Thank you for the solution! It's very helpful!

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

      thx a lot ,but why when i use log(n)/log(k) didnot work ,(log here is bultin function)

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

        Checkout this submission of mine, here I used log(n)/log(k) 283840657

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

          i found that you use GNU G++20 13.2(64bit ,winlibs) but i use GNU G++17 7 .3.0 so your code and my code got wrong answer on test2 if i use GNU G++17 7 .3.0 but it give me accepted if i use GNU G++20 13.2(64bit ,winlibs) . because GNU G++20 13.2(64bit ,winlibs) has more features and updates . thank you very much , i got a good information!

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

            Yep to be more precise, programming languages are bad at floating points, log returns float/double, it may return 3.99999 which when converted to int becomes 3 and it will cause error. GNU G++ 20 and above solves this as it problem. To do it in GNU 17, you need to make your own log function as I did earlier or Search for articles (especially before 2020) in codeforces to deal with it.

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

Although I know $$$O(1204\cdot n)$$$ is not the standard solution to E, I have encountered a strange TLE in this solution by just moving $$$M = 10^9 + 7$$$ to the inside of the $$$solve()$$$. 283686661 283686119 Could anyone tell me what's going on?

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

    if you put it outside pypy compiles it as constant, which is way faster.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone please explain what is wrong here?

During the contest, I took limits of 1 to 1e18 (wrong, I later realised why), tried upsolving with 1 to LONGMAX, 1 to 2e18. all wrong. ~~~~~ void solve() { ll k; cin >> k;

ll low = k, high = 2e18, res = -1;

while (low <= high) {
    ll mid = low + (high - low) / 2;
    ll sqcnt = floor(sqrt(mid));
    ll ON = mid - sqcnt;

    if (ON == k) {
        res = mid;
        high = mid - 1; 
    } 
    else if (ON < k)low = mid + 1; 
    else high = mid - 1;
}

cout << res << "\n";

} ~~~~~ Sorry if the code is bad/unreadable. Thank you for your time.

Just in case, if link to submission is needed. https://mirror.codeforces.com/contest/2020/submission/283589596

Thank you!

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

    Good Day ,

    Please replace sqrt with `sqrtl' to avoid precision error.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Please help for question B :

why this submission: https://mirror.codeforces.com/contest/2020/submission/283695028

Gives wrong answer on test 6.

I tried locally with generated test cases my answer is exactly same as the editorial code. No diff.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Why this code is failing at test 8.

void execute_test(){
	long long n;
	cin>>n;
	long long ans=n;
	long long s=n,e=2e18;
	while(s<=e){
		long long m=(s+e)>>1LL;
		long long val=sqrt(m);
		if(m-val>=n){
			ans=m;
			e=m-1;
		}else s=m+1;
	}
	cout<<ans<<endl;
}

why binary search in editorial works perfectly, i mean both are doing the same things.

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

I have created a video solution for Problem B and Problem A on my youtube channel, please check it out, it's a simple and intuitive solution

Video solution for Problem C

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

For E I used the dumb O(1024*n) solution but idk why I'm TLEing. For this submission 283708821 it TLE test 12 since I did dp%MOD. But for the previous submission 283708742 it passes, but I all did was changing the MOD so that it MODs the whole thing instead of the dp itself. How in the world is this not the same thing???

Pls help if anyone know the issue thx <3

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone plz explain the problem A solution why we use % and / and how it is related to powers (k^x)

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

    take example of n=6492 and k=10 to make it 0 we will first apply 6 operation of 1000(10^3) 4 operations of 100(10^2) 9 operations of 10 (10^1) and 2 operations of 1 (10^0) thereby total operations are 6+4+9+2 =21 but here base is 10 now if we generalise this for kth base ans is sum of digits in kth base . This is because each non-zero digit corresponds to an operation that subtracts some multiple of a power of k now we can extract digits in base k similar to how we do in decimal base .but instead to 10 we mod by k

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

      Thank you so much it really helps me to understand the problem.

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

F can also be solved using standard min_25 sieve trick: https://mirror.codeforces.com/contest/2020/submission/283749226

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me understand why: 283765681 gives WA But: 283765681 gives AC

In the AC solution I just decrease the number of while iterations by subtracting from n multiples of maximum allowable k^x.

Whereas in the WA solution, I decrease the maximum allowable k^x one at a time.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem C why is it giving WA on test-11?

283777193

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

    Hello, did you find what the error is? I have a similar problem in WA 11.

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

      I have changed the approach, after lot of WA!

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    if (val == nd){
        a += j * (1 << i);
        break;
    }
    

    j * (1 << i) is an integer, changing it to j * (1LL << i) should do!

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

      Oh yes! It worked.

      Thanks :)

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

      Thanks a lot, i had the same stupid mistake

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Binary search for Problem-B gives WA on test-8. 283788662

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone pls explain E, how DP is being applied?

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem d can't we just make a graph with the help of dsu with the help of given nodes that we receive during input and then calculate the number of connected components?

My solution:https://mirror.codeforces.com/contest/2020/submission/283746432

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

    i did same, don't know i expected tle but i got WA can somebbody explain

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

      if you guys get the answer can you please explain to me also?

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

    before adding to the map... and make ds.parent[i] = ds.findupar(i);

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem A, i do

$$$n - k^{log_{k}{n}}$$$

till n is bigger than zero and count the operations Can anyone explain why it is wrong? It passes the provided test cases but fails on pretests

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

Looking at the tutorial of problem E, it isn't clear why the contribution of pairs of bits from both operands can be added together. When we think about the multiplication, we observe that multiple pairs $$$(i,j)$$$ can affect the same bit of the result and yield a carry over. Thus, we don't know a priori if that bit will be set (with some probability) or not, but the contribution should only count when the bit is set.

However, after some consideration, I've concluded that it doesn't matter whether the bit will be set. What matters is that the contribution of all pairs will add up (in terms of expected value), just as it would in the multiplication. Please correct me if I'm wrong in this reasoning.

  • »
    »
    10 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    You can write f(S) like this:

    Yes, it doesn't really matter whether there is carry over. It's just convenient to look at the number in base 2, that's all.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please clarify my doubt regarding the constraints in problem B.

In my Binary search approch 283836255. The code got accepted but looking at the constraints since k can be 1e18 then answer will be more than 1e18 right. but why are we using long long instead of unsigned long long here and truncating our values?

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem A, can someone explain why solving the problem for n is equivalent to solving the problem for n/k in case k divides n.
I understand that if n is a multiplier of k, then we don't need the operation of subtracting 1.. and we solve by subtracting k, k^2, ...
But what proves that the min number of operations required to solve for n/k is equal to that required for n in such case?

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

bro $$$E$$$ is so easy so yet so less accepted submissions , I missed out too , easiest problem in the contest if you know how to do memory optimisation in DP

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

The same solution problem B in JAVA does not work

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

In problem E, I tried O(n * 1024) and got tle, so I spent a lot of time to optimize it and did not have enough time to solve D.

And after contest finish, I knew that just need to add ios::sync_with_stdio to get AC

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

Can someone tell me how I can solve B in java? As far as I know there's no equivalent of sqrtl() in java and Math.sqrt() introduces precision errors for larger inputs.

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

    You can just use binary search to find square root.

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

Tip for anyone solving B:

go for the Binary Search solution Also to learn and think how to came to solution, just iterate through some cases. It took me while to figure out but once you do, it becomes easy

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

After testing multiple cases for problem C, I found that the correct answer is a=((b&c)⊕d), but I couldn't determine the exact reason behind this result. If anyone understands please help

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

why is this not a valid solution for C? 284331257

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

mmm, i thinking i better formula for B can be

ans = k + floor(sqrt(floor(sqrt(k))) + k))

the m = floor(sqrt(k)) is for know how many perfect squares be in the number k, and now we have the possible ans s. So the answer will be s = k+m;

But we have to verify if the gap between k ans k+m there is not another perfect square, so we have do the same process: ans = k + s + (s — (k+floor(sqrt(s))))

and with some algebra we can end with ans = k + floor(sqrt(s)) how the final answer, with s=k+floor(sqrt(k))

I tried my best for make the comment clear, sorry , i'm not good expressing ideas :(

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

why 0.5 was added in answer in B