nkamzabek's blog

Best use of binary search in real life
By nkamzabek, history, 4 years ago, In English

Yesterday, when I was writing virtual contest in GYM, I found some interesting feature. From status I could find number of tests, I guess it works for any problem. However, I have not tested it for official round, but at all it's worth for a new blog. In the status-filter bar, you maybe have seen a section "test", but you probably dont know the magic, which can be done with it.

By changing sign to $$$\geq$$$(is greater than or equal to) and giving number to this empty space you can find number of test. If you found that maximal $$$x$$$, that all submissions are accepted and no submissions at $$$x + 1$$$, $$$x$$$ is the number of test. You may ask, why binary search is written in the title. It's the most optimal and the fastest way to find this number, less than 10 steps)

P.S. Sorry for my poor English

UPD: It works in Official Rounds.

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

»
4 years ago, # |
  Vote: I like it +41 Vote: I do not like it

Typical useless feature from Reddreamer:(

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

It is not the number of tests, it is the last test submissions ever failed on.

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

In the rounds you can use m2.codeforces.com. The judge simply shows the number of tests.

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

    original post: using ternary search to optimize function

    this comment: using calculus to optimize function

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

Also CF hasn't __int128 ,but other platforms like AtCoder , YandexContest and etc have

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

    and Why do you exactly need this?? use long long or similar data types

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

      Stuff like factoring or primality testing of numbers larger than 1e9 is very painful to do without __int128. The standard convex hull trick with constants ~1e18 and multipliers ~1e9 for the lines requires __int128 or custom long long multiplication to protect from overflows. There are a lot of other applications as well that I just can't recall right now.

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

        Oh, I see but On some platforms, long long is 128 bits, but there is no guarantee.

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

          I don't know a platform where long long is 128 bits, mind sharing it?

          → Reply