тестовое задание для абитуры

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

Поясните что им *ИЗВЕСТНО ?
последнее предложение вызывает затруднение понимания.

(139) И как ты до того как получил значение этих 10^5 точек узнаешь какие из массивов лишние? Ты же вроде хочешь сразу объявить двумерный массив. Или это какие-то хитрые массивы, которым можно присваивать индекс в потоке?

Я так понял, что ты теперь понимаешь что твое решение не укладывается по памяти?

(140) Одного массива 10^5*100 разве не хватит?

(142)+ Двумерный массив 100000 на 100

(143) И какие у тебя будут исключены остатки по модулю 100019 при заведении массива?

Вот у тебя в потоке первая точка
1,100
Вторая 100019,100
//
В какой элемент массива ты запишешь первую, в какой вторую?
//
10^5*100*8 байт (две координаты, х и y, каждая по 4 байта) это 80 мегабайт.

(144) Входной поток он линейный с последовательным чтением или можно возвращаться к старым элементам но номеру?

(145) Допустим можно возвращаться.

(23) Спасибо за поправку. Век живи, век учись.

Ну вы монстры... Дочитал до сюда. Вроде понимаю о чем говорите, но блин так это далеко и давно было. И "по кусочкам"...
Вот ТС куда-то слился.

(144) Хм делаем массив 100019 х 100 и x координата задается остатком от деления, внутри храним в 100 элементах только y координату

(148)+ не влазит 40 мегабайт будет ((

(148) И как ты отличишь две разные точки, с разным x, но с одинаковым остатком от деления на 100019?

(149)+ Но если можно возвращаться (146) то хранить можно не значение y координаты а номер точки из входных данных

(150) Они рядом будут записаны в 100, их порядковым номером (151)

(151) Как, ииз какой структуры ты будешь получать номер точки?
Вот у тебя пара запросов на изменение цвкта точки, и один чтение. Тебе каждый раз после первой записи нужно точно определить "порядковый номер точки". Как ты это сделаешь? Хеш-таблицей? Map? :)

+ (153) Три раза встретилась одна и та-же точка, как ты узнаешь что это одна и та-же точка, если ты не хранишь её координату?

(154) Чем то напоминает задачку на сжатие данных, координаты у нас до 10^9 но точек всего 10^5 можно составить "словарик допустимых координат"

Ответ же нам нужен только цвет R, B или N координату не надо возвращать - их можно не хранить.

Провести при чтении некую замену координат где будет подмена порядкового номера точки встретившегося позднее на самый первый номер этой же точки (с этими же координатами).

"координаты у нас до 10^9" // Орицательные тоже могут быть. Т.е. координата по У ограничена только сверху, а по Х - только слева (больше нуля, типа). Плюс есть ограничение на размер области по высоте и ширине, описанные мною ранее

(156) 0 <= x,y <= 10^9
https://prnt.sc/kgyyos

И Я про то же. Не ясно, зачем ты это написал.

(158) Не может быть отрицательных координат x или y

(155) Ты понимаешь что элементарную задачу, которая решается начинающим программистом, джуниором - минут за 5 - ты превратил невесть в что, и до сих пор не выдал рабочего решения укладывающегося в лимиты?
Когда есть решение в ветке за О(N), на hashMap, и понятно что при N элементах в потоке - решения с лучшей асимптотикой быть не может. Так как на чтение из потока нужно О(N) операций.
(156) В условии написано: 0<=x,y<=10^9
Эта запись означает что обе координаты меньше либо равны 10^9, и обе больше либо равны нулю.

(159) (160) Это одна из двух возможных трактовок

(160) Для решения на hashMap, ты ключом что будешь делать?

Сколько будет операций при добавлении новых значений в 10^5 HashMap или получении значения оттуда?
Число 10 операций откуда взялось?

(162) 10 это двоичный логарифм от 1000. К hashmap это не имеет никакого значения. Это количество операций для поиска и добавления значения в "map" (бинарное дерево) с 1000 элементами.
//
В HashMap добавление и чтение это О(1) - константа. Одна операция.
Для добавления 10^5 значений в HashMap потребуется 10^5 (О(10^5)) операций.

(162)+ Ключ (x+y) записываем в 8 байт, еще 1 байт для цвета.
Макс элементов 10^5 итого 10^5 * 9 = 900 килобайт.

Но не учитываются накладные расходы на хранение списка ключей и списка значений, а они для 10^5 элементов будут немаленькие.
https://habr.com/post/159557/

(163) >В HashMap добавление и чтение это О(1) - константа. Одна операция.

Офигеть а за сколько времени выполняется эта одна операция в мс?

(165) Я выше приводил картинку где есть размеры коллекций и быстродействие

(166)+ http://korzh.net/2010-11-proizvoditelnost-osnovnyx-kollekcij-java-sravnenie-s-analogami-net.html

(165) Неважно. Там константа конечно больше чем в map, но не на много.
Около 10^-6 сек.
(166) И что ты понял из этой картинки? Что реализация HashMap не очень хорошая, и сложность конечно заметно меньше логарифма, но чуть хуже чем О(1)?
А хорошая реализация в LinkedHash?
Ну и что?

До 50000 элементов , а это и есть почти 10^5, как и есть в условии - скорость доступа 1микросекунда, 10^-6. Зависимость становится чуть хуже чем константа на намного больших размерах.

(164) Немаленькие это в 20 раз больше, или максимум в два раза больше? По условию у нас лимит до 15 мегабайт.
(162) Это очень странный вопрос. Конечно
typedef pair<uint, uint> Key;

Всё было описано выше. На хранение каждой точки нужно 9 байт. Итого потребуется 900 килобайт, ну и естественно плюс накладные расходы. Допустим даже в 10 раз больше. Все-равно укладываемся.
Не укладываешься - так поменяй в коде hashmap на map, делов то. Будет чуть медленней, на логарифм, но места будет занимать меньше.

(171) Угу 3 мегабайта накладных расходов примерно

(147)  +1
Почитал, как будто снова окунулся в детство.  Все это было, но блин так давно. Чувствую уже давно стал "не программистом",  совсем мозг заплыл адинэсом. )

