Задача 1 Попутные автомобили
Решение:
Решение простое. Нам нужно определить две переменные и отдельно считать единицы и нули. Каждый раз, когда мы встречаем единицу, мы добавляем к числу единиц количество пройденных нулей. Таким образом, мы получаем количество пропущенных пар на данный момент. Когда мы дойдем до конца массива, у нас будет полное количество пар.
В C ++ это выглядит так:
int get_pairs_passed_by(vector<int> &v) {
size_t v_size = v.size();
size_t pairs_passed_by = 0;
size_t zeroes = 0;
for(size_t i = 0; i < v_size; ++i) {
if(0 == v[i]) {
++zeroes;
}
else if(1 == v[i]) {
pairs_passed_by += zeroes;
if(pairs_passed_by > 1'000'000'000) {
return -1;
}
}
}
return pairs_passed_by;
}
Задача 2 GenomicRangeQuery
Решение:
Кажется, это единственная задача на уроке, для решения которой действительно необходимо использовать совокупные суммы, потому что нам нужно сделать много запросов к одному и тому же набору данных. Таким образом, запросы должны быть как можно более быстрыми, и время на построение дополнительной структуры данных для увеличения скорости этих запросов не так важно, потому что чем больше запросов мы сделаем, тем меньше будет время для построения дополнительных данных. В нашем случае эти дополнительные данные представляют собой массив накопленных сумм. Конечно, можно использовать хэш-таблицы или деревья, но они не бесплатны, они используют дополнительную память, нуждаются в дополнительных вычислениях для доступа к своим элементам, и большинство из них имеет непостоянную временную сложность для доступа и добавления своих элементов. Так что простого массива накопительных сумм постоянного размера более чем достаточно для этой задачи.
Какие есть накопительные (префиксные, постфиксные) суммы и как их использовать, читайте в описании урока. Вот мое решение на C ++:
vector<int> DNA_impact(const string &s, vector<int> &p,
vector<int> &q) {
enum impact_t { A = 1, C = 2, G = 3, T = 4 };
struct counters_t { int A = 0; int C = 0; int G = 0; };
size_t dna_len = s.length();
size_t p_size = p.size();
vector<int> result(p_size, 0);
vector<counters_t> cumulative_sums;
cumulative_sums.reserve(dna_len+1);
counters_t counters = counters_t();
for(size_t i = 0; i <= dna_len; ++i) {
cumulative_sums.push_back(counters);
switch (s[i]) {
case 'A': { counters.A++; break; }
case 'C': { counters.C++; break; }
case 'G': { counters.G++; break; }
}
}
for(size_t i = 0; i < p_size; ++i) {
int from = p[i], to = q[i]+1;
// If the number of A is increased throughout
// the query the it contains A
if(cumulative_sums[to].A - cumulative_sums[from].A > 0) {
result[i] = impact_t::A;
}
// the same for C and other nucleotides with higher
// impact factor
else if(cumulative_sums[to].C-cumulative_sums[from].C > 0) {
result[i] = impact_t::C;
}
else if(cumulative_sums[to].G-cumulative_sums[from].G > 0) {
result[i] = impact_t::G;
}
else {//one of the counters must be changed, so it is the T
result[i] = impact_t::T;
}
}
return result;
}
Задача 3 MinAvgTwoSlice
Решение:
Есть два гениальных решения этой задачи, и оба они намного более продвинуты, чем предполагали авторы задачи, и оба они не используют суммы Префикса.
Первое предлагаемое здесь решение https://codesays.com/2014/solution-to-min-avg-two-slice-by-codility/
Он основан на нескольких утверждениях, требующих строгого математического доказательства, поэтому я не считаю его лучшим решением. Но это так замечательно, что я должен описать это здесь.
Он основан на следующих двух утверждениях:
(1) Должно быть несколько срезов длиной два или три, имеющих минимальное среднее значение среди всех срезов.
(2) И все более длинные срезы с минимальным средним значением создаются с помощью этих 2-элементных и / или 3-элементных небольших срезов.
Сначала докажем утверждение (1). Во всем следующем обсуждении мы предполагаем, что срезы содержат два или более элемента. В каждом массиве должен быть хотя бы один срез, например S, имеющий минимальное среднее значение (MA). И ОБРАТИТЕ ВНИМАНИЕ, следующее доказательство проводится с буквой S, которая ИМЕЕТ глобальное минимальное среднее значение.
- Если длина S равна двум или трем, это следует нашему выводу.
- Если длина S нечетная, мы могли бы разделить его на 3-элементный вспомогательный фрагмент и некоторый 2-элементный вспомогательный фрагмент. Например, для слайса [1, 2, 3, 4, 5] мы могли бы получить трехэлементный суб-слайс [1, 2, 3] и двухэлементный суб-слайс [4, 5]. Или иначе мы могли бы получить [1, 2] и [3, 4, 5]. Но раскол не имеет значения в следующем доказательстве.
- Если суб-срезы имеют разные средние значения, некоторые из них будут иметь среднее значение меньше MA. Но это противоречит условию, что MA известен как глобальное минимальное среднее значение для всех срезов. Этим противоречием доказано, что все подсрезы ДОЛЖНЫ иметь одинаковое среднее значение.
- Если все субсрезы имеют одинаковое среднее значение, среднее из них должно быть MA. Таким образом, все эти суб-срезы имеют общее минимальное среднее значение и длину два или три.
- Если длина S четная, мы могли бы разделить его на некоторый двухэлементный суб-фрагмент. Для слоя [1, 2, 3, 4] единственное возможное разделение - это [1, 2] и [3, 4]. Затем, как и в предыдущем случае, все эти двухэлементные суб-срезы имеют глобальное минимальное среднее значение.
И в построении на шаге б мы уже доказали утверждение (2).
Пожалуйста, прочтите более подробную информацию по указанному выше URL.
В C ++ это решение выглядит так:
int min_avg_two_slice(vector<int> &v) {
size_t v_size = v.size();
// The minimal average of the first slice
double min_avg_value = (v[0] + v[1]) / 2.0;
// The start position of the first
// slice with minimal average
size_t min_avg_pos = 0;
for (size_t i = 0; i < v_size - 2; ++i) {
// Try the next 2-element slice
double min_avg_slice_2 = (v[i] + v[i + 1]) / 2.0;
if (min_avg_value > min_avg_slice_2) {
min_avg_value = min_avg_slice_2;
min_avg_pos = i;
}
// Try the next 3-element slice
double min_avg_slice_3 = (v[i] + v[i + 1] + v[i + 2]) / 3.0;
if (min_avg_value > min_avg_slice_3) {
min_avg_value = min_avg_slice_3;
min_avg_pos = i;
}
}
// Try the last 2-element slice
double min_avg_last_slice = (v[v_size - 2] + v[v_size - 1]) / 2.0;
if (min_avg_value > min_avg_last_slice) {
min_avg_pos = v_size - 2;
}
return min_avg_pos;
}
Этот код можно немного оптимизировать.
Вот реализация того же алгоритма, но без делений и переменных с плавающей запятой, потому что деления и операции с числами с плавающей запятой значительно медленнее, чем работа с целыми числами.
int min_avg_two_slice_optimized(vector<int> &v) {
int v_size = v.size();
if (v_size == 2) return 0;
int min_slice_2 = v[0] + v[1];
int min_slice_2_pos = 0;
int min_slice_3 = INT_MAX;
int min_slice_3_pos = 0;
for (int i = 2; i < v_size; i++) {
int slice_2 = v[i - 1] + v[i];
if (slice_2 < min_slice_2) {
min_slice_2 = slice_2;
min_slice_2_pos = i - 1;
}
int slice_3 = slice_2 + v[i - 2];
if (slice_3 < min_slice_3) {
min_slice_3 = slice_3;
min_slice_3_pos = i - 2;
}
}
int avg_min_2 = min_slice_2 * 3;
int avg_min_3 = min_slice_3 * 2;
if (avg_min_2 == avg_min_3) {
return min(min_slice_2_pos, min_slice_3_pos);
}
else {
return avg_min_2 < avg_min_3 ? min_slice_2_pos : min_slice_3_pos;
}
}
Последний и ИМХО лучший алгоритм, основанный на алгоритме Кадане, который является наилучшим теоретически возможным алгоритмом для нахождения подмассива с максимальной суммой элементов. Этот алгоритм на псевдокоде выглядит довольно просто:
maxsofar = 0 maxendinghere = 0 for i = 0 to n-1 maxendinghere = max(maxendinghere + x[i], 0) maxsofar = max(maxendinghere, maxsofar)
Мы перемещаемся по массиву и добавляем все положительные элементы в переменную maxendinghere, которая сохраняет локальный максимум, если локальный максимум оказывается больше, чем глобальный максимум, который сохраняется в maxsofar, мы сохраняем новый максимум как глобальный.
В наших случаях нам просто нужно заменить расчет максимума на расчет минимального среднего. В C ++ это выглядит так:
int min_avg_two_best(vector<int> &v) {
// keep current sum of the processed elements here
int sum = v[0] + v[1];
int v_size = v.size();
int left_index, min_left_index;
double avg_here, min_avg, avg_of_two, avg_with_prev;
// Initialize variables at the first possible slice (v[0:1]).
left_index = min_left_index = 0;
min_avg = (v[0] + v[1]) / 2.0;
// Find min average of every slice that ends at ith element,
// starting at i = 2.
for (int i = 2; i < v_size; ++i) {
sum += v[i];
// average of v[left_index : i]
avg_with_prev = ((double) sum) / (i - left_index + 1);
// average of v[i - 1 : i]
avg_of_two = (v[i - 1] + v[i]) / 2.0;
// Find minimum and update left_index of slice
// (previous left_index or i - 1).
if (avg_of_two < avg_with_prev) {
avg_here = avg_of_two;
left_index = i - 1;
sum = v[i - 1] + v[i];
}
else {
avg_here = avg_with_prev;
}
// Keep track of minimum so far and its left index.
if (avg_here < min_avg) {
min_avg = avg_here;
min_left_index = left_index;
}
}
return min_left_index;
}
Задание 4 CountDiv
Решение:
Решение этой задачи основано на простом математическом приеме: количество целых чисел в диапазоне [1..B], которые делятся на K, равно B / K. Это легко заметить, если вы попытаетесь разделить последовательность на число, например, давайте разделим 1,2,3,4,5,6,7,8,9 на 3. Вы заметите, что без остатка можно разделить только кратно 3, то есть 3,6,9. Итак, 9/3 = 3, то есть количество целых чисел, делящихся на 4 в этой последовательности.
Поэтому для решения этой задачи нам нужно найти, сколько целых чисел, делящихся на K, состоит из последовательности [1..B], затем исключить из этого числа целые числа, делящиеся на K, которые составляют последовательность [1..A-1].
Это результат = B / K - (A - 1) / K
В C ++ решение будет выглядеть так:
int count_div(int A, int B, int K) {
int b = B/K, a = 0;
if (A > 0) {
a = (A – 1) / K;
}
else {
// If A == 0 we need to count
// it in because 0 is divisible by any positive number
b++;
}
return b – a;
}
Вернитесь к оглавлению.
