Это был бы самый обычный разбор, если бы не новая фича — спойлеры. Заценить как это круто и удобно можно уже прямо в этом посте, к каждой задаче под спойлером прикладывается код решения. Скажем спасибо MikeMirzayanov :)

Текст разбора: MikeMirzayanov, fcspartakm и GlebsHP.

637A - Voting for Photos

Автор идеи: MikeMirzayanov. Разработка: fcspartakm.

Для решения данной задачи достаточно было проитерироваться по поставленным лайкам в хронологическом порядке и в отдельном массиве поддерживать количество лайков, которые уже были поставлены фотографиям (например, в cnt[i] будет храниться количество лайков, поставленных i-й фотографии). Для нахождения ответа достаточно на каждой итерации обновлять имеющийся максимум лайков текущим значением cnt[i], и если cnt[i] > maxCnt обновлять ответ, где maxCnt — это текущее максимальное количество лайков.

Асимптотика такого решения — O(n), где n — количество поставленных лайков.

int n;
int a[N];
int cnt[M];

int main() {
    scanf("%d", &n);
    int maxCnt = 0, ans;
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        cnt[a[i]]++;
        if (cnt[a[i]] > maxCnt) {
            ans = a[i];
            maxCnt = cnt[a[i]];
        }
    }
    printf("%d", ans);
}

637B - Chat Order

Автор идеи: GlebsHP. Разработка: fcspartakm.

Для решения данной задачи нужно проитерироваться в обратном порядке по адресатам сообщений, начиная с последнего, так как верно то, что чем позднее Поликарп отправит сообщение какому-то собеседнику, тем выше этот собеседник будет в списке чатов. На каждой итерации нужно проверять, что текущий собеседник еще не был добавлен в список чатов (то есть Поликарп еще не писал ему сообщение). Это можно сделать с помощью структуры данных set. Таким образом, если текущего собеседника еще нет в списке чатов, нужно добавить имя этого собеседника в конец ответного списка чатов и добавить имя этого собеседника в set.

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

Асимптотика такого решения — O(n·log(n)), где n — количество сообщений, отправленных Поликарпом.

int n;
string a[N];
set<string>names;

int main () {
	cin >> n;
	for (int i = 0; i < n; i++) {		
		cin >> a[i];
	}	
	for (int i = n - 1; i >= 0; i--) {
		if(names.count(a[i]))
			continue;
		names.insert(a[i]);
		cout << a[i] << endl;
	}		
}

637C - Promocodes with Mistakes

Автор идеи: GlebsHP. Разработка: GlebsHP.

Для начала научимся решать задачу проверки фиксированного значения k. Правда ли, что если мы в каждом промокоде совершим не более чем k ошибок, ты мы сможем однозначно идентифицировать исходных промокод? Иначе говоря, верно ли, что для любой последовательности из шести цифр, существует не более одного промокода отличающегося от данной последовательности в k или менее позициях.

Для каждого промокода можно построить множество последовательностей отличающихся от него не более чем в k позициях, то есть шар радиуса k в данной метрике. Так, для промокода 123456 подойдут последовательности ?23456, 1?3456, 12?456, 123?56, 1234?6 и 12345? (вопросик заменяется на любую цифру). Очевидно, что некоторое k подходит, если никакие два шара радиуса k не пересекаются. Этого уже достаточно для решения задачи, просто честно перебрать значения k и проверить наличие пересечения шаров. Единственная тонкость — процесс необходимо остановить как только найдётся любая последовательность принадлежащая двум шарам.

Благодаря условию n ≤ 1000 задачу можно было решить и гораздо проще. Заметим, что два шара радиуса k пересекаются если расстояние между их центрами не превосходит 2·k. Таким образом достаточно найти пару прокодов с минимальным расстоянием между ними и выбрать максимальное подходящее k. Не забываем про случай n = 1.

int calc_dist(const string& s1, const string& s2) {
    int d = 0;
    for (int i = 0; i < (int) s1.size(); i++)
        d += (s1[i] != s2[i]);

    return d;
}

int main() {
    int n;
    cin >> n;
    vector <string> code(n);

    for (int i = 0; i < n; i++)
        cin >> code[i];

    int ans = 12;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            ans = min(ans, calc_dist(code[i], code[j]) - 1);

    cout << ans / 2 << endl;

    return 0;
}

637D - Running with Obstacles

Автор идеи: MikeMirzayanov. Разработка: fcspartakm.

В самом начале отсортируем все координаты препятствий по возрастанию. Затем воспользуемся следующим фактом: если спортсмен может преодолеть препятствие номер x и успевает разбежаться перед прыжком до препятствия номер x + 1 (то есть s ≤ a[x + 1] - a[x] - 2, где s — длина разбега перед прыжком), ему выгодно разбежаться и начать новый прыжок в точке a[x + 1] - 1.

Таким образом, для решения задачи достаточно проитерироваться по препятствиям слева направо. Пусть спортсмен преодолеть препятствие с номером i. Тогда нужно найти первое такое препятствие с номером j (правее i), что спортсмен успеет разбежаться для прыжка после препятствия j - 1 и до препятствия j. В таком случае спортсмену необходимо выполнить прыжок из точки a[i + 1] - 1 в точку a[j - 1] + 1. Если расстояние между этими точками больше чем d, значит спортсмен не сможет добраться до финиша. В противном случае нужно выполнить такой прыжок и продолжить работу программы. После преодоления всех препятствий нужно проверить нужно ли спортсмену бежать до финишной точки, или он уже находится в ней.

Асимптотика такого решения — O(n), где n — количество препятствий.

int a[N];
int n, m, s, d;
vector<pair<string, int> > ans;

int main () {
	cin >> n >> m >> s >> d;
	for(int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a, a + n);
	int curPos = 0;
	for (int i = 0; i < n; ) {
		int prev = i;
		if(a[i] - curPos - 1 >= s) {
			i++;
			while(i < n && a[i] - a[i - 1] - 2 < s)
				i++;
			int jumpDist = a[i - 1] + 1 - (a[prev] - 1);
			if (jumpDist > d) {
			    cout << "IMPOSSIBLE" << endl;
			    return 0;
			}
			ans.push_back(make_pair("RUN", a[prev] - curPos - 1));
			ans.push_back(make_pair("JUMP", jumpDist));
			curPos = a[i - 1] + 1;
		} else {
			cout << "IMPOSSIBLE" << endl;
			return 0;
		}		
	}
	if(curPos != m)
		ans.push_back(make_pair("RUN", m - curPos));
	for(int i = 0; i < (int)ans.size(); i++) {
		cout << ans[i].first << ' ' << ans[i].second << endl;
	}                  
}