Killever's blog

E. Weakness and Poorness (Time Limit)
By Killever, 9 years ago, In English

HI,
After I got the idea of this problem and solved it true, it's my first time to solve E during contest but sadly I got TLE it seems that the time limit is too strict.
I used loop in My Ternary search (my loop limit is 400 ) and It got TLE ,after the contest I changed it to 398 and it suddenly passed.
I asked about that in a comment and ho-jo-bo-ro-lo told me he use 500 in loop and it passed but I have to use cin.tie(0);
what about submitting the same code twice with cin.tie(0) one got TLE and the other got Accepted.
Accepted
Time limit exceeded on test 22
during the contest I got TLE on Testcase #15 so if the TLE because reading and writing speed I think testcase 13,14 has the maximum limit and similar numbers so why it passed them and failed in 15.
Thanks

Tags tle
  • Vote: I like it
  • +8
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Why ternary? Binary, let's look. It's easier and faster. Second. 400 — it's too much. 100-200 for ternary search it's enough, 30-50 it's enough for binary(i used 100 because time limit was very good)

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

    Why ternary? This is the idea I came with during the contest
    also I know that 400 is large number but I think making test-cases passed for 398 and TLE on 400 is really weird.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Nothing weird. You're just unlucky man. But my solution show you that you can solve this problem without any hacks like change loop limit

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

        :D but what about submitting the same solution twice with different results (I used cin.tie(0) for both :D

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

    30-50 it's enough for binary(i used 100 because time limit was very good)

    actually 64 is enough in all cases because each iteration sets at least 1 correct bit in answer

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

      You're right. But at this problem 40 is enough

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

      Technically, yes, this is possible, but it requires every step of the binary search to partition the set of remaining values exactly in half. The set of numbers that can be represented by floats (or (long) doubles for that matter) is more dense around 0 than it is towards 1e300. If you use (l + r) / 2 as a midpoint formula, you won't get a nice 50/50 partition, and you will require more than 64 iterations.

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      This isn't true for doubles since they have exponential bits. As an example you have to halve 1.0 1075 times for it to become zero.

      → Reply