Вход | Регистрация

  1  2  3
Информационные технологии :: Математика и алгоритмы

Помогите понять задачу

Помогите понять задачу
Я
   DES
 
10.08.18 - 06:39
тестовое задание для абитуры

Раскрашивание точек
ТL =1 секунда
МL=16 мегабайт
Лимит по памяти важен. Далеко не все интерпретируемые языки смогут запустить интерпретатор в этих ограничениях. Выбирайте инструмент в соответствии с задачей
Реализуйте структуру данных, которая может выполнять следующие две операции:
PAINT(х, у, со1) -- покрасить точку (х, у) в цвет соl
QUERY(х, у) — определить цвет точки (х, у).
Покрашенные точки могут быть красными или синими.
Изначально все точки плоскости считаются непокрашенными.
*Известно, что размер любого множества точек, в котором совпадают остатки от деления координат х на 100019, не превосходит 100.

Поясните что им *ИЗВЕСТНО ?
последнее предложение вызывает затруднение понимания.
 
 
   DES
 
201 - 11.08.18 - 19:16
а вы видели пример входящих данных? там х далеко не 100019
   NSSerg
 
202 - 11.08.18 - 19:53
(201) Это к чему?
   NSSerg
 
203 - 11.08.18 - 20:04
(201) Если вам там учиться, и уже сейчас дают задачи уровня "В"-"C", то такие задачи в любом случае придется учиться решать.
Чтоб не было непоняток с условиями, не было далеко идущих выводов из тестовых примеров, нужно просто зарегистрироваться на codeforces.ru и начать решать задачи, например начиная с тех, которые решило большее количество участников.
https://codeforces.com/problemset?order=BY_SOLVED_DESC
Практически сразу станет проще ориентироваться в подобного рода заданиях.
Значение имеют только условия. Тестовый пример в условии всегда простой, и не покрывает всех возможных случаев. Только даже если бы в примере было x=100019 - что это меняет? Условие то осталось прежним.
   kyvv
 
204 - 11.08.18 - 21:17
(200) С делением по модулю и совпадениями понял, хоть это было и не мне. Это как-то влияет на множество точек плоскости для раскраски?
   NSSerg
 
205 - 11.08.18 - 21:25
(204) Если мы формируем списки по точкам с заданным x%100019, то мы можем быть уверенны что влезем в TL.
Каждую точку мы ищем пробегаясь по списку из уже добавленных точек с фиксированным x%100019, а список не более чем из 100 точек по условию. Всего запросов максимально 10^5 из условия. Всего максимальное количество операций получается равно количество запросов помноженное на максимальное количество операций в каждом запросе, это 100 операций.
Итого 10^5*100=10^7 операций. Точно уложимся.
   NSSerg
 
206 - 11.08.18 - 21:38
(204) Это не деление по модулю, это остаток от деления.
   NSSerg
 
207 - 11.08.18 - 21:43
(206) Хотя ладно, это почти одно и то же :)
   kyvv
 
208 - 11.08.18 - 21:45
Что-то не увидел в условии, что нет множеств точек, в которых не совпадают остатки от деления координат х на 100019
   kyvv
 
209 - 11.08.18 - 21:56
(0) Что есть абитура?
   NSSerg
 
210 - 11.08.18 - 22:04
(208) "Известно, что размер любого множества точек, в котором совпадают остатки от деления координат х на 100019, не превосходит 100."
Код в (193), при каждом запросе - ищет только среди точек с совпадающим x%100019 с искомой точкой. А по условию таких точек не больше 100. Если бы их было не больше 10000, то при некоторых наборах исходных данных код бы не укладывался в таймлимит. Но их не больше 100, и это дает возможность использовать x%100019 как значение хеш функции, и гарантирует что цепочка значений не будет превышать 100 элементов.
 
 Рекламное место пустует
   kyvv
 
211 - 11.08.18 - 22:04
(205) В условии вроде бы про размер интерпретатора?
   NSSerg
 
212 - 11.08.18 - 22:05
(211) В условии, как и в любой другой задаче спортивного программирования - про ограничения на время, и на память.
   NSSerg
 
213 - 11.08.18 - 22:08
TL - таймлимит.
ML - меморилимит.
Накладывает ограничения на алгоритмы, чтоб не прошли медленные и требующие большого количества памяти решения.
Данное ограничение отсекает все решения за О(N^2), и простые решения требующие огромного числа памяти.
   kyvv
 
214 - 11.08.18 - 22:11
(212 Лимит по памяти важен. Далеко не все интерпретируемые языки смогут запустить интерпретатор в этих ограничениях. Выбирайте инструмент в соответствии с задачей. Это разве о данных? Как вы time вычисляете?
   DES
 
215 - 11.08.18 - 22:12
СПС
   NSSerg
 
216 - 11.08.18 - 22:17
(214) Есть общепринятые стандарты количества простых операций которые можно выполнить в одну секунду. Это порядка 10^7, максимум 5*10^8
Чтоб его прочувствовать самостоятельно, достаточно (203)
Как и везде там автоматическая проверка, и выводит и время вычисления, и израсходованную память, и TL или ML если превысил. То есть любой человек с достаточным опытом решения задач спортивного программирования - понимает сколько операций влезет в TL.
А чтоб проверить память - достаточно sizeof, посмотреть в диспетчере задач, либо просто уметь её вычислять.
   NSSerg
 
217 - 11.08.18 - 23:49
Яндекс проводит чемпионат  по программированию
В этой ветке немного есть про термины и суть подобных задач.
   Mort
 
218 - 12.08.18 - 00:56
Короче делаем так.

1. Берем пример одного прекрасного узкоспециализированного решения.

2. Формулируем его в задачу.

3. Т.к. без трудностей с которым пришлось столкнутся гению из (1) задача решается на раз-два, дополняем её тупыми условиями.

4. Готово! Можно запускать.

Такая херня через раз встречается на собеседованиях. Особенно если вас собеседует тот самый гений из (1). А задача - говно.
   NSSerg
 
219 - 12.08.18 - 01:46
(218) Если ты хочешь стать алгоритмистом-программистом, то должен уметь пользоваться инструментами для проверки качества решения, и уметь решать типовые задачи. Любой студент современный на прикладной математике и информатике и подобных специальностях - должен щелкать такие задачи как орешки, учитывая что она в лоб на map или hashmap решается за несколько минут.
Подобные задачи решают  и в вузах, и на собеседованиях на должности где требуется алгоритмика в любой серьезной компании. Ну и что-то мне подсказывает что они знают как выявлять способности и познания в алгоритмике.
Яндекс например проводит (217) по результатам которого приглашает на работу. На собеседованиях у них я таких задач не видел, но попросить написать реализацию хеш-таблицы они на собеседовании вполне могут.
А что не так с задачей - я в упор не понимаю. Обычная задача на алгоритмику.
   NSSerg
 
220 - 12.08.18 - 02:14
Соревнования по спортивному программированию для отбора программистов устраивают все крупные компании. Google Code Jam, Facebook Hacker Cup, Mail Code Cup (не путать с AI CUP), Яндекс Алгоритм, VK Cup  и т.д.
Им нужны специалисты с хорошей алгоритмикой. Ну и вузы по специальности "прикладная математика и информатика" готовят именно специалистов умеющих решать подобные задачи, потому что это востребовано рынком.  А в (0) несложная конечно, но хорошая алгоритмическая задача.
   Mort
 
221 - 12.08.18 - 02:37
(219) Да-да-да. Целый вагон окружения в котором ты чо-то должен. Илита. Илита по лекалам.
   Mort
 
222 - 12.08.18 - 02:38
И эти люди рассказывают про выпуск школы квадратноголовых.
   Mort
 
223 - 12.08.18 - 02:41
Бля, задача в (0) это ссылка на конкретный курс и на конкретный его параграф. Она не оставляет пространства мысли. Тупой зубреж. Я наслушался таких в акамедии, хорош.
   Mort
 
224 - 12.08.18 - 02:44
Лимит по памяти важен. Далеко не все интерпретируемые языки смогут запустить интерпретатор в этих ограничениях. Выбирайте инструмент в соответствии с задачей

Охеренное условие. А Билл говорил, что хватит 640мб. Или блин важнее решить на память а не на скорость. Чо за г-но?
   kyvv
 
225 - 12.08.18 - 09:30
(220, 223) Если я правильно понял, то такие задачи - типичные для вузовской подготовки. Ну, не дает мне покоя вопрос, а куда это тс поступает? Неужели в аспирантуру?
   NSSerg
 
226 - 12.08.18 - 09:54
(224) там условие и по времени и по памяти. Как у любой подобной задачи.
   NSSerg
 
227 - 12.08.18 - 10:01
(221) Да-да-да! Только 1Сники знают как правильно готовить программистов, и какие знания  навыки требуются гуглам-яндексам. Я бы на твоем месте предложил им свои услуги по правильному подбору персонала. Ведь тогда они и сами озолотятся, и тебя озолотят.
(223) Зубреж? Академии? Ничего что спортивные программисты выигрывают совревнования по промышленному программированию, на конкретных реальных задачах.
Ну и простой вопрос - ты на полном серьезе думаешь что олимпиадники это зубрежники? Второе название спортивного программирования - олимпиадное программирование. Олимпиады - школьные, студенческие - это соревнования именно по спортивному программированию.
   NSSerg
 
228 - 12.08.18 - 10:07
   NSSerg
 
229 - 12.08.18 - 10:11
   NSSerg
 
230 - 12.08.18 - 10:37
Если кому интересно, прямо сейчас начинается финал VC Cup 2018 проводимого "вконтакте"
http://codeforces.com/blog/entry/61156
онлайн трансляция
http://codeforces.com/spectator/contest/951/standings
Важный день! Сегодня мы узнаем победителей VK Cup 2018. Призовой фонд чемпионата как и в прошлом году связаны с круглыми числами в двоичной системе счисления:
•1 место — 1048576 рублей
•2 местo — 524288 рублей
•3 местo — 262144 рубля
•4-8 места — 131072 рубля

Планируем начинать в 10:40.
   DES
 
231 - 12.08.18 - 12:44
(225) не я, дочка. см. личку. (в ней инфа нее менялась с момента создания).

Дочка уже поступила в МФТИ, без экзаменов.
И меня терзают смутные сомнения.
Правильно ли она сделала выбор.
   NSSerg
 
232 - 12.08.18 - 13:27
(231) На прикладную математику и информатику?
А чего плохого в выборе?
   NSSerg
 
233 - 12.08.18 - 13:32
Вот у меня сын отличный выбор сделал. БВИ, выбирал из ИТМО СПБГУ, СПбАУ. Выбрал третье, так как там состав студентов намного сильнее, они брали только победителей и призеров финала вош, с других олимпиад не брали.
Так в итоге факультет после этой сессии развалился!
Они полным составом, три курса бакалавриата, включая преподавателей и спонсоров (Яндекс) перешли в ВШЭ.
Утешает то, что не вуз делает студентов, а студенты, преподаватели и спонсоры делают вуз. Так что репутация ВШЭ в прикладной математике и информатики должна вырасти, и места на icpc acm улучшится.
 
 
   DES
 
234 - 12.08.18 - 13:42
я не представляю девчонку которая так парит мозги, ну или она очень слишком более лучше крутая.
   NSSerg
 
235 - 12.08.18 - 13:54
(234) его год, прошлый год выпуска, одна из самых крутых в России - девушка.
   NSSerg
 
236 - 12.08.18 - 13:59
Дроздова Алнксандра. Чемпион России (чистое первое место), серебрянный медалист чемпионата мира среди школьников.
   NSSerg
 
237 - 12.08.18 - 14:01
Виноват, третье место в фиеале всеросса вош
http://roi2017.snarknews.info/index.cgi?data=roi/base/012487&head=index&menu=index&class=roi2017&year=2017&contest=roi
   2mugik
 
238 - 14.08.18 - 12:08
ВШЭ - высшая школа экономики?
   NSSerg
 
239 - 14.08.18 - 13:17
(238) Да. ВШЭ далеко не на последнем месте по рейтингам по ПМиИТ, и нормально выступает на ACM ICPC, но чемпионом мира ни разу не была. Ну и такого факультета в Питере не было, они в этом году будут числиться в Москве, а учиться в Питере. И есть вероятность что из-за этого в этом году в чемпионате мира участвовать не удастся.
Но по большому счету главное все-таки программа обучения и преподаватели, а они остались прежними.
Ну и есть разница получить диплом ИТМО или СПбГУ,  которые многократные чемпионы мира по программированию, или ВШЭ.
  1  2  3

Список тем форума
Рекламное место пустует  Рекламное место пустует
Прочитай, хотя бы, Митичкина "Разработка в системе 1С:Предприятие 8". Волшебник
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.
Рекламное место пустует