выяснить ошибку алгоритма Uneaten Leaves

Я столкнулся с этой проблемой во время собеседования

K гусеницы едят свой путь через N листьев, каждая гусеница
падает с листа на лист в уникальной последовательности, все гусеницы запускаются
на ветке в положении 0 и падает на листья в положении между
1 и N. У каждой гусеницы j есть связанный прыжковый номер Aj.
гусеница с номером прыжка j ест листья в положениях, которые
кратный j. Это будет происходить в порядке j, 2j, 3j…. пока это
достигает конца листьев и останавливается и строит свой кокон. Дано
набор A из K элементов, мы должны определить количество
несъеденных листьев.

Ограничения:

1 <= N <= 109

1 <= К <= 15

1 <= A [i] <= 109

Формат ввода:

N = Нет несъеденных листьев.

К = количество гусениц.

A = массив целых чисел.
номера прыжков Выход:

Целое число ню. Несъеденных листьев

Пример ввода:

10
3
2
4
5

Выход:

4

Объяснение:

[2, 4, 5] — это набор из трех номеров прыжков. Все листья, кратные 2, 4 и 5, съедены. Осталось всего 4 листа с номерами 1,3,7,9.

Наивный подход к решению этого вопроса есть логический массив всех N чисел, итерации по каждой гусенице и запоминание съеденных им листьев.

int uneatenusingNaive(int N, vector<int> A)
{
int eaten = 0;
vector<bool>seen(N+1, false);
for (int i = 0; i < A.size(); i++)
{
long Ai = A[i];
long j = A[i];
while (j <= N && j>0)
{
if (!seen[j])
{
seen[j] = true;
eaten++;
}
j += Ai;
}
}
return N - eaten;
}

этот подход прошел 8 из 10 тестовых случаев и дает неправильный ответ для 2 случаев.

другой подход с использованием Принцип исключения, объяснение этому можно найти Вот а также Вот
ниже мой код для второго подхода

 int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a%b);
}
int lcm(int i, int j)
{
return i*j / gcd(i, j);
}

vector<vector<int>> mixStr(vector<vector<int>> & mix, vector<int>& A, unordered_map<int, int> & maxStart)
{
vector<vector<int>> res;
if (mix.size() == 0)
{
for (int i = 0; i < A.size(); i++)
{
vector<int> tmp;
tmp.push_back(A[i]);
res.push_back(tmp);
}
return res;
}for (int i = 0; i<mix.size(); i++)
{
int currSlotSize = mix[i].size();
int currSlotMax = mix[i][currSlotSize - 1];

for (int j = maxStart[currSlotMax]; j < A.size(); j++)
{
vector<int> tmp(mix[i]);
tmp.push_back(A[j]);
res.push_back(tmp);
}
}
return res;
}
int uneatenLeavs(int N, int k, vector<int> A)
{
int i = 0;
vector<vector<int>> mix;
bool sign = true;
int res = N;
sort(A.begin(), A.end());
unordered_map<int,int> maxStart;
for (int i = 0; i < A.size(); i++)
{
maxStart[A[i]] = i + 1;
}
int eaten = 0;while (mix.size() != 1)
{

mix = mixStr(mix, A, maxStart);
for (int j = 0; j < mix.size(); j++)
{
int _lcm = mix[j][0];
for (int s = 1; s < mix[j].size(); s++)
{
_lcm = lcm(mix[j][s], _lcm);
}
if (sign)
{
res -= N / _lcm;
}
else
{
res += N / _lcm;
}
}
sign = !sign;
i++;
}
return res;
}

этот подход прошел только один 1/10 тест. а для остальных тестовых случаев превышено ограничение по времени и неправильный ответ.

Вопрос:
Чего мне не хватает в первом или втором подходе, чтобы быть на 100% правильным.

3

Решение

Использование теоремы «Включение-исключение» является правильным подходом, однако ваша реализация кажется слишком медленной. Мы можем использовать технику битовой маскировки, чтобы получить О (К * 2 ^ К) сложность времени.

Взгляните на это:

long result = 0;

for(int i = 1; i < 1 << K; i++){
long lcm = 1;
for(int j = 0; j < K; j++)
if(((1<<j) & i) != 0) //if bit j is set, compute new LCM after including A[j]
lcm *= A[j]/gcd(lcm, A[j]);
if(number of bit set in i is odd)
result += N/lcm;
else
result -= N/lcm;
}

Для вашего первого подхода, O (N * К) Алгоритм сложности времени, с N = 10 ^ 9 и K = 15, он будет слишком медленным и может привести к превышению лимита памяти / превышению лимита времени.

Заметить, что lcm может быть больше, чем N, поэтому необходима дополнительная проверка.

3

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector