Editorial for SAC '21 Code Challenge P4 - Averaging Averages

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: maxcruickshanks

Subtask 1

Maintaining the averages in an array and running a for-loop to sum up the grades and dividing by the total number of grades suffices.

Time Complexity: \mathcal{O}(NQ)

Subtask 2

A prefix sum array can be used to expedite these queries since the array is static.

Time Complexity: \mathcal{O}(N + Q)

Comments


  • 0
    22yeetz22  commented on June 16, 2023, 4:10 p.m. ← edited

    If you keep getting TLEs with Python, use PyPy instead.


  • 9
    suguruchhaya  commented on May 20, 2021, 7:30 p.m. ← edited

    I used C++ but still had trouble with TLE. Specific tips:

    1. Read the array and create the prefix sum in one pass.
    2. The int type is large enough. No need to use long or long long.
    3. Write cin.sync_with_stdio(0); and cin.tie(0) at the top or use scanf. Refer to https://dmoj.ca/tips/.

    With these, you should be good to go!