abcsumits's blog

Help me to find number of solution of this equation efficiently
By abcsumits, history, 16 months ago, In English

I have to find min value of [a/x]+[b/x]+x-1 ,where x belongs to (1,10^9) ,here [] denotes ceil value. I then observed it is monotonic in nature. Its graph will be like

The only problem i am having is to find slope(from slope i meant if every step is assumed as points ,this will help me to shift l and r) and slope can be find by use of its previous neighbour points to find neighbour of y=f(x),we need to find length of y so for given y=[a/x]+[b/x]+x-1 i need the range of the solution

  • Vote: I like it
  • +2
  • Vote: I do not like it

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

??

→ Reply
»
16 months ago, # |
  Vote: I like it +4 Vote: I do not like it

You can try ternary search

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Where have you seen that problem? I'll gladly help you if you link the source of the problem.

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

    https://codeforces.net/problemset/problem/1814/B

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

    I am trying to do binary search on stepping function

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

      You can't. It's not monotonic. The idea of the problem is that a and b is limited and by choosing x = sqrt(a+b), we find an answer that's O(sqrt(a+b)) so we can try all values up until c * sqrt(a+b) for some c and it works.

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

        There is no method to solve stepping function using binary search?

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

          Where length of steps varies*

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

            You've observed something that isn't real. Check your data again.

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

              I think graph is correct for integers

              → Reply
            • »
              »
              »
              »
              »
              »
              »
              16 months ago, # ^ |
              ← Rev. 3   Vote: I like it -25 Vote: I do not like it

              .

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

                You forgot to add x-1.

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

                  sorry about that i forgot to match equation chatgpt fault, I have drawn some example (I am generalizing it due to my intuition ), If i am wrong give me some case where it is wrong

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  16 months ago, # ^ |
                  ← Rev. 4   Vote: I like it +10 Vote: I do not like it

                  I made a python script that prints out the points where the y changes. The following is what I got for a = b = 31.

                  [(1, 62), (2, 33), (3, 24), (4, 19), (5, 18), (6, 17), (7, 16), (8, 15), (9, 16), (10, 17), (11, 16), (12, 17), (13, 18), (14, 19), (15, 20), (16, 19), (17, 20), (18, 21), (19, 22), (20, 23), (21, 24), (22, 25), (23, 26), (24, 27), (25, 28), (26, 29), (27, 30), (28, 31), (29, 32), (30, 33)]

                  look at what happens in (7, 16), (8, 15), (9, 16), (10, 17), (11, 16). That by itself is enough.

                  You're suposedly a programmer, why don't you go write something really quickly to try checking your guesses for low values? I guess you're just a product of the guessing culture cultivated in recent codeforces rounds.

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  16 months ago, # ^ |
                  ← Rev. 2   Vote: I like it +15 Vote: I do not like it

                  tfg sorry about that :(, thanks next time i will just code to check my guess(I never thought about that )

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

                Also, you shouldn't trust ChatGPT over things related to math. It's extremely bad at it.

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

        .

        → Reply
»
16 months ago, # |
  Vote: I like it +6 Vote: I do not like it

This problem can be effectively addressed using calculus, leveraging some pivotal concepts to unravel the given predicament.

1.When we differentiate an equation, we derive its slope.

2.The points of minimum or maximum correspond to instances where the slope equals zero.

3.For every point where the slope is zero:

a. If the second differentiation is positive, it signifies a minimum.
b. Conversely, if it's negative, it indicates a maximum.

So Now,

Applying differentiation to both sides, we arrive at y' = -[a/x^2] — [b/x^2] + 1. Upon equating y' to 0, we deduce x = √(a+b) and -√(a+b).

Subsequently, performing a secondary differentiation yields y" = 2[a/x^3] + 2[b/x^3]. When evaluating for x = √(a+b), we ascertain a minimum as y" remains positive at this point.

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

chatGPT is not a trustable for CP coding

→ Reply