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

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

Метки: 

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

Я
   DES
 
10.08.18 - 06:39
тестовое задание для абитуры

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

Поясните что им *ИЗВЕСТНО ?
последнее предложение вызывает затруднение понимания.
 
  Рекламное место пустует
   0xFFFFFF
 
1 - 10.08.18 - 06:46
Ощущение корявого перевода вырванных из контекста предложений
   Лодырь
 
2 - 10.08.18 - 06:54
Обрати внимание что область координаты Х не задана.
Условие, которое ты спрашиваешь, говорит о том, что разброс точек по Х не должен превышать 100019*100
Фактически крайняя левая точка если имеет координату Хmin то крайняя правая - Хмах = Хmin+100019*100-1
   Лодырь
 
3 - 10.08.18 - 06:56
вдогонку к (2) И даже больше того, это при условии константной Y. Так же можем сказать, что больше чем 100 по оси Y быть не может.
   DES
 
4 - 10.08.18 - 07:08
(3) стало еще меньше понятно
   DES
 
5 - 10.08.18 - 07:08
они намекают на размерность матрицы?
   DES
 
6 - 10.08.18 - 07:16
Понятно что намекают на необходимость произвести контроль исходных данных типа
if (x%100019)<=100 then good else alarm

т.е. тестируют на внимательность при чтени условий задачи?
   Йохохо
 
7 - 10.08.18 - 07:20
(6) размер группы, а не Х. Х, У могут быть сколь угодно большими, но всего в множестве не больше 100019*100 точек.
   Ненавижу 1С
 
8 - 10.08.18 - 09:01
размер группы у которых координаты: x, x+100019, x+2*100019, ...
не более 100

очевидно таких групп не более 100019
   Малыш Джон
 
9 - 10.08.18 - 09:10
(0) если бы это было задание для языка низкого уровня(а то и машкода), то я бы сказал, что это условие нужно для организации разметки видеопамяти(ограничение размера блоков и общего количества)
   DES
 
10 - 10.08.18 - 09:11
а координата У любая ?
В чем смысл этого уточния задания?
 
 
   DES
 
11 - 10.08.18 - 09:12
В решении что нужно предусмотреть?
   Малыш Джон
 
12 - 10.08.18 - 09:18
Или как вариант, если для хранения множества всех точек(для ускорения определения цвета, например) используется структура данных, то размер каждого элемента - не превышает 100, т.е. хватит 1 байта.
   DES
 
13 - 10.08.18 - 09:50
В задании РЕАЛИЗОВАТЬ СТРУКТУРУ ДАННЫХ
т.е. не написать программу, нарисовать ТЗ на структуру хранения данных для указанной задачи.
Т.е., например МАССИВ струтур
где элемент структура типа:
struct screen {
byte x, y;
char colour;
};

и на этом все?
   Малыш Джон
 
14 - 10.08.18 - 09:52
(13)"Реализуйте структуру данных, которая может выполнять следующие две операции"

т.е. не просто структуру, а структуру и два метода к ней
   Chang Woo
 
15 - 10.08.18 - 09:59
(0) Это значит что зазмер Х * Y не превышает 100019 * 100
Но не обязательно что размер Х = 100019, а Y = 100, возможны любые комбинации, например размер X = 1000190, Y = 10.
Главное чтобы произведение макс.Х * макс.Y было меньше 100019 * 100
   Chang Woo
 
16 - 10.08.18 - 10:00
Короче задача не для тупых которые не могут понять даже условие.
   Chang Woo
 
17 - 10.08.18 - 10:01
И Y не может быть больше 100, тоже из этого же условия.
   kww163
 
18 - 10.08.18 - 10:06
По русски, размер множества не превышает 100, при условии.
А вот условие ))) не по русски.
   Лодырь
 
19 - 10.08.18 - 11:15
(15) А кто сказал, что множество точек - прямоугольное?
   Lama12
 
20 - 10.08.18 - 11:22
(0)ИМХО. Задача поставлена не корректно.
"...Реализуйте структуру данных, которая может выполнять следующие две операции..." Структура данных не может выполнять операции.
По последнему предложению, поддержу (7)
   Вафель
 
