Есть две посылки на C#: с многопоточкой — Accepted и без многопоточки — TLE. Автор решения использует Parallel.For в функции MultiplyMatrixPow, за счет чего и добивается успеха. Вопрос: сколько ядер мы можем нагружать на серверах codeforces при проверке нашего решения?
UPD: Многопоточка здесь ни при чем. В первом решении автор берет остаток от деления три раза, во втором всего один. Отсюда и выигрыш.
Look at mike's comment: blog.
Thanks, it turns out that additional cores are not used to run the program.
But why use of the parallel for speed up the solution? Are there any optimizations in comparison with the usual cycle for?
As far I know, you'll never decrease the running time on all adequate e-judges via additional threads, since they're single-cored. Your case is probably false-positive, I mean when I was writing solutions on C#, it could give different execution time on the server, and your code may give a result somewhere in an interval [2000-x, 2000+x] of milliseconds, almost randomly.
Разница в посылках не только в
Parallel.For. Если взять посылку сParallel.Forи заменить его на обычныйfor, то тоже получим AC: http://codeforces.net/contest/691/submission/41135667Увидел, в первом решении автор берет остаток три раза, во втором решении всего один, спасибо. А я затригерился только на Parallel.For