Сообщение Re: Уникальные запросы от 17.09.2018 16:54
Изменено 17.09.2018 17:04 Qulac
Re: Уникальные запросы
Здравствуйте, SomeOne_TT, Вы писали:
SO_>Не дает покоя нерешенная задачка.
SO_>Возможно, вы покажете, как она решается?
SO_>(найти ее можно при регистрации на сайте яндекс блица по ссылке https://contest.yandex.ru/contest/8470/problems/K/)
SO_>"Пользователи задают в Яндекс.Поиске десятки тысяч запросов в секунду. Часть запросов задают сотни раз в час, другая часть запросов повторяется несколько раз в день, третью часть запросов пользователи спрашивают у Яндекса впервые.
SO_>Необходимо оценить количество уникальных запросов, при условии наличия 500 KB оперативной памяти. Гарантируется, что правильный ответ не превосходит
SO_>100000 и не меньше, чем 50000.
SO_>Решение засчитывается, если ответ отличается от правильного не более, чем на 5%. "
SO_>Для плюсов
SO_>Ограничение времени
SO_>2 секунды
SO_>Ограничение памяти
SO_>500Kb
SO_>Формат ввода
SO_>В первой строке указано число
SO_>n ≤ 500000 — количество запросов, среди которых нужно найти число уникальных. В каждой из
SO_>n последующих строк содержится по одному запросу. Длина каждого запроса не превосходит
SO_>1000 символов.
SO_>Формат вывода
SO_>Необходимо вывести одно число — оценку количества уникальных запросов. Оценка не обязана быть целой.
SO_>Я решал ее "в лоб" хэшируя запросы, но, очевидно, это неверно — совершенно не используется информация про распределение запросов.
Точность 5%, т.е. все можно не анализировать, а взять например каждый 10 запрос.
SO_>Не дает покоя нерешенная задачка.
SO_>Возможно, вы покажете, как она решается?
SO_>(найти ее можно при регистрации на сайте яндекс блица по ссылке https://contest.yandex.ru/contest/8470/problems/K/)
SO_>"Пользователи задают в Яндекс.Поиске десятки тысяч запросов в секунду. Часть запросов задают сотни раз в час, другая часть запросов повторяется несколько раз в день, третью часть запросов пользователи спрашивают у Яндекса впервые.
SO_>Необходимо оценить количество уникальных запросов, при условии наличия 500 KB оперативной памяти. Гарантируется, что правильный ответ не превосходит
SO_>100000 и не меньше, чем 50000.
SO_>Решение засчитывается, если ответ отличается от правильного не более, чем на 5%. "
SO_>Для плюсов
SO_>Ограничение времени
SO_>2 секунды
SO_>Ограничение памяти
SO_>500Kb
SO_>Формат ввода
SO_>В первой строке указано число
SO_>n ≤ 500000 — количество запросов, среди которых нужно найти число уникальных. В каждой из
SO_>n последующих строк содержится по одному запросу. Длина каждого запроса не превосходит
SO_>1000 символов.
SO_>Формат вывода
SO_>Необходимо вывести одно число — оценку количества уникальных запросов. Оценка не обязана быть целой.
SO_>Я решал ее "в лоб" хэшируя запросы, но, очевидно, это неверно — совершенно не используется информация про распределение запросов.
Точность 5%, т.е. все можно не анализировать, а взять например каждый 10 запрос.
Re: Уникальные запросы
Здравствуйте, SomeOne_TT, Вы писали:
SO_>Не дает покоя нерешенная задачка.
SO_>Возможно, вы покажете, как она решается?
SO_>(найти ее можно при регистрации на сайте яндекс блица по ссылке https://contest.yandex.ru/contest/8470/problems/K/)
SO_>"Пользователи задают в Яндекс.Поиске десятки тысяч запросов в секунду. Часть запросов задают сотни раз в час, другая часть запросов повторяется несколько раз в день, третью часть запросов пользователи спрашивают у Яндекса впервые.
SO_>Необходимо оценить количество уникальных запросов, при условии наличия 500 KB оперативной памяти. Гарантируется, что правильный ответ не превосходит
SO_>100000 и не меньше, чем 50000.
SO_>Решение засчитывается, если ответ отличается от правильного не более, чем на 5%. "
SO_>Для плюсов
SO_>Ограничение времени
SO_>2 секунды
SO_>Ограничение памяти
SO_>500Kb
SO_>Формат ввода
SO_>В первой строке указано число
SO_>n ≤ 500000 — количество запросов, среди которых нужно найти число уникальных. В каждой из
SO_>n последующих строк содержится по одному запросу. Длина каждого запроса не превосходит
SO_>1000 символов.
SO_>Формат вывода
SO_>Необходимо вывести одно число — оценку количества уникальных запросов. Оценка не обязана быть целой.
SO_>Я решал ее "в лоб" хэшируя запросы, но, очевидно, это неверно — совершенно не используется информация про распределение запросов.
Точность 5%, т.е. все можно не анализировать, а взять например каждый 10 запрос или сравнивать только начало строк.
SO_>Не дает покоя нерешенная задачка.
SO_>Возможно, вы покажете, как она решается?
SO_>(найти ее можно при регистрации на сайте яндекс блица по ссылке https://contest.yandex.ru/contest/8470/problems/K/)
SO_>"Пользователи задают в Яндекс.Поиске десятки тысяч запросов в секунду. Часть запросов задают сотни раз в час, другая часть запросов повторяется несколько раз в день, третью часть запросов пользователи спрашивают у Яндекса впервые.
SO_>Необходимо оценить количество уникальных запросов, при условии наличия 500 KB оперативной памяти. Гарантируется, что правильный ответ не превосходит
SO_>100000 и не меньше, чем 50000.
SO_>Решение засчитывается, если ответ отличается от правильного не более, чем на 5%. "
SO_>Для плюсов
SO_>Ограничение времени
SO_>2 секунды
SO_>Ограничение памяти
SO_>500Kb
SO_>Формат ввода
SO_>В первой строке указано число
SO_>n ≤ 500000 — количество запросов, среди которых нужно найти число уникальных. В каждой из
SO_>n последующих строк содержится по одному запросу. Длина каждого запроса не превосходит
SO_>1000 символов.
SO_>Формат вывода
SO_>Необходимо вывести одно число — оценку количества уникальных запросов. Оценка не обязана быть целой.
SO_>Я решал ее "в лоб" хэшируя запросы, но, очевидно, это неверно — совершенно не используется информация про распределение запросов.
Точность 5%, т.е. все можно не анализировать, а взять например каждый 10 запрос или сравнивать только начало строк.