21 - 10.08.18 - 11:23
(13) не удобно будет искать цвет точки
нужно чтоб х, у были индексами
   DES
 
22 - 10.08.18 - 11:31
(21) это если задать матрицу размерность  охулион на охулион, тогда индексы.
А если линейный массив размерностью N - то ….
   NSSerg
 
23 - 10.08.18 - 11:32
(20) Структура данных может выполнять операции. Так как в ЯП у структур есть методы.
   DES
 
24 - 10.08.18 - 11:32
(20)т.е. по (7) уже можно сказать про размерность массива?
   NSSerg
 
25 - 10.08.18 - 11:39
+ (23) Структура данных (англ. data structure) — программная единица, позволяющая хранить и ОБРАБАТЫВАТЬ множество однотипных и/или логически связанных данных в вычислительной технике. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый НАБОР ФУНКЦИЙ, составляющих её интерфейс.
https://ru.wikipedia.org/wiki/Структура_данных
Ключевые слова выделил капсом.
   Вафель
 
26 - 10.08.18 - 11:40
На 1с  - это типо
Соотвествие[x + '_' + y] = Цвет
   mistеr
 
27 - 10.08.18 - 11:42
(15) > Это значит что зазмер Х * Y не превышает 100019 * 100

Это откуда? В (0) ни слова про ограничения на Y.

Общий смысл ограничения понятен. Есть лимит по памяти, и если хранить тупо в массиве или списке, то все точки туда не влезут. А нужно придумать что-то хитрее, чтобы влезли.
Но вот детали пока ясны...
   mistеr
 
28 - 10.08.18 - 11:44
(27) *пока не ясны*
   Вафель
 
29 - 10.08.18 - 11:52
(26) ну или бинарное дерево (индекс по 2м полям)
   NSSerg
 
30 - 10.08.18 - 12:15
(27) Ограничения не на количество значений координаты Х, а на общее количество точек!
   DES
 
31 - 10.08.18 - 12:15
там дальше в задании

В первой строке входных данных содержится число запросов п (1 < п < 105).
В каждой из следующих п строк содержатся запросы. Запросы выполняются в том порядке, в котором они встречаются во входных данных. Разные запросы могут односиться к одной и той же точке (в частности, некоторые точки могут быть перекрашенными в процессе, см. пример).
   DES
 
32 - 10.08.18 - 12:16
т.е. N меньше 10 в пятой степени
   NSSerg
 
33 - 10.08.18 - 12:16
(26) И вывалишься за ограничение.
10 миллионов значений, на каждое пара байт - это 20 мегабайт.
 
 
   DES
 
34 - 10.08.18 - 12:17
т.е. это кол-во запросов , которые есть или установить цвет точки или получить цвет точки. значить матрица можетбыть не более 100000 элементов
   NSSerg
 
35 - 10.08.18 - 12:17
(31) Если запросов 10^5, то можно делать операции добавления и удаления за lnN, уложишься в таймлимит.
Ну и вообще в условии должны быть ограничения на x и у.
   Cyberhawk
 
36 - 10.08.18 - 12:18
Поясняю: дана двумерная система координат. Кусок плоскости пикселей, в любом месте которого пиксель имеет координату Х и У.
Этот кусок плоскости должен быть таким (такой формы), что в нем будет не более ста пикселей, координата Х которых кратна 100019.
Т.е. это может быть:
- вертикальный столбик из ста пикселей: каждый пиксель будет иметь одинаковую координату Х, но разную координату У
- горизонтальный отрезок из 100019*100 пикселей и высоток один пиксель: у всех одинаковая координата У, и в нем будет сто пикселей, координата Х которых кратна тому числу 100019
- любой прямоугольный (?) участок между этими двумя "крайними формами"
   DES
 
37 - 10.08.18 - 12:18
есть только на х
   NSSerg
 
38 - 10.08.18 - 12:19
(31) Полностью задание можешь выложить?
   Вафель
 
39 - 10.08.18 - 12:20
(33) так не нужно же все хранить, только те что перекрасили
   NSSerg
 
40 - 10.08.18 - 12:20
(37) Какое? Если х и y неограниченные, то на хранение координат одной точки может уйти больше 16 мегабайт.
   Cyberhawk
 
