DjangoBB LoFi version

nokados

Окт. 4, 2014 18:57:31

Прошу помощи:
Задача:

Ограничение времени 	1 секунда
Ограничение памяти 	64Mb
Ввод 	стандартный ввод или input.txt
Вывод 	стандартный вывод или output.txt

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

Первая строка входного файла содержит одно число N от 0 до 1000. Затем идет не более 10000 строк с информацией о запросах в формате “дата\tзапрос\tрегион\tколичество”, причем для каждого региона каждый запрос встречается не более одного раза за день. Количество — натуральное число от 1 до 109. День, запрос и регион — строки длины не более 100, не содержащие символов табуляции.
Формат вывода

Для каждой даты рассмотрите N самых популярных запросов за эту дату. При равенстве частот запросов сравнивайте запросы лексикографически, и берите первые. Выведите получившиеся результаты в формате “дата\tзапрос”, отсортировав их лексикографически по дате, затем по популярности, и наконец лексикографически по запросу.
Пример

Ввод

2
01.01.2014	We love python	HSE	1
01.01.2014	We love PEP8 too	HSE	1
01.01.2014	E225 missing whitespace around operator	Moscow	2
01.01.2014	E201 whitespace after '{'	Saint Petersburg	25
01.01.2014	E231 missing whitespace after ':'	Moscow	5
02.01.2014	E225 missing whitespace around operator	Moscow	3
02.01.2014	E225 missing whitespace around operat32[code python][/code]or	Saint Petersburg	1312
02.01.2014	E501 line too long (80 > 79 characters)	Moscow	4
02.01.2014	E203 whitespace before ':'	Moscow	5
03.01.2014	E231 missing whitespace after ':	Moscow	19
03.01.2014	E225 missing whitespace around operator	New-York	12
04.01.2014	We will solve this problem	HSE	1

Вывод

01.01.2014	E201 whitespace after '{'
01.01.2014	E231 missing whitespace after ':'
02.01.2014	E225 missing whitespace around operator
02.01.2014	E203 whitespace before ':'
03.01.2014	E231 missing whitespace after ':
03.01.2014	E225 missing whitespace around operator
04.01.2014	We will solve this problem

Мое решение 1

import sys
N = int(input())
requests = {}
for line in sys.stdin:
    date, query, region, number = line.split('\t')
    number = int(number)
    if date in requests:
        if query in requests[date]:
            requests[date][query] += number
        else:
            requests[date][query] = number
    else:
        requests[date] = {query: number}
dates = list(requests.keys())
dates.sort()
for date in dates:
    queries = requests[date]
    res_q = []
    for i in range(N):
        max_val = 0
        max_key = -1
        for query in queries:
            if queries[query] > max_val:
                max_val = queries[query]
                max_key = query
            elif queries[query] == max_val:
                if query < max_key:
                    max_key == query
        if max_key != -1:
            print(date, max_key, sep='\t')
            queries.pop(max_key)

Решение в лоб. Работает, но из-за своей неэфективности превышает лимит по времени на одном из тестов.

Мое решение 2

import sys
N = int(input())
requests = {}
resinput = ''
for line in sys.stdin:
    resinput += line
    date, query, region, number = line.split('\t')
    number = int(number)
    if date in requests:
        if query in requests[date]:
            requests[date][query] += number
        else:
            requests[date][query] = number
    else:
        requests[date] = {query: number}
dates = list(requests.keys())
dates.sort()
for date in dates:
    queries = requests[date]
    res_q = []
    l = 0
    for query in queries:
        num = queries[query]
        if l == 0:
            res_q.append({'num': num, 'query': query})
            l = 1
        else:
            i = 0
            j = l-1
            m = (i+j)//2
            while i <= j:
                if num > res_q[m]['num']:
                    j = m-1
                elif num < res_q[m]['num']:
                    i = m+1
                else:
                    if query < res_q[m]['query']:
                        j = m-1
                    else:
                        i = m+1
                m = (i+j)//2
            res_q.insert(i, {'num': num, 'query': query})
            l += 1
            if l > N:
                res_q = res_q[:N]
                l = N
    for res in res_q:
        print(date, res['query'], sep='\t')

Заменил полный перебор массива на бинарный поиск места, куда вставляется очередной запрос, в сортированном массиве (res_q). Но теперь ошибка в тесте раньше того, на котором был Time Limit в прошлом примере.

nokados

Окт. 5, 2014 15:58:30

Неужели нет никаких идей?

nokados

Окт. 5, 2014 18:55:49

Ну все, я уже сам решил.

import sys
N = int(input())
dates = {}
def print_queries():
    keys = list(dates.keys())
    keys.sort()
    for date in keys:
        L = [(query, dates[date][query]) for query in dates[date]]
        L.sort(key=lambda x: [-x[1], x[0]])
        i = 0
        for q in L:
            if i >= N:
                break
            print(date, q[0], sep='\t')
            i += 1
for line in sys.stdin:
    date, query, region, number = line.split('\t')
    number = int(number)
    if date in dates:
        if query in dates[date]:
            dates[date][query] += number
        else:
            dates[date][query] = number
    else:
        dates[date] = {query: number}
print_queries()

nokados

Окт. 5, 2014 19:00:36

Вообще, функция print_queries() здесь не нужна, она - рудимент. Осталась от прошлой версии, где вместо списка с датами я пытался выводить отдельно логи для каждой даты. Нужно было использовать эту функцию и в цикле перебора в блоке else, и после цикла для вывода последней даты. Это не сработало, так как на одном из тестов даты были неупорядочены

py.user.next

Окт. 5, 2014 23:08:08

nokados

dates = list(requests.keys())
dates.sort()

>>> d = {'a': 1, 'b': 2, 'c': 3}
>>> d
{'c': 3, 'b': 2, 'a': 1}
>>> srt = sorted(d)
>>> srt
['a', 'b', 'c']
>>>

nokados
Первая строка входного файла содержит одно число N от 0 до 1000.

И что оно значит?

nokados
Ввод

01.01.2014 We love python HSE 1
01.01.2014 We love PEP8 too HSE 1
01.01.2014 E225 missing whitespace around operator Moscow 2
01.01.2014 E201 whitespace after '{' Saint Petersburg 25

nokados
Вывод

01.01.2014 E201 whitespace after '{'
01.01.2014 E231 missing whitespace after ':'

Какая тут связь?

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

По идее, он должен просто суммировать количества одинаковых запросов в каждой дате (которые могут идти не по порядку), а потом выдавать один самый частый запрос (если одинаковые, то первый в лексикографическом порядке).