#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef pair<unsigned int, unsigned int> Key;
struct pair_hash {
    template <class T1, class T2>
    std::size_t operator () (const pair<T1,T2> &p) const {
        auto h1 = hash<T1>{}(p.first);
        auto h2 = hash<T2>{}(p.second);
        return h1 ^ h2;  
    }
};
int main()
{
    std::ios::sync_with_stdio(false);
    unordered_map <Key,char,pair_hash> a;
    int n;
    int op;
    unsigned int x,y;
    char c;
    cin >> n;
    for(int i=0;i<n;i++) {
      cin >> op >> x >> y;
      if (op==1) { cin >> c; a[make_pair(x,y)]=c;} else
      {
      auto f=a.find(make_pair(x,y));      
      if (f==a.end()) cout << 'N'; else
        cout << f->second << "\n";
      }
    }
    cout.flush();
    return 0;
}
Вот код,
если не нравятся Хеш-таблицы, достаточно unordered_map поменять на map

виноват, косяк, забыл перевод строки, в тестовом примере ‘N’ в последней строке, поэтому глюк не заметил
auto f=a.find(make_pair(x,y));      
      if (f==a.end()) cout << 'N' << "\n"; else
        cout << f->second << "\n";

это на каком ЯП??

(176) C++
можешь проверить на любом онлайн компиляторе. Я так и проверял на тех входных данных которые на твоем скриншоте задания.
могу написать на другом ЯП. На каком надо?

(177) На 1С давай, чтоб всем понятно было )

(178) на 1с слишком просто.
только условие не выполнить, 1с не умеет читать из консольного ввода.

(176) Извиняюсь, а точно имеет смысл абитура?
Конечно ИМХО, но С++ хорошо бы знать в лицо.
Очень рекомендую.

(177) на с

(177) и еще …
в задании указаны условия, нужно ли в решения делать проверку условий или условия указаны для понимания объема данных и ресурсов

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

код на C++11, он немного ускоряет написание по сравнению с чистым C++

нужен чистый классический С

(179) 1с умеет же читать с консоли
ВвестиЧисло

(185) это не то :)
вечером, освобожусь, напишу на си
задачу можно решить без использования индексов, бинарных деревьев и хеша, на списках.
заводим массив на 100019 элементов, в который пишем ссылку  в списке на первую точку с заданным остатком от деления x на 100019.
а в списке (общем для всех точек) с каждой точкой хранится ссылка на следующую точку с таким же остатком от деления.
итого у нас на поиск каждой точки уйдет не больше 100 операций.
И в лимит по памяти легко уложились.

т.е. мы вычислили что объем массива не более 100019 ?

я не понял в чем фишка остатка от деления. что это определяет?

(187) В условии написано что таких чисел не больше ста.
У нас есть точка с координатой x,y
Если мы будем искать её в нашей структуре только среди точке с остатком отделения x на 100019 таким-же как и у текущей точки, то потратим на это не более 100 операций, потребуется перебрать не больше 100 точке.