41 - 10.08.18 - 12:20
Область вариантов скорее всего выглядит как экспонента.
Т.к. если после вертикального отрезка (высота 100 пикселей, ширина 1) увеличивать ширину, то высота сразу уменьшается пропорционально увеличению ширины
   NSSerg
 
42 - 10.08.18 - 12:21
(39) При любых начальных условиях, укладывающихся в ограничения, программа должна тратить не меньше 16 мегабайт памяти указанных в условии. Это основное условие всех подобных задач.
   NSSerg
 
43 - 10.08.18 - 12:21
Я привел вариант при котором 16 мегабайт не хватит.
   Вафель
 
44 - 10.08.18 - 12:23
эхх, далек я от олимпиадного программирования
   DES
 
45 - 10.08.18 - 12:23
   NSSerg
 
46 - 10.08.18 - 12:40
Там же написано - 0<=x,y<=10^9
   NSSerg
 
47 - 10.08.18 - 12:41
Теперь, учитывая что запросов не больше чем 10^5, то и покрашенных точек не больше этого количества.
Оптимально - использование HashMap.
   DES
 
48 - 10.08.18 - 12:49
(46) точно, еще хуже.
   Garykom
 
49 - 10.08.18 - 12:54
100 000 запросов на покраску точек, для каждого нужно сохранить еще 2 числа не более чем 1 000 000 000 и цвет R или B.
 
 
   Garykom
 
50 - 10.08.18 - 13:00
(49)+ 400 килобайт хватит на все
   Garykom
 
51 - 10.08.18 - 13:02
(50)+ сорри ошибся надо 800 килобайт
   NSSerg
 
52 - 10.08.18 - 13:04
Понятно что по памяти легко укладывается, и по производительности (С любой структурой с скоростью доступа не хуже lnN)
(50) Число до 10^9 это уже 4 байта,
две координаты это 8 байт, и один байт на хранение цвета (вообще бит, но пусть будет байт - проще организовать).
Итого 9 байт на точку, 100000 точек. Это 900000 кбайт.
Но и HashMap и Map тратят еще память на вспомогательные данные, но в 16 МБайт конечно в любом случае укладываешься.
   Garykom
 
53 - 10.08.18 - 13:06
(52) >Число до 10^9 это уже 4 байта,

неа 2^30 же хватит и еще аж 4 бита останутся для цвета с двух чисел
   Garykom
 
54 - 10.08.18 - 13:07
(52) Нахрена HashMap или Map когда обычного линейного массива хватит?

Какая разница что для определения текущего цвета точки будет цикл по 100 000 элементам массива?
   Вафель
 
55 - 10.08.18 - 13:08
(54) а ты успеешь за 1с покрасить 100тыщ точек?
   Garykom
 
56 - 10.08.18 - 13:09
(55) Не покрасить а выполнить 100 000 запросов каждый из которых или на покраску или определение цвета
   Вафель
 
57 - 10.08.18 - 13:11
(56) ну ты же не знаешь сколько и каких запросов
   Garykom
 
58 - 10.08.18 - 13:11
(56)+ Это сильно зависит от тактовой частоты и накладных расходов на выполнение в реальной системе.
   RKx
 
59 - 10.08.18 - 13:12
(55) Успею. Частота проца такая, какую я захочу:)
   Вафель
 
60 - 10.08.18 - 13:12
(58) но тем не менее, если не уложишься то твое решение не примут
   Garykom
 
61 - 10.08.18 - 13:13
(57) Там сказано ограничение на n (число запросов указанное в первой строке входных данных) 1<=n<=10^5
   Garykom
 
62 - 10.08.18 - 13:14
Самая хреновая ситуация если все 100 000 запросов на определение цвета, будет 100 000 циклов по 100 000 строк массива.

Надо бы отдельно сохранить число выполненных запросов на покраску и цикл только по ним делать при определении цвета.
   Вафель
 
63 - 10.08.18 - 13:15
(62) а для покраски разве не нужно по массиву бежить? перекраска же возможна
   Garykom
 
