user311's blog

"repetedly getting TLE in interactive problem despite optimal complexity of submission"
By user311, history, 3 years ago, In English

I sincerely need help, I've tried everything to not get a TLE.

problem

my solution

Thanks in advance

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

Comments Comments (10)
| Write comment?
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

You have to flush your output. Write: fflush(stdout); After everytime you print something. Also, for interactive problems, I don't advise using ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); because it might interfere with reading input and output. You won't need the speed gains anyway for interactive problems.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it +8 Vote: I do not like it

    Absence of flush causes IL, not TL. And TS uses endl, which flushes output

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

    Still TLE, please look at this submission

    (i've added flush and removed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0))

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it -8 Vote: I do not like it

      Your first for should be for (int i = 0; (1 << i) < n * n; ++i), what a great typo :)

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

        I'm calculating row and column using (i / n) and (i % n). So I think i < n * n is right. I've wronged somewhere else.

        Please Please look once again.

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it -8 Vote: I do not like it

          No, I'm talking about first for, right after reading n. You output all powers of two for all i from 0 to n, not all powers of two, which are less than n

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

            The question requires doing just that, Also he's getting TLE at case 6(not 1). Please, look at the editorial if you don't want to read the whole question.

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

              Ah, sorry, I was just seeing output on tc 6 and was guessing it's overflow. And I was right, but in other place. If n is 6, n * n is 36 and TS gets bit up to 36, which causes overflow. It can be fixed by changing to 1ll << i, but n is up to 25

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

              Ouch, I was right. He prints powers of two till n * n, which is big enough to overflow

              → Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Your issue seems to be overflow. On the following lines:

while(i != (n * n) - 1){
    if(k & (1<<(i + 1)))
        i = i + 1;

$$$i \in [0, n^2 - 1]$$$, so $$$2^{i + 1}$$$ can be up to order of magnitude $$$10^{188}$$$ far overflowing any bit integer data type in C++. The reason why you get TLE instead of something else like WA is likely because your terminating condition is specifically i != n * n - 1, and because the if statement is now essentially gibberish since 1 << (i + 1) is just overflowed gibberish, your i might exceed n * n - 1 without ever being n * n - 1 exactly, so the while loop runs forever.

To confirm this, I changed 1 << (i + 1) to 1LL << (i + 1) to increase size up to 64-bit integer, so now it doesn't overflow for $$$n = 6$$$ and makes it to test 8.

→ Reply