Структуры для хранения две.
Первая - массив на 100019 элементов, по два байта на значение - ссылка на первый элемент с заданным остаток от деления в списке.
Вторая - связный список, на N+1 элементов
(максимум на 100001). Для удобства нулевой элемент использовать не будем, 0 - это будет пустая ссылка.
В котором хранятся координаты x и y (8 байт), цвет (1 байт), и ссылка на следующий номер элемента в этом массиве с таким-же остатком от деления x на 1000019 (2 байта)
Итого 100001*11+100019*2 байт, чуть больше мегабайта.
Связный список сделаем на массиве - для скорости. Чтоб не выделять память по одному элементу.

+(189) То есть мы по сути реализуем хеш-таблицу, где в качестве хеша используется остаток от деления координаты x на 100019. Как и хотел Garykom, но у него что-то не получилось :)

Виноват, все ссылки по 4 байта.

#define size 100019
#define maxN 100001
#include <stdio.h>
#include <stdlib.h>
typedef unsigned long int UINT;
typedef struct node
{
    UINT x,y,next;
    char c;
};
struct node List[maxN];
UINT Hash[size];
UINT ListN=0;
char QUERY(UINT x, UINT y)
{
    UINT p=Hash[x%size];
    while (p!=0)
    {
        struct node Node=List[p];
        if ((Node.x==x)&&(Node.y==y)) return Node.c;
        p=Node.next;
    }
    return 'N';
}

void PAINT(UINT x, UINT y, char col)
{
    UINT p=Hash[x%size];
    while (p!=0)
    {
        if ((List[p].x==x)&&(List[p].y==y))
        {
            List[p].c=col;
            return;
        }
        p=List[p].next;
    }
    List[++ListN].x=x;
    List[ListN].y=y;
    List[ListN].c=col;
    List[ListN].next=Hash[x%size];
    Hash[x%size]=ListN;
}
int main()
{
    int i;
    for (i=0; i<size; i++) Hash[i]=0;
    int n;
    scanf("%d",&n);
    UINT op,x,y;
    char c;
    for (i=0; i<n; i++)
    {
        scanf("%lu%lu%lu",&op,&x,&y);
        if (op==1)
        {
            do
            {
                scanf("%c",&c);
            }
            while ((c!='R')&&(c!='B'));
            PAINT(x,y,c);
        }
        else
            printf("%c\n",QUERY(x,y));
    }
    return 0;
}

#define size 100019
#define maxN 100001
#include <stdio.h>
#include <stdlib.h>
typedef unsigned long int UINT;
typedef struct node
{
    UINT x,y,next;
    char c;
};
struct node List[maxN];
UINT Hash[size];
UINT ListN=0;
char QUERY(UINT x, UINT y)
{
    UINT p=Hash[x%size];
    while (p!=0)
    {
        if ((List[p].x==x)&&(List[p].y==y)) return List[p].c;
        p=List[p].next;
    }
    return 'N';
}

void PAINT(UINT x, UINT y, char col)
{
    UINT p=Hash[x%size];
    while (p!=0)
    {
        if ((List[p].x==x)&&(List[p].y==y))
        {
            List[p].c=col;
            return;
        }
        p=List[p].next;
    }
    List[++ListN].x=x;
    List[ListN].y=y;
    List[ListN].c=col;
    List[ListN].next=Hash[x%size];
    Hash[x%size]=ListN;
}
int main()
{
    int i;
    for (i=0; i<size; i++) Hash[i]=0;
    int n;
    scanf("%d",&n);
    UINT op,x,y;
    char c;
    for (i=0; i<n; i++)
    {
        scanf("%lu%lu%lu",&op,&x,&y);
        if (op==1)
        {
            do
            {
                scanf("%c",&c);
            }
            while ((c!='R')&&(c!='B'));
            PAINT(x,y,c);
        }
        else
            printf("%c\n",QUERY(x,y));
    }
    return 0;
}

Так единообразней. По сути это реализация простейшей Хеш-таблицы.

В typedef struct node - typedef лишнее. Нужно писать
typedef unsigned long int UINT;
struct node
{
    UINT x,y,next;
    char c;
};
struct node List[maxN];

ТС ты не одинок, но я не поступаю :)
"Известно, что размер любого множества точек, в котором совпадают остатки от деления координат х на 100019, не превосходит 100"

...множество(из пар х и у), в котором совпадают остатки от деления координат х на const = 100019 (x1/const=xN/const). Или  хто там должЁн совпасть?

