Многие пользуются std::cin для ввода чисел. Известно, что он работает медленнее, чем scanf, но до настоящего момента я не подозревал, насколько медленнее.

Задача: 472D - Уроки дизайна задач: обратные задачи

Решение с cin не проходит ограничение по времени: 11495679

Решение с scanf проходит ограничение по времени с большим запасом: 11495791

Отличие между этими версиями состоит только в замене cin на scanf. Долгое время я искал проблему в самом алгоритме, а оказалось, что она в вводе/выводе.

Позже я прочитал, как ускорить cin (и cout), отключив синхронизацию с stdio. Однако этого оказалось недостаточно: тест 9 был пройден, но на тесте 10 уже свалилась: 11495880

Мораль: если входных данных много, то надо использовать scanf.

Кстати, меня удивило, что при превышении лимита по времени ответ всё равно выводится: 11495679, тест 9. Программа выводит ответ непосредственно перед завершением, значит при превышении лимита времени (тем более, на чтении входных данных) она не должна была бы успеть распечатать ответ.

Решение задачи.

1. Проверим, что диагональные элементы матрицы равны 0, а остальные — не равны.
2. Проверим, что матрица симметрична.
3. Назначим первую вершину корнем.
4. Найдем одну из ближайших к ней вершин и назначим её ближайшим соседом (её индекс хранится в cmp).
5. Для каждой вершины i, не являющейся корнем или ближайшим соседом корня, проверим верность хотя бы одного из утверждений: (1) маршрут от корня к i проходит через ближайшего соседа: D[root][cmp] + D[cmp][i] == D[root][i] и (2) маршрут от i к ближайшему соседу проходит через корень: D[i][root] + D[root][cmp] == D[i][cmp]
6. Назначим корнем следующую вершину и перейдем к нашу 4.

PS. Можно ли в тексте сделать вложенный список?

UPD. В комментариях предложили, как дополнительно ускорить cin: использовать cin.tie(NULL) в сочетании с ios_base::sync_with_stdio(0). 11496401

UPD2. Когда даже scanf оказывается слишком медленным, можно использовать побайтовый fread и парсить вручную. 11496768

Вчера в списке рассылки Lua было обсуждение, в каких случаях правильно использовать слова "numeric" и "numerical". Думаю, здесь это может пригодиться.

В словарях слова numeric и numerical числятся как синонимы, однако используются они по-разному. Кроме того, в некоторых значениях или переводах их можно спутать со словами numeral, digital и digit.

numeric — про то, что состоит из чисел. Перевод на русский: числовой. Примеры: numeric variable, numeric field.

numerical — про то, что работает с числами или основывается на числах. Перевод на русский: численный. Примеры: numerical methods (численные методы), numerical reasoning (математическое мышление, т.е. способность делать выводы на основе множества чисел).

numeral — как существительное, переводится на русский как числительное. Если используется как прилагательное, то относится к обозначению числа (предлагаю перевод "цифровой").

digital — в узком смысле то же, что numerical, в широком смысле — всё, что связано с компьютерами, перевод цифровой. Пример: Digital Millennium Copyright Act — Закон об авторском праве в цифровую эпоху.

digit — цифра. Редко используется в значении "палец".

Привожу несколько цитат от носителей языка.

I think "numeric" is definitely the preferred form here. While the two words may be near-synonymous by a dictionary definition, the common usage is different.

The term "numeric" is most frequently used to describe things that CONSIST of numbers, while the term "numerical" is most frequently used to describe things that USE numbers. For example, a "numeric value" is the result of an arithmetic expression, and a "numeric field" can contain a number, but a "numerical method" employs a series of computed number values to approximate a result that is difficult to evaluate directly and "numerical reasoning" describes one's ability to derive meaning from a set of numbers.

Coda Highland

What ABOUT "numeral"? It means a symbol representing a digit or number as a noun, and it means pertaining to denoting a number as an adjective. In both cases it's about how a number is written, rather than how it's handled.

Coda Highland

numeric = consisting entirely of numbers ("a numeric ID")

numerical = involving numbers ("some numerical process")

numeral = the written form of a single digit (e.g. 1 or one)

digital = technically means numerical, but more commonly taken to mean "associated with computers"

digit = the symbols used to represent numbers (i.e. the symbols 0, 1, 2, 3, 4, 5, 6, 7, 8, 9), though it's also valid to refer to the digits of non-written numbers, e.g. "the third digit of my secret code is 4" (and this example phrase also implies that said code is numeric, else you'd say "third character" or (not really correctly) "third letter") digit also = finger or thumb, but this is less common

Rena

Для массива размера n, для каждого k от 1 до n, найти максимальную сумму подмассива из последовательных элементов,

У задачи есть очевидное квадратичное решение с константным расходом памяти. Код на Lua:

array = {7, 1, 3, 1, 4, 5, 1, 3, 6}
n = #array

function maxArray(k)
    ksum = 0
    for i = 1, k do
        ksum = ksum + array[i]
    end
    max_ksum = ksum
    for i = k + 1, n do
        add_index = i
        sub_index = i - k
        ksum = ksum + array[add_index] - array[sub_index]
        max_ksum = math.max(ksum, max_ksum)
    end
    return max_ksum
end

for k = 1, n do
    print(k, maxArray(k))
end

Существует ли алгоритм меньшей сложности? К примеру, O(N log N) с использованием дополнительной памяти.

Этот же вопрос я задавал на stackoverflow.

Похожие темы:

• Kadane's algorithm
• 548D - Майк и футы
• Efficient and easy segment trees