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!
this might help
Thanks for you effort but still TLE.
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:
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.
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.
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.
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.
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.
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.
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.
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 - Оценочная строка,
8ggenerates an executable costing 2.46s on my machine. Andgccgogenerates an executable costing 1.28s. It seemsgccgois 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.
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.