NSSerg слился, ...

Да и фиг с ней.

(196) в смысле?

(198) из ветки. Понятно, что мастера тупняки достали.

(177) на вход подаются в том числе запросы на добавление точек, с координатами (x,y)
И разных точек, но при этом с одинаковым x%100019  - не может быть больше ста.

а вы видели пример входящих данных? там х далеко не 100019

(201) Это к чему?

(201) Если вам там учиться, и уже сейчас дают задачи уровня "В"-"C", то такие задачи в любом случае придется учиться решать.
Чтоб не было непоняток с условиями, не было далеко идущих выводов из тестовых примеров, нужно просто зарегистрироваться на codeforces.ru и начать решать задачи, например начиная с тех, которые решило большее количество участников.
https://codeforces.com/problemset?order=BY_SOLVED_DESC
Практически сразу станет проще ориентироваться в подобного рода заданиях.
Значение имеют только условия. Тестовый пример в условии всегда простой, и не покрывает всех возможных случаев. Только даже если бы в примере было x=100019 - что это меняет? Условие то осталось прежним.

(200) С делением по модулю и совпадениями понял, хоть это было и не мне. Это как-то влияет на множество точек плоскости для раскраски?

(204) Если мы формируем списки по точкам с заданным x%100019, то мы можем быть уверенны что влезем в TL.
Каждую точку мы ищем пробегаясь по списку из уже добавленных точек с фиксированным x%100019, а список не более чем из 100 точек по условию. Всего запросов максимально 10^5 из условия. Всего максимальное количество операций получается равно количество запросов помноженное на максимальное количество операций в каждом запросе, это 100 операций.
Итого 10^5*100=10^7 операций. Точно уложимся.

(204) Это не деление по модулю, это остаток от деления.

(206) Хотя ладно, это почти одно и то же :)

Что-то не увидел в условии, что нет множеств точек, в которых не совпадают остатки от деления координат х на 100019

(0) Что есть абитура?

(208) "Известно, что размер любого множества точек, в котором совпадают остатки от деления координат х на 100019, не превосходит 100."
Код в (193), при каждом запросе - ищет только среди точек с совпадающим x%100019 с искомой точкой. А по условию таких точек не больше 100. Если бы их было не больше 10000, то при некоторых наборах исходных данных код бы не укладывался в таймлимит. Но их не больше 100, и это дает возможность использовать x%100019 как значение хеш функции, и гарантирует что цепочка значений не будет превышать 100 элементов.

(205) В условии вроде бы про размер интерпретатора?

(211) В условии, как и в любой другой задаче спортивного программирования - про ограничения на время, и на память.

TL - таймлимит.
ML - меморилимит.
Накладывает ограничения на алгоритмы, чтоб не прошли медленные и требующие большого количества памяти решения.
Данное ограничение отсекает все решения за О(N^2), и простые решения требующие огромного числа памяти.

