pedrovictor48's blog

By pedrovictor48, history, 3 years ago, In English

Firstly i came up with this solution: https://codeforces.net/contest/1542/submission/121218884 I think it's O(n) in worst cases, and i got TLE. But shouldn't O(n) be sufficient for these constraints?

After the contest I also updated a O(logn) solution, and its similar to others that i saw submitted, but its getting TLE too: https://codeforces.net/contest/1542/submission/121269280

What am I missing here?

  • Vote: I like it
  • -3
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

I didn't think much but Im certain that you should make p long long. Its possible for it to keep overflowing and doing a lot of interactions.

»
3 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

If $$$a$$$ is $$$10^9-1$$$ and $$$n$$$ is $$$10^9$$$,first $$$p$$$ will multipliy by $$$a$$$ and then $$$p$$$ is $$$10^9-1$$$,second $$$p$$$ will multiply by $$$a$$$ again and $$$p$$$ will be more than $$$\text{INT_MAX}$$$.It will be very likely that $$$p$$$ overflows and make it less than or equal to $$$n$$$,so this code will keep running and you will get TLE.

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

    Thanks, i get it in O(logn) sol, but do you know why this isn't working? isn't it linear?

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

        You can't simulate the process of substracting b,it is very likely to get TLE,too.And the solution isn't substracting or dividing,it is adding and multipling.

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

      Sorry,I can see your picture that you post.

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

          Let $$$x=1$$$.

          If you add $$$b$$$ to $$$x$$$ first,and then multiply $$$x$$$ by $$$a$$$.In fact, it is equivalent to multiply $$$x$$$ by $$$a$$$ and add $$$b$$$ to $$$x$$$ for $$$a$$$ times.So you should multiply first and add,then you can strictly get $$$O(\log n)$$$

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

      Let $$$a=10^9,b=1,n=10^9-1$$$,when you take this data to your code and run it again, the program will continue to decrease by $$$1$$$, so that your code will be linear and will burst.