Many people use std::cin to input numbers. cin is known to be slower, than scanf, however until now I did not realize how much slower it is.

The problem: 472D - Design Tutorial: Inverse the Problem

The solution using cin exceeds time limit: 11495679

The solution using scanf satisfies time limit more than enough: 11495791

The only difference between these solutions is using cin or scanf. I spent lot of time looking for a problem with algorithm itself, but slow io turned out to be the reason.

Then I found how to speen up cin (and cout): turn off synchronization with cstdio streams. However it is not sufficient for this problem. test 9 was passed, but test 10 failed: 11495880

Use scanf for large inputs.

By the way, why the output is shown in the time limit is exceeded? 11495679, test 9. The program prints the answer immediately before exiting, so if the time limit is exceeded (especially if it happens when it reads input data), it must not be having time to print the answer.

The solution.

1. Check diagonal elements of the matrix are equal to 0 and other elements are not.
2. Check that matrix is symmetrical.
3. Set root to the first vertex.
4. Find a vertex nearest to the root (or one of such possible vertices) and set it to "nearest neighbour" (variable cmp in the code).
5. For each vertex i not equal to the root and to the nearest neighbour, check that at least one of the following conditions is satisfied: (1) path from the root to i includes the nearest neighbour: D[root][cmp] + D[cmp][i] == D[root][i] and (2) path from the i to the nearest neighbour includes the root: D[i][root] + D[root][cmp] == D[i][cmp]
6. Set root to next vertex and go to 4.

PS. How to make nested list in this markdown?

UPD. Additional speed up of cin: use cin.tie(NULL) in addition to ios_base::sync_with_stdio(0). 11496401

UPD2. Reading bytes with fread are manual parsing is even faster than scanf. 11496768

Given an array of size n, for each k from 1 to n, find the maximum sum of contiguous subarray of size k.

This problem has an obvious solution with time complexity O(N²) and O(1) space. Lua code:

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

Is there any algorithm with lower time complexity? For example, O(N log N) + additional memory.

I asked this question on stackoverflow.

Related topics:

• Kadane's algorithm
• 548D - Mike and Feet
• Efficient and easy segment trees