(212 Лимит по памяти важен. Далеко не все интерпретируемые языки смогут запустить интерпретатор в этих ограничениях. Выбирайте инструмент в соответствии с задачей. Это разве о данных? Как вы time вычисляете?

СПС

(214) Есть общепринятые стандарты количества простых операций которые можно выполнить в одну секунду. Это порядка 10^7, максимум 5*10^8
Чтоб его прочувствовать самостоятельно, достаточно (203)
Как и везде там автоматическая проверка, и выводит и время вычисления, и израсходованную память, и TL или ML если превысил. То есть любой человек с достаточным опытом решения задач спортивного программирования - понимает сколько операций влезет в TL.
А чтоб проверить память - достаточно sizeof, посмотреть в диспетчере задач, либо просто уметь её вычислять.

Яндекс проводит чемпионат  по программированию
В этой ветке немного есть про термины и суть подобных задач.

Короче делаем так.

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

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

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

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

Такая херня через раз встречается на собеседованиях. Особенно если вас собеседует тот самый гений из (1). А задача - говно.

(218) Если ты хочешь стать алгоритмистом-программистом, то должен уметь пользоваться инструментами для проверки качества решения, и уметь решать типовые задачи. Любой студент современный на прикладной математике и информатике и подобных специальностях - должен щелкать такие задачи как орешки, учитывая что она в лоб на map или hashmap решается за несколько минут.
Подобные задачи решают  и в вузах, и на собеседованиях на должности где требуется алгоритмика в любой серьезной компании. Ну и что-то мне подсказывает что они знают как выявлять способности и познания в алгоритмике.
Яндекс например проводит (217) по результатам которого приглашает на работу. На собеседованиях у них я таких задач не видел, но попросить написать реализацию хеш-таблицы они на собеседовании вполне могут.
А что не так с задачей - я в упор не понимаю. Обычная задача на алгоритмику.

Соревнования по спортивному программированию для отбора программистов устраивают все крупные компании. Google Code Jam, Facebook Hacker Cup, Mail Code Cup (не путать с AI CUP), Яндекс Алгоритм, VK Cup  и т.д.
Им нужны специалисты с хорошей алгоритмикой. Ну и вузы по специальности "прикладная математика и информатика" готовят именно специалистов умеющих решать подобные задачи, потому что это востребовано рынком.  А в (0) несложная конечно, но хорошая алгоритмическая задача.

(219) Да-да-да. Целый вагон окружения в котором ты чо-то должен. Илита. Илита по лекалам.

И эти люди рассказывают про выпуск школы квадратноголовых.

Бля, задача в (0) это ссылка на конкретный курс и на конкретный его параграф. Она не оставляет пространства мысли. Тупой зубреж. Я наслушался таких в акамедии, хорош.

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

Охеренное условие. А Билл говорил, что хватит 640мб. Или блин важнее решить на память а не на скорость. Чо за г-но?

(220, 223) Если я правильно понял, то такие задачи - типичные для вузовской подготовки. Ну, не дает мне покоя вопрос, а куда это тс поступает? Неужели в аспирантуру?

(224) там условие и по времени и по памяти. Как у любой подобной задачи.

(221) Да-да-да! Только 1Сники знают как правильно готовить программистов, и какие знания  навыки требуются гуглам-яндексам. Я бы на твоем месте предложил им свои услуги по правильному подбору персонала. Ведь тогда они и сами озолотятся, и тебя озолотят.
(223) Зубреж? Академии? Ничего что спортивные программисты выигрывают совревнования по промышленному программированию, на конкретных реальных задачах.
Ну и простой вопрос - ты на полном серьезе думаешь что олимпиадники это зубрежники? Второе название спортивного программирования - олимпиадное программирование. Олимпиады - школьные, студенческие - это соревнования именно по спортивному программированию.

(225) И для школьной.
Вот задачи всеросса ВОШ по информатике.
https://neerc.ifmo.ru/school/archive/2017-2018.html#roi
В самом низу
https://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-roi-2018-day1.pdf
https://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-roi-2018-day2.pdf

ну и спойлер, решения
https://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-roi-2018-analysis.pdf

Если кому интересно, прямо сейчас начинается финал 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.

(225) не я, дочка. см. личку. (в ней инфа нее менялась с момента создания).

Дочка уже поступила в МФТИ, без экзаменов.
И меня терзают смутные сомнения.
Правильно ли она сделала выбор.

(231) На прикладную математику и информатику?
А чего плохого в выборе?

Вот у меня сын отличный выбор сделал. БВИ, выбирал из ИТМО СПБГУ, СПбАУ. Выбрал третье, так как там состав студентов намного сильнее, они брали только победителей и призеров финала вош, с других олимпиад не брали.
Так в итоге факультет после этой сессии развалился!
Они полным составом, три курса бакалавриата, включая преподавателей и спонсоров (Яндекс) перешли в ВШЭ.
Утешает то, что не вуз делает студентов, а студенты, преподаватели и спонсоры делают вуз. Так что репутация ВШЭ в прикладной математике и информатики должна вырасти, и места на icpc acm улучшится.

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

(234) его год, прошлый год выпуска, одна из самых крутых в России - девушка.

Дроздова Алнксандра. Чемпион России (чистое первое место), серебрянный медалист чемпионата мира среди школьников.

Виноват, третье место в фиеале всеросса вош
http://roi2017.snarknews.info/index.cgi?data=roi/base/012487&head=index&menu=index&class=roi2017&year=2017&contest=roi

ВШЭ - высшая школа экономики?

(238) Да. ВШЭ далеко не на последнем месте по рейтингам по ПМиИТ, и нормально выступает на ACM ICPC, но чемпионом мира ни разу не была. Ну и такого факультета в Питере не было, они в этом году будут числиться в Москве, а учиться в Питере. И есть вероятность что из-за этого в этом году в чемпионате мира участвовать не удастся.
Но по большому счету главное все-таки программа обучения и преподаватели, а они остались прежними.
Ну и есть разница получить диплом ИТМО или СПбГУ,  которые многократные чемпионы мира по программированию, или ВШЭ.