64 - 10.08.18 - 13:16
(63) Хехе не надо, при покраске просто в конец массива дописываем x,y,col
   Garykom
 
65 - 10.08.18 - 13:16
(64)+ При определении цвета пробегаемся по всему массиву, если координаты встретили то запоминаем цвет, повторно встретили поменяли, если ни разу то цвет N
   Вафель
 
66 - 10.08.18 - 13:16
(64) тогда для поиска тебе нужно будет каждый раз бежать до конца массива
   RKx
 
67 - 10.08.18 - 13:18
"Изначально все точки плоскости считаются непокрашенными. "
Красные в массив х, синие - в y. Оставшиеся - в z. Всегда первыми проверяем самые короткие. Если в первых двух нет - точка в третьем.
   Garykom
 
68 - 10.08.18 - 13:18
(66) Не до конца массива а до кол-ва выполненных (записанных) запросов на покраску
   Garykom
 
69 - 10.08.18 - 13:19
(67) Угу ускорение за счет большего выделения и использования памяти, у нас аж 16 мегабайт еще можно развернуться
   Garykom
 
70 - 10.08.18 - 13:19
(69)+ Намек как делить массивы дан:

"*Известно, что размер любого множества точек, в котором совпадают остатки от деления координат х на 100019, не превосходит 100"
   Garykom
 
71 - 10.08.18 - 13:20
(70)+ Как понимаем поделить координату x на 1000019 и сравнить остаток это быстро
   NSSerg
 
72 - 10.08.18 - 13:25
(54) С обычным массивом ты не укладываешься в таймлимит.
Потому что сложность алгоритма О(N^2) при N=10^5 это 10^10 операций, а успеть за секунду можно 10^7
   NSSerg
 
73 - 10.08.18 - 13:27
(58) Могу еще раз посоветовать немного порешать задач на codeforces. Будешь лучше ориентироваться в сложности.
Твое решение с поиском каждый раз по массиву не укладывается по времени в 1000 раз.
   Garykom
 
74 - 10.08.18 - 13:29
(72) С одним возможно но массивов 100 и мы ищем цвет точки только в 1
   NSSerg
 
75 - 10.08.18 - 13:29
(71) Еще раз повторюсь, можно успеть за секунду сделать 10^7 простейших операций. Если в условии 10^5 запросов, то сложность алгоритма должна быть не хуже NlnN
   Garykom
 
76 - 10.08.18 - 13:31
(75) >за секунду сделать 10^7 простейших операций

Это уже зависит от частоты процессора
   Garykom
 
77 - 10.08.18 - 13:32
(76)+ И да 10^5 меньше чем 100^7
   Garykom
 
78 - 10.08.18 - 13:32
(77) *10^5 меньше чем 10^7
   RKx
 
79 - 10.08.18 - 13:34
Данные массива:
(КоординатаИгрек, КоординатаИкс, смещение, Цвет)
Смещение - количество точек одного цвета
   NSSerg
 
80 - 10.08.18 - 13:34
(74) Ты пытаешься изобрести велосипед. Это совершенно шаблонная задача.
(76) Это простейшая задача спортивного программирования. Я кандидат в мастера (КМС) codeforces (До девальвации рейтингов был КМС-ом), ты ни разу не участвовал в спортивном программировании. Зачем ты споришь?
   RKx
 
81 - 10.08.18 - 13:34
+(79) Если один массив
   DES
 
82 - 10.08.18 - 13:35
(80) в чем состоит шаблон этого типа задач?
   NSSerg
 
83 - 10.08.18 - 13:35
(78) Тебе 10^5 раз нужно сделать операцию поиска точки в массиве. Посчитай сколько всего операций тебе нужно сделать.
   NSSerg
 
84 - 10.08.18 - 13:36
(82) Это задача добавления и чтения значений. Обычная несложная стандартная задача. Решаемая при помощи HashMap.
   Garykom
 
85 - 10.08.18 - 13:42
(83) Сделать максимум 10^5 раз в одном из 100 массивов по 1000 максимум элементов.
Еще расходы на операции по определению в каком из массивов искать.

