Разбор задачи «Аналитика сессий пользователей»

1. Идея

Нужно пройти по логу событий слева направо и для каждого пользователя поддерживать:

• есть ли у него сейчас открытая сессия;
• если есть, то когда она началась;
• сколько суммарно времени уже набралось по завершённым сессиям.

Так как события уже даны в неубывающем порядке времени, можно обрабатывать их последовательно, без сортировок и сложных структур.

Для этого удобно использовать два словаря:

• opened[uid] = ts — у пользователя uid сейчас открыта сессия, начавшаяся в момент ts;
• total[uid] = sum — суммарная длительность всех его сессий.

2. Наблюдения

Наблюдение 1. Что делать с LOGIN

Если приходит LOGIN:

• если у пользователя нет открытой сессии, открываем её;
• если сессия уже открыта, этот LOGIN игнорируем.

Это ровно соответствует условию.

Наблюдение 2. Что делать с LOGOUT

Если приходит LOGOUT:

• если у пользователя есть открытая сессия, закрываем её и прибавляем ts - start;
• если открытой сессии нет, событие игнорируем.

Наблюдение 3. Кто должен попасть в ответ

В ответ нужно вывести только тех пользователей, у которых была хотя бы одна корректно начатая сессия.

Это значит: пользователь должен хотя бы один раз успешно пройти через обработку LOGIN, который не был проигнорирован.

Поэтому в момент первого корректного открытия сессии удобно сразу создать запись total[uid] = 0. Тогда даже если сессия длилась 0 секунд, пользователь всё равно попадёт в итог.

Наблюдение 4. Незакрытые сессии после конца лога

Если после обработки всех событий у пользователя сессия осталась открытой, по условию считаем, что она завершилась в момент 86400.

Значит, после основного прохода надо пройти по всем пользователям из opened и прибавить 86400 - start.

Наблюдение 5. Порядок вывода

Нужно вывести пользователей по возрастанию uid.

В эталонном решении:

• в C++ используется map, он уже хранит ключи отсортированными;
• в Python в конце делается sorted(total).

3. Алгоритм

1. Считать n.
2. Создать:
   • total — словарь суммарных длительностей;
   • opened — словарь открытых сессий.
3. Для каждого из n событий:
   • считать ts, type, uid;
   • если type == "LOGIN":
     • если uid нет в opened:
       • записать opened[uid] = ts;
       • если uid ещё нет в total, создать total[uid] = 0;
     • иначе ничего не делать;
   • иначе это LOGOUT:
     • если uid есть в opened:
       • прибавить к total[uid] значение ts - opened[uid];
       • удалить uid из opened;
     • иначе ничего не делать.
4. После обработки всех событий пройти по всем оставшимся элементам в opened:
   • для каждого пользователя прибавить 86400 - start.
5. Вывести всех пользователей из total в порядке возрастания uid.

4. Почему это работает

Докажем, что алгоритм правильно считает суммарное время.

Обработка одного пользователя

Рассмотрим фиксированного пользователя uid.

Алгоритм хранит в opened только одно из двух состояний:

• у пользователя нет открытой сессии;
• у пользователя есть открытая сессия с моментом начала start.

Это полностью соответствует правилам задачи, потому что пересекающихся корректных сессий у одного пользователя быть не должно, а лишние LOGIN игнорируются.

Корректный LOGIN

Если у пользователя нет открытой сессии и приходит LOGIN, то по условию начинается новая сессия. Алгоритм именно это и делает: сохраняет время начала в opened[uid].

Если сессия уже открыта, новый LOGIN должен быть проигнорирован. Алгоритм ничего не меняет, значит состояние остаётся верным.

Корректный LOGOUT

Если у пользователя есть открытая сессия с началом start и приходит LOGOUT в момент ts, то эта сессия должна завершиться, а в ответ нужно добавить её длительность ts - start.

Алгоритм прибавляет именно это значение и удаляет пользователя из opened, то есть закрывает сессию.

Если открытой сессии нет, такой LOGOUT по условию игнорируется. Алгоритм тоже ничего не делает.

Незавершённая сессия в конце

Если после конца лога у пользователя осталась открытая сессия с началом start, по условию она считается продолжающейся до 86400.

Алгоритм после основного прохода добавляет 86400 - start, значит и этот случай обработан правильно.

Итог

Для каждого пользователя алгоритм:

• открывает сессию только в допустимый момент;
• закрывает её только допустимым LOGOUT;
• игнорирует все нештатные события по правилам;
• учитывает незакрытую сессию до конца суток.

Следовательно, сумма в total[uid] точно равна суммарной длительности всех сессий пользователя.
Так как в total пользователь добавляется при первом корректном LOGIN, в ответ попадут ровно те пользователи, у которых была хотя бы одна корректно начатая сессия.

5. Сложность

Обозначим через m число различных пользователей, которые встретились в корректных LOGIN.

C++17

Используется map, поэтому каждая операция со словарём работает за O(log m).

• обработка n событий: O(n log m);
• обработка оставшихся открытых сессий: O(m);
• вывод: O(m).

Итого: O(n log m).

Python 3

Словари работают в среднем за O(1) на операцию.

• обработка n событий: в среднем O(n);
• проход по opened: O(m);
• сортировка пользователей перед выводом: O(m log m).

Итого: в среднем O(n + m log m).

По памяти в обоих решениях хранится несколько словарей по пользователям, то есть O(m).

6. Код на C++17

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    int n;
    cin >> n;

    map<long long, long long> total;
    map<long long, int> opened;

    for (int i = 0; i < n; i++) {
        int ts;
        string type;
        long long uid;
        cin >> ts >> type >> uid;

        if (type == "LOGIN") {
            if (opened.find(uid) == opened.end()) {
                opened[uid] = ts;
                if (total.find(uid) == total.end()) {
                    total[uid] = 0;
                }
            }
        } else {
            auto it = opened.find(uid);
            if (it != opened.end()) {
                total[uid] += (long long)ts - it->second;
                opened.erase(it);
            }
        }
    }

    for (auto it = opened.begin(); it != opened.end(); ++it) {
        long long uid = it->first;
        int start = it->second;
        total[uid] += 86400LL - start;
    }

    for (auto it = total.begin(); it != total.end(); ++it) {
        cout << it->first << " " << it->second << "\n";
    }

    return 0;
}

7. Код на Python 3

n = int(input())

total = {}
opened = {}

for _ in range(n):
    parts = input().split()
    ts = int(parts[0])
    typ = parts[1]
    uid = int(parts[2])

    if typ == "LOGIN":
        if uid not in opened:
            opened[uid] = ts
            if uid not in total:
                total[uid] = 0
    else:
        if uid in opened:
            total[uid] += ts - opened[uid]
            del opened[uid]

for uid, start in opened.items():
    total[uid] += 86400 - start

for uid in sorted(total):
    print(uid, total[uid])