Comments 49
Линейное решение тоже может быть быстрым.
Сначала подумал: да ерунда, ровные ступеньки под прямой. Через секунду понял, что не прав... Да, классная ловушка для любителей математики, на досуге подумаю сам, потом посмотрю ваше решение. Спасибо за хорошую задачку!
Фактически нам надо посчитать количество целочисленных точек для (n1*c1, n2*c2), где n1,n2 E Integer, внутри прямоугольного треугольника. Как мне кажется можно чисто из геометрических соображений, попробовать решить следующим образом. Рекурсивно бить на прямоугольник лежащий внутри треугольника на целочисленных координатах (0,0) - (x1*cost1, y1*cost2), и два новых прямоугольных треугольника ((x1+1)*cost1, 0) и (0, (y1 + 1)*cost2). Для двух новых треугольников спускаемся рекурсивно вниз. Но докрутить до рабочего решения по быстрому с наскоку не получилось, хотя кажется идея рабочая.
PS: хотя да, косяк, асимптота будет линейная 2^log2(N)
Под эталонным решением наверное имеется в виду не
O(min(cost1, cost2))
А O(total / max(cost1, cost2))?
Да, вы правы, самое простое решение будет действительно за O(total / max(cost1, cost2)). Перепутал с другим решением.
Исправил текст.
Но вообще, есть решение и за O(min(cost1, cost2)): можно перебрать значение x%B. После чего уравнение упрощается до x'A+y <= C', откуда можно подсчитать обычную арифметическую прогрессию, перебирая все возможные y.
Но, в общем-то, оба этих решения линейны по максимуму: Если ограничить все входные числа неким N, то обе этих оценки будут O(N) в худшем случае.
Пока не понял решение через min, но выбрав минимум из total/max и min, уже уменьшили сложность до корня :)
Отличная идея! Но логарифм, все-равно круче!
А решение за минимум вот такое:
Считаем решения Ax+By <= C. Переберем x%B: x = x'*B+i. Подставим в неравенство и упрастим: B(Ax'+y) <= C-iA. Теперь для фиксированного y существует ровно floor((C-iA)/B)-y решений. Просуммируем по всем y — это будет просто арифметическая прогрессия за O(1). Ну, еще аккуратно с отрицательными числами еще надо границы перебора i подобрать. В итоге один цикл по i до B.
Не упростит ли решение переход от решения диофантова неравенства к решению равенства?
Когда мы решаем ax + by < c - это число точек в прямоугольном треугольнике. Давайте достроим его до прямоугольника. Число точек в прямоугольнике найти легко, а с другой стороны оно = дважды число точек в треугольнике минус число точек на гипотенузе этого треугольника (они были учтены дважды). То есть достаточно найти число решений диофантова равенства ax + by = c.
Давайте достроим его до прямоугольника.
Тут проблема в том, что треугольник может иметь не целые вершины. Например, при 5x+7y=100. Эта прямая отсекается осями координат в каких-то рациональных точках.
А если такой треугольник достраивать до прямоугольника, то там не будет симметрии.
Вот если верширны целые (когда C делится на A и на B), то есть много способов. Например, через формулу Пика для площади.
В качестве идеи: например, b = 3, а = 2. Total = 20. Считаем черные точки. На синих линиях количество этих точек - сумма арифметической прогрессии. На красных - тоже. Синих линий всего floor(total/b) + 1, красных - floor(total/a) - floor(total/b). Остальное вроде понятно. Выглядит подозрительно просто, может я где ошибся?
У вас картинка — очень частный случай. Вершины треугольнка в целых точках. В общем случае это не так. Например, цены 7, 13, бюджет — 20. Зеленая линия тут не будет проходить через целые точки на осях.
А в этом случае длины красных линий будут менятся на нецелое количество "шагов". Соответственно, у вас получится там похожая на SumFloor сумма округленной арифметической прогрессии (Только еще и начало будет не с 0, а с произвольной точки. Но это тоже можно считать, сведя его к разности двух SumFloor).
А вот этот частный случай действительно легко считается. Или можно до прямоугольника достроить, как mentin предложил, или через формулу Пика площади многоугольника на целых вершинах. Надо только через GCD найти количество точек на зеленой прямой.
Edit: поздно заметил, что у вас на картинке только одна точка целая. Это действительно шаг впередНо этот случай тоже можно обработать. Плохой случай, когда обе вершины нецелые. И еще, под "целыми" точками, я имел ввиду черные.
Edit2: Осознал! Ваша картинка работает, потому что 20 делиться на 1=3-2 (цены товаров). Именно поэтому все красные линии имеют целую длину в шагах. В общем случае это не так.
Зеленая линия тут не будет проходить через целые точки на осях
Под "целыми точками" вы подразумеваете черные кругляшки, которые считаем?
Если в моем рисунке взять бюджет не 20, а 19, то зеленая линия тоже не проходит через них на обеих осях, тем не менее по прежнему имеются арифметические прогрессии. На синих это всегда (1+2+3+...), на красных в данном случае, при total==19, будет (2+4+6+8+...). Красная прогрессия зависит от, но, кажется, нулевой элемент и шаг можно вычислить.
Эта неоднозначность разрешается первым же примером входных-выходных данных в условии задачи. Решение от этого, кстати, принципиально не меняется. И в целом, условие - это компромисс.
total = 20
cost1 = 5
cost2 = 10
x1 = 0
n1 = total
i1 = total // max(cost1, cost2)
while i1 > 0:
x1 += (n1 - max(cost1, cost2)) // min(cost1, cost2)
n1 -= max(cost1, cost2)
i1 -= 1
print(1 + total // cost1 + total // cost2 + x1)Получилось как-то так.
Автор чуть исказил условия, но с этим надо определиться четко, сколько комбинаций когда обе покупки присутствуют.
" Надо подсчитать, сколько всего существует различных способов купить сколько-то этих двух товаров, не выходя из бюджета (значение имеет только общее количество покупок, а не порядок). "
Т.е. обязательно должна быть пара товаров, а не 0 товаров какого то типа, следует из условий.
Соответственно Total - A - B = получаем свободный остаток C.
Потом С / A = C1, затем С / B = C2.
Потом соответственно комбинаторика обычная, количество комбинаций X = С1 * С2
И потом прибавить 2 это в одном случае когда Первая покупка = 1 и Вторая покупка = 1
Единственное с комбинаторикой надо проверить мог ошибиться и X = (C1+1) * (С2+1)
Ну вы бы хоть на примере из условия свое решение прогнали.
Ваше решение вообще не работает, потому что остаток C делится между и покупками первого и второго товара. Поэтому нельзя просто брать "комбинацию" любое количество из С1 и любое из С2. Взяв сколько-то товаров первого типа (x <= C1), у вас остается остаток C-A*x, что меньше С2.
если считать что 0 товаров возможно, получается целочисленное деление.
С1 = 20 / 5 = 4 и С2 = 20 / 2 = 2, и соответственно получается X = 4 * 2 = 8
и как я написал будет C1 = 5 / 5 = 1, C2 = 5 / 10 = 0, но второй множитель 0, и соответственно число комбинаций 2 * 1 + 2 = 4
Нет, тут вы считатете, что 0 товаров невозможно. Чтобы считать с 0, вам надо сделать +1 везде, ведь можно брать от 0 до 4 первого товара (5 вариантов) или от 0 до 2 второго (3 варианта). В итоге получается (4+1)*(2+1) = 15. А правильный ответ 9. Если же считать без нуля товаров (4*2), то получается, что надо обязательно брать каждый товар хотя бы по разу, а значит там всего 2 варианта (5+10 и 5+5+10), а вы насчитали 8.
правильный 8мь, 9ть если только 0 1го товара и 0 2го товара, а так всего 2 получается
чтобы считать комбинаторику уточните все же 0 возможен или нет. если нет то получает 2*1 = 2 варианта если 0 возможен то 2*4 = 8 мь вариантов
считается элементарно C1 = 20 / 5 и С2 = 20 / 10, если 0 возможен, т.е. 4 * 2 = 8
второй вариант остаток от вычитания C - A - B = 20 - 5 - 10 = 5
соответственно C1 = (20 - 15) / 5 = 1 и С2 = (20 - 15) / 10 = 0, т.е. (1+1) * (0 + 1) = 2, почему прибавляем по 1 это самые первые варинты когда и и первый и второй товар в единичном экземпляре
Ох, у вас все так напутанно!
Давайте другой тест рассмотрим, а то в этом так совпало, что ваш неправильный ответ на неправильную задачу отличается от искомого ответа всего на 1, и вы, не формализуя и не доказывая ничего, просто списали эту единицу на вариант {0, 0}.
Вот, например, цены 3 и 5, а бюджет 13. Тут есть 10 вариантов: {0, 3, 3+3, 3+3+3, 3+3+3+3, 5, 5+3, 5+3+3, 5+5, 5+5+3}. Ваша первая формула дает C=13-3-5=5, C1=5/3 = 1, C2 = 5/5 = 1. В итоге (C1+1)*(C2+1)=4. Даже близко не 10.
Если же, как вы в конце сделали, не вычитать 3 и 5 из 13, а взять 13 сразу, то будет: C1=13/3 = 4, C2=13/5=2, (4+1)*(2+1)=15. Тоже вообще не 10. Или если +1 в скобках не прибавлять, то будет 4*2=8 — все равно не 10.
И даже если {0,0} не рассматривать, то нужно получить 9, а оно никак из ваших формул не вылезает.
извините если каждый товар должен присутствовать единожды, откуда вы 0 выводите, т.е. нельзя покупать один товар, их должно быть 2, хотя бы 1 первый и хотя бы 1 второй.
Так, тогда остется 3 варианта {5+3, 5+3+3, 5+5+3} Из ваших формул 3 никак нигде не получается.
я может в формулах чуть ошибся был в туалете и мельком решал задачу, но она решается комбинаторикой.
Нет. Вообще нет. Еще раз: перемножая какие-то два числа, вы считаете, что вы можете брать какое-то количество первого товара и какое-то количество второго товара независимо. Но у вас один кошелек, из которого вы платите за оба товара. Взяв сколько-то первого товара, вы уменьшаете оставшиеся деньги на второй товар. Вот так перемножать можно было бы, если бы у вас было 2 разных бюджета на каждый товар по отдельности.
Очень интересная и полезная (как минимум для меня) статья. Большое спасибо за пищу для размышлений ?
Если существует аналитическое решение для суммы конечного ряда остатков от деления, то я, скорее всего, смогу предложить решение представленной задачи за О(1).
Нормализуем значения относительно цены более дешевого из товаров:
n = total / min(cost1, cost2)
c1 = 1
c2 = max(cost1, cost2) / min(cost1, cost2)
Решение задачи с total = n, cost1 = c1, cost2 = c2 эквивалентно решению исходной задачи.
Разобъем множество всех комбинаций товаров, удовлетворяющих условию задачи, следующим образом: сначала рассмотрим все комбинации, которые дают сумму, лежащую на полуинтервале (n-1;n], затем (n-2;n-1], затем (n-3;n-2] и т.д. (n-k;n-k+1] пока n-k+1 >= c1 (т.е. n-k+1 >= 1). Объединение всех этих комбинаций плюс пустая комбинация дадут нам исходное множество. Осталось их посчитать.
Количество комбинаций, сумма товаров в которых лежит на отрезке (x-1;x], равно одной комбинации исключительно из товаров c1 плюс floor(x / c2) комбинаций, включающих товары c2. Код на Java за О(n) исключительно для проверки утверждений выше (без нормализации, т.к. ошибки округления валят тесты)
int c1 = Math.min(cost1, cost2);
int c2 = Math.max(cost1, cost2);
long sum = 1;
for (int i = total; i >= c1; i -= c1) {
sum += 1 + (long) Math.floor(((double) i) / c2);
}
return sum;Суть в том, что теперь мы можем эту сумму с округлениями вниз, которую считает цикл, представить как разнсть сумм без округлений: sum(1 + x / c2) - sum(x mod c2). Значение первой легко вычислимо за О(1), потому что существует аналитическое решение для суммы арифметической прогрессии. А вот существует ли аналитическое решение для второй суммы остатков от деления, я не знаю, к сожалению.
Итого, если кто-то знает аналитическое решение для суммы по k от 1 до n выражений ((k*a + b) mod c), буду благодарен подсказке.
Нормализуем значения относительно цены более дешевого из товаров:
Так делать нельзя. Вот были цены 3 и 7. Вы поменяли их на 1 и 2. Но оно не эквивалентно, потому что в изначальной задаче 3 вторых товара позволяли купить 7 первого. А в новой задаче — только 6.
без нормализации, т.к. ошибки округления валят тесты
Это не ошибки округления, а именно неправильность такой "нормализации". Можно сократить GCD(c1, c2), да. Но не min(c1, c2).
А так сумма модулей тоже считается за логарифм, через сумму округлений вниз из статьи. Но за O(1) формулы, похоже, нет. В модулях тоже можно выбрасывать полные круги, но там все очень нерегулярно. Эта сумма состоит из кусков арифметической прогрессии, динами total/c1, округленной то вниз, то вверх. В зависимости от того, на каком остатке начинается эта прогрессия там будет на одно слагаемое больше. При чем каждое следующее начало сдвигается на total%c влево. Возможно там тоже можно вывести рекуррентную формулу уже для шага в total%c1 и модуля c1, просто аккуратно все нарисовав на бумаге — но там очень много деталей. Я не смог. Но в любом случае, эту рекурентную формулу можно вывести через функцию SumFloor из статьи, переведя сумму модулей в сумму округлений и обратно.
Так делать нельзя. Вот были цены 3 и 7. Вы поменяли их на 1 и 2. Но оно не эквивалентно, потому что в изначальной задаче 3 вторых товара позволяли купить 7 первого. А в новой задаче — только 6.
Еще раз перечитайте формулы нормализации, что я привел, c2 и n не заявлены мной, как целые числа. На вашем примере:
cost1 = 3, cost2 = 7, total = 42
c1 = 1, c2 = 7/3, n = 42/3
Это не ошибки округления
Это именно ошибки округления, т.к. я переписывал этот код на BigDecimal с описанной нормализацией и он продолжал работать (в отличие от double), но выглядел существенно менее наглядно.
Автор, вы крут. Я зацепился за этот пост, потому что мне показалось, что так не может получиться, и вы наверняка где-то ошиблись и вылезет линия всё равно. Но нет, линия не вылезает. В итоге я два дня искал статьи по теме, и кое-что нашел.
Первое: сама проблема целиком рассматривается в этой статье: https://hal.science/hal-02049558v1/file/Triangle-1.pdf См. Theorem 2, и на 8 странице ваш трюк с делением c на GCD(a,b) с округлением вниз. Но в этой статье все равно в формуле есть линейная сумма до в худшем случае min(cost1, cost2).
Второе: нашел замечательный красивый вывод рекуррентного соотношения для случая более общего, чем у вас, но нужного для формулы из статьи: https://asfjwd.github.io/2020-04-24-floor-sum-ap/
Далее женится это довольно прямолинейно, только заменой в сумме j = floor(r/b) - i и переменой порядка суммирования на обратный мы добивается того, что под floor все коэффициенты положительны.
Код:
`
int64_t gcdEx(int64_t a, int64_t b, int64_t &x, int64_t &y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
if (b > a) return gcdEx(b, a, y, x);
int64_t xx, yy;
int64_t d = gcdEx(b, a % b, xx, yy);
y = xx - a/b*yy;
x = yy;
return d;
}
int64_t magicSum(int64_t a, int64_t b, int64_t c, int64_t n)
{
if(!a)
return (b / c) * (n + 1);
if(a >= c or b >= c)
return ( ( n * (n + 1) ) / 2) * (a / c) + (n + 1) * (b / c) +
magicSum(a % c, b % c, c, n);
int64_t m = (a * n + b) / c;
return m * n - magicSum(c, c - b - 1, a, m - 1);
}
int64_t countPoints(int64_t a, int64_t b, int64_t c)
{
if (b < a)
{
int64_t t = b;
b = a;
a = t;
}
int64_t x0, y0;
int64_t d = gcdEx(a, b, x0, y0);
a /= d;
b /= d;
c /= d;
int64_t q = c / (a * b);
int64_t r = c - q * a * b;
int64_t r_over_b_floor = r / b;
return -a * b * q * q / 2 + (a + b + 1 + 2 * c) * q / 2 + (r_over_b_floor + 1) +
magicSum(b, r - r_over_b_floor * b, a, r_over_b_floor);
}
`
Внезапно сложная задача на литкоде: Варианты покупки двух товаров