И да ты думаешь внутри HashMap что то отличающееся от обычных массивов?
Там просто добавлены накладные расходы на перебор массива ссылок при добавлении записей, перебор всех записей (таблицы адресов) при получении значений никуда не девается ))
   NSSerg
 
86 - 10.08.18 - 13:45
(85) 10^5 раз просмотреть все элементы массива из 1000 значений. Это 10^5*1000 операций. 10^8. Вопрос - ты издеваешься? Говорю еще раз, стандарт спортивного программирования - 10^7 операций таймлимита.
   NSSerg
 
87 - 10.08.18 - 13:46
(85) Поиск в обычном массиве из 1000 элементов это 1000 операций, в HashMap - это одна операций. Я не думаю, я знаю.
   Garykom
 
88 - 10.08.18 - 13:47
(87) Хера се... Это какая то новая арифметика каких то квантовых процессоров?
   NSSerg
 
89 - 10.08.18 - 13:47
В бинарном дереве это 10 операций (Map). В хеше одна операция. Уже вторая ветка подряд где ты советуешь пургу, при этом и в первый раз не понял что дождаться ответа твоего решения невозможно. Потому что и там был N^2.
   NSSerg
 
90 - 10.08.18 - 13:50
(88) Блин. Ты что такое бинарное дерево знаешь? Понимаешь что в бинарном дереве поиск это десять операций?
https://ru.wikipedia.org/wiki/Хеш-таблица
Вот описание Хеш таблицы. Исходя из хеша вычисляется адрес (одна операция), и по этому адресу лежит значение. Это в двух словах устройство хеш-таблицы.
Если не понимаешь принцип жействия Хеш-таблиц, то можешь использовать бинарное дерево, в котором поиск не за Nопераций, а за Ln N - это "Map".
Решение на Map тоже укладывается в лимит.
   Garykom
 
91 - 10.08.18 - 13:51
(89) http://korzh.net/wp-content/uploads/2010/11/image008.gif - четкая зависимость кол-ва операция от количества объектов внутри - перебор же ))

В задаче не сказано что можно использовать готовый HashMap.

Ты предлагаешь его реализовать вручную? На чем? На массивах?

Вперед и заодно покажешь что не гонишь пургу.
   Garykom
 
92 - 10.08.18 - 13:52
(90) В бинарном дереве поиск это не 10 операций а зависит от его размера
   NSSerg
 
93 - 10.08.18 - 13:53
(92) Это 10 операция для 1000 элементов! Жесть просто. Я  тебе же пишу что это О(lnN), ты понимаешь что N - это и есть размер массива?
   Garykom
 
94 - 10.08.18 - 13:54
(93) Ты только что выше писал "в HashMap - это одна операций. Я не думаю, я знаю." соврал?
   NSSerg
 
95 - 10.08.18 - 13:55
(94) Ты понимаешь что HashMap это не бинарное дерево, в нем не О(LnN), а О(1)?
   Garykom
 
96 - 10.08.18 - 13:55
По сути я как раз и предлагаю реализовать хеш-таблицу вручную, разбив данные по нескольким массивам, не хватает 100 массивов? Сделаем 1000 или 10 000
   NSSerg
 
97 - 10.08.18 - 13:56
   Garykom
 
98 - 10.08.18 - 13:57
(97) Прикинь я это читал. И даже понимаю что мое предложение это и есть хеш-таблица, точнее некая реализация нечто похожего.
   NSSerg
 
99 - 10.08.18 - 13:58
(96) Ты изобретаешь велосипед. HashMap, Map - Это готовые структуры, которые нужно уметь использовать в спортивном программировании. А в (0) как раз задача спортивного программирования.
Еще раз Map - бинарное дерево, операции добавления, поиска выполняются за О(LnN). HashMap - хеш-таблица, операции жбавления и поиска выполняются за О(1)
   Garykom
 
100 - 10.08.18 - 14:04
"МL=16 мегабайт
Лимит по памяти важен. Далеко не все интерпретируемые языки смогут запустить интерпретатор в этих ограничениях. Выбирайте инструмент в соответствии с задачей"

Покажи мне интерпретатор имеющий на борту HashMap и работающий в этих ограничениях в 16 Mb RAM ?

  1  2  3   

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