Блог пользователя nishkarsh

Автор nishkarsh, история, 2 месяца назад, По-английски

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
  • Проголосовать: нравится
  • -349
  • Проголосовать: не нравится

»
2 месяца назад, # |
  Проголосовать: нравится +325 Проголосовать: не нравится

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

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится -184 Проголосовать: не нравится

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

    We didn't knew that these solutions existed.

    • »
      »
      »
      2 месяца назад, # ^ |
        Проголосовать: нравится +25 Проголосовать: не нравится

      know*

    • »
      »
      »
      2 месяца назад, # ^ |
        Проголосовать: нравится +14 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        2 месяца назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          2 месяца назад, # ^ |
            Проголосовать: нравится -23 Проголосовать: не нравится

          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.

      • »
        »
        »
        »
        2 месяца назад, # ^ |
          Проголосовать: нравится +12 Проголосовать: не нравится

        What is amazing about this contest?

    • »
      »
      »
      7 недель назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      then you just killed the problem

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +24 Проголосовать: не нравится

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

    • »
      »
      »
      2 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      2 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      can you please explain your optimized solution for problem E?

      • »
        »
        »
        »
        2 месяца назад, # ^ |
        Rev. 6   Проголосовать: нравится +10 Проголосовать: не нравится

        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://codeforces.me/contest/2020/submission/283652607 In my case cnt array is pdp precalculations.

    • »
      »
      »
      7 недель назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      it is still O(n*1024) ?

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    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 :)

    • »
      »
      »
      2 месяца назад, # ^ |
      Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        7 недель назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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 ?

        • »
          »
          »
          »
          »
          7 недель назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            7 недель назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    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.

  • »
    »
    2 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится -12 Проголосовать: не нравится

    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

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
2 месяца назад, # |
  Проголосовать: нравится -76 Проголосовать: не нравится

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.

»
2 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

  • »
    »
    2 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    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$$$

    • »
      »
      »
      2 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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$$$

      • »
        »
        »
        »
        2 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          2 месяца назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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

          • »
            »
            »
            »
            »
            »
            7 недель назад, # ^ |
            Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

            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.

  • »
    »
    2 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
2 месяца назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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 )$$$?

  • »
    »
    2 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    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.

    • »
      »
      »
      2 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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$$$.

      • »
        »
        »
        »
        2 месяца назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        $$$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.

»
2 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
2 месяца назад, # |
Rev. 2   Проголосовать: нравится +53 Проголосовать: не нравится

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.

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      2 месяца назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        2 месяца назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Amazing

  • »
    »
    7 недель назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
2 месяца назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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

The idea
»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Binary search is an alternative solution

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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.

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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

»
2 месяца назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

contest is too math

»
2 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      2 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I personally guess that formula was a trap for chatgpt cheaters

»
2 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      2 месяца назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        2 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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.

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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.

  • »
    »
    7 недель назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
2 месяца назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится

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.

»
2 месяца назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Why is Carrot not working !?

»
2 месяца назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

E can (accidentally) be solved with FWT: https://codeforces.me/contest/2020/submission/283601247

»
2 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      2 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

»
2 месяца назад, # |
Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

$$$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.

»
2 месяца назад, # |
Rev. 4   Проголосовать: нравится +2 Проголосовать: не нравится

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

Submission:283668245

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      2 месяца назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      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 дней назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Same bro, use isqrt with Python

»
2 месяца назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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.

  • »
    »
    2 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    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!

»
2 месяца назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 месяца назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

https://codeforces.me/contest/2020/submission/283572788

can anyone help me why above is wrong

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 месяца назад, # |
Rev. 3   Проголосовать: нравится +15 Проголосовать: не нравится

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.

»
2 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

..

»
2 месяца назад, # |
Rev. 6   Проголосовать: нравится +1 Проголосовать: не нравится

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.

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

problem B solution without Binary search : solution

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

problem a can be solved by take log?

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I also have the same question!

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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;
    }
    
    • »
      »
      »
      2 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I try your solution but it got tle on testcase 3

      • »
        »
        »
        »
        2 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        Check my comment: Comment-1203949

      • »
        »
        »
        »
        2 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        hmm really?

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

        283695273

        • »
          »
          »
          »
          »
          2 месяца назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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);

          • »
            »
            »
            »
            »
            »
            2 месяца назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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!

        • »
          »
          »
          »
          »
          2 месяца назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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

          • »
            »
            »
            »
            »
            »
            7 недель назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

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

            • »
              »
              »
              »
              »
              »
              »
              7 недель назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

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

              • »
                »
                »
                »
                »
                »
                »
                »
                7 недель назад, # ^ |
                Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 недель назад, # ^ |
                  Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                  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 недель назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      7 недель назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 недель назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          7 недель назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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!

          • »
            »
            »
            »
            »
            »
            7 недель назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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.

»
2 месяца назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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://codeforces.me/contest/2020/submission/283589596

Thank you!

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Please help for question B :

why this submission: https://codeforces.me/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.

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
2 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
2 месяца назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

283777193

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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://codeforces.me/contest/2020/submission/283746432

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 месяца назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    2 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    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.

»
7 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
7 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
7 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The same solution problem B in JAVA does not work

»
7 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

why is this not a valid solution for C? 284331257

»
7 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 :(

»
6 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

why 0.5 was added in answer in B

»
5 недель назад, # |
Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

Thanks for the editorial

»
5 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

in the editorial of problem D, can anyone please explain/elaborate the following:

We will consider dp[j][w], which denotes the number of ranges that contain the j node in connection by the triplets/ranges with w as d and j is not a + k*d

What do we mean j is not a + k*d ? how can j node be a part of connection if it is not representable as a + k*d ?

»
5 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The binary search in Question B is still a bit difficult to understand. For example, when k=6, both n=8 and n=9 can be calculated on a computer as diff=n-sqet(n)=6=k. So how can this issue be avoided?

  • »
    »
    5 недель назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    you have to find the smallest n satisfying n-sqrt(n) = k so in the code also when mid-sqrt(mid) >= k then r = mid and else l = mid which ensures that l will be the largest number such that l — sqrt(l) < k and r will be the smallest such that r-sqrt(r) >= k.

»
10 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

the link to the book isn't working (B)

»
8 дней назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

can someone explain why for A the following logic is giving WA

int n, k;
cin >> n >> k;
if(k > n || k == 1) {
    cout << n << endl;
    continue;
} 

int cnt = 0;
while(n) {
    int a = log(n)/log(k);
    n -= pow(k, a);
    cnt++;
}
cout << cnt << endl;