Блог пользователя filo

Автор filo, история, 7 лет назад, По-английски

Hi all,

I know Go isn't the most popular language when it comes to competitive programming but since it is added on CF I will ask this question.

In this problem I try to read two strings, the problem is that Go's bufio.Text() or bufio.ReadLine() cannot read million characters in one string.

I've tried lots of other options as well(already -57 on that problem), like increasing buffer size for Scanner, or concatenating parts of strings returned from bufio.ReadLine() but all of them gets TLE.

I am almost sure that the solution itself is pretty fast and the problem is in reading from the input.

If you have any idea how to speed it up you are welcome!

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Your solution involves O(n) inversions via fast exponentiation to 109 + 5. That's sixty million multiplications and thirty million divisions of 64-bit numbers. That's quite a lot and I can easily imagine it getting TLE even if you don't consider reading time.

Two suggestions:

  1. Generate a big test locally and check how long it takes for your solution to read the input.
  2. Optimize your solution so it doesn't do O(n) fast exponentiations.
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Let's consider two ways of reading input A and B.

    If I read with method A I pass test 14 in 31 ms, but method A isn't suitable for test 22 because of the specifications mentioned above.

    If I read with method B, which should read whole lines without character limitations I get TLE on test 14.

    That's why I think the solution itself works quiet fast.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Method B may be 10-100-1000(sic!) times slower than method A, so test 14 may actually be quite small, so that the solution works ok. This is not a joke.

      • »
        »
        »
        »
        7 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        I got your point and even if you are right, that still doesn`t answer my question. Which method should I use? A: which is super slow or B: which cannot handle large strings. I believe what I am looking for is method C which is faster than A and can read large strings.

        P.S. I've rewritten the code in C++ it passes in 1887 ms.

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I think bufio.ReadString('\n') is fast enough. On my machine it takes almost zero time to read two strings with length 106.

But I still get TLE... Maybe my inversion is too slow.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Yes. With a O(n) inversion preprocess algorithm I got Accepted (32779895).

    I/O is not the bottle neck of this problem.

    n - 1 ≡ nt2k - 2 (mod P) where t = ⌊ P / n and k = P mod n.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      But this is still very slow on Codeforces (much slower than equivlent C++ version 32780344). I don't know why. On my machine (x86_64, linux) the C++ version takes 0.28s and the Go version takes 0.44s.

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Wow, thanks for your reply, good job! I am not sure was that the official solution? I feel like Go performs really badly on CF, it isn't the first occasion, but it is possible to get AC with Go, so everything is OK.

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          I found the issue. It seems Google Go compiler for 32-bit x86 (8g) generates very low-performance code. Unfortunately, Codeforces has 32-bit judge machines.

          For 895D - String Mark, 8g generates an executable costing 2.46s on my machine. And gccgo generates an executable costing 1.28s. It seems gccgo is better Go compiler for 32-bit x86.

          Perhaps Google Go compiler is optimized for modern machine with enough registers (for example x86-64), and 32-bit x86 doesn't have much registers.

          • »
            »
            »
            »
            »
            »
            7 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Makes sense, nice research. But unfortunately there's nothing we can do, other than writing super optimized code for Go when the time limits are tight.