|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
Каков механизм экспоненциального роста объёма задачи, как прикинуть/вывести это? Шла речь о некоих нижней и верхней оценках, хотя такие не просматриваются в выложенном якобы доказательстве - что это за оценки, как их определяют?  |
|
|
| номер сообщения: 49-2-3452 |
|
|
|
|
Игорь: Есть веселая задачка, много разных версий. Идея в стиле что есть 3 кучки монет с разным количеством. На каждом шагу можно из большей кучки А в меньшую Б перекинуть некоторое количество монет, но так, чтобы число монет в Б увеличилось не более чем вдвое. Вопрос можно ли опустошить одну из кучек.
Подсказка - можно  . Главное показать стратегию как это делать. Это само по себе уже не просто. Но самое интересное после этого - я немного попарился пытаясь дать какой-то лимит минимальному количество шагов. Я так понимаю, что ни у кого ответа на это нет, а задачка любопытная. |
Может быть, я что-то недопонял в условии, но у меня ничего интересного не получается. Опустошить кучку можно только переложив все монетки из нее в соседнюю. Это немного противоречит условиям ((а) перекладывать из большей в меньшую; (б) не увеличивать количество монет более, чем вдвое), но я допустил, что можно перекладывать в равную кучку. Задача, таким образом, сделать две равных кучки. Если есть две кучки, одна поменьше размера m, другая побольше размера - M, то мы можем перекладывать из большей в меньшую пока та не дорастет до (M+m)/2. Это требует двоичного логарифма от (M+m)/2m шагов. Потенциальные проблемы с четностью ((M+m)/2 может оказаться нецелым) решаются за шаг с помощью третьей кучки. Вроде все. |
|
|
| номер сообщения: 49-2-3453 |
|
|
|
|
А если к позиции выше 4132 (16 ходов для её упорядочивания) прийти из позиции 4123 за счёт еще 2 хода, то получаем 18 ходов для упорядочивания начальной позиции 4123  , то бишь формула 2^n летит в трубу  |
|
|
| номер сообщения: 49-2-3454 |
|
|
|
|
| Хайдук, Вы бы вместо того, чтоб замусоривать тему, включили бы голову, что ли. |
|
|
| номер сообщения: 49-2-3455 |
|
|
|
|
А почему бы и не показать как включить головушку?  |
|
|
| номер сообщения: 49-2-3456 |
|
|
|
|
iourique: Игорь: Есть веселая задачка, много разных версий. Идея в стиле что есть 3 кучки монет с разным количеством. На каждом шагу можно из большей кучки А в меньшую Б перекинуть некоторое количество монет, но так, чтобы число монет в Б увеличилось не более чем вдвое. Вопрос можно ли опустошить одну из кучек.
Подсказка - можно . Главное показать стратегию как это делать. Это само по себе уже не просто. Но самое интересное после этого - я немного попарился пытаясь дать какой-то лимит минимальному количество шагов. Я так понимаю, что ни у кого ответа на это нет, а задачка любопытная. |
Может быть, я что-то недопонял в условии, но у меня ничего интересного не получается. Опустошить кучку можно только переложив все монетки из нее в соседнюю. Это немного противоречит условиям ((а) перекладывать из большей в меньшую; (б) не увеличивать количество монет более, чем вдвое), но я допустил, что можно перекладывать в равную кучку. Задача, таким образом, сделать две равных кучки. Если есть две кучки, одна поменьше размера m, другая побольше размера - M, то мы можем перекладывать из большей в меньшую пока та не дорастет до (M+m)/2. Это требует двоичного логарифма от (M+m)/2m шагов. Потенциальные проблемы с четностью ((M+m)/2 может оказаться нецелым) решаются за шаг с помощью третьей кучки. Вроде все. |
Да, я не так обьяснил. Когда держишь в голове решение не просто дать условие без подсказки.
Конечно, можно перекладывать при равном количестве. А мулька в том, что можно только увеличивать в двое. Т.е. не на любое количество, а только в 2 раза. Моя ошибка, извиняюсь.
П.С. вы тут классную тему закрутили. Я давно на нее с аппетитом посматриваю, только там везде время нужно, а его как раз совсем нет. Но я доберусь, глядишь и подкину еше чего интересного.
__________________________
ИМХО |
|
|
| номер сообщения: 49-2-3458 |
|
|
|
|
| Игорь: А мулька в том, что можно только увеличивать в двое. Т.е. не на любое количество, а только в 2 раза. |
Так гораздо интереснее :) - три дня решал. Самое обидное, что основные идеи придумались минут за 10 - все оставшееся время искал завершающий удар. Оценки по числу ходов получаются какие-то грустные - типа константа на квадрат числа камней; ясно, что почти всегда должно получаться много быстрее, но можно ли дать принципиально более пристойную оценку в общем случае, мне неясно. |
|
|
| номер сообщения: 49-2-3460 |
|
|
|
|
iourique: | Игорь: А мулька в том, что можно только увеличивать в двое. Т.е. не на любое количество, а только в 2 раза. |
Так гораздо интереснее :) - три дня решал. Самое обидное, что основные идеи придумались минут за 10 - все оставшееся время искал завершающий удар. Оценки по числу ходов получаются какие-то грустные - типа константа на квадрат числа камней; ясно, что почти всегда должно получаться много быстрее, но можно ли дать принципиально более пристойную оценку в общем случае, мне неясно. |
Признаюсь, что задачу и не решал. Так получилось, что читал условие сразу с решениеми. Поэтому должен заметить, что мне кажется что решить ее крайне трудно.
Я знаком с двумя решениями: одно я до конца не понял (и время не тратил, так как пусть потрудяться обьяснять решение понятно), другое понятное и красивое. И судя по всему лучшее. Первое тоже говорить о квадрате, второе о nlogn. Что такое n напрямую связано с решением . Вопрос что дальше делать? Ждать другие решения, закинуть мне известное?
П.С. к слову, задача из советской олимпиады. Хотя я ее узнал только на английском.
__________________________
ИМХО |
|
|
| номер сообщения: 49-2-3461 |
|
|
|
|
Да, забыл сказать, что не сомневаюсь, что nlogn завышено. В том числе в известном нне решении.
__________________________
ИМХО |
|
|
| номер сообщения: 49-2-3462 |
|
|
|
|
| Игорь: Вопрос что дальше делать? Ждать другие решения, закинуть мне известное? |
Ну не знаю. Я могу ещё подумать, но боюсь, что осилить не смогу. |
|
|
| номер сообщения: 49-2-3463 |
|
|
|
|
MikhailK: | Игорь: Вопрос что дальше делать? Ждать другие решения, закинуть мне известное? |
Ну не знаю. Я могу ещё подумать, но боюсь, что осилить не смогу. |
Задачка-то трудная. Я скажу так - есть способ показать, что после сета из logn операций в меньшей кучке останется как минимум на один меньше, чем в меньшей до этих операций. Этот "как минимум" мне и не нравится. Мне кажется что невозможно чтобы по ходу этого процесса будет часто получатся что после logn операций останется всего на один меньше. Но я не наставаю, всего лишь загадка
Я на днях собирался помучаться на эту тему, а пока больше мешать не буду
__________________________
ИМХО |
|
|
| номер сообщения: 49-2-3464 |
|
|
|
|
Мое решение после некоторых улучшений тоже дало n log n.
Общие идеи такие:
1. Начнем с ситуации, когда есть только две кучки. Если они обе четные, можно поделить на два; если обе нечетные, то через ход будут две четные и см. выше. Интересный случай - одна четная другая нечетная, скажем, a и b, общее число камней - a+b. За ход ситуация меняется так: (a,b)->(2a,b-a). Если смотреть на все по модулю a+b, можно записать изящнее: (a,b)->(2a,2b). Так как 2 и a+b взаимно просты, то операция зацикливается. Заметим, что за ход до того, как она зациклится, мы получаем (a/2,b+a/2), то есть, мы научились делить четную кучку пополам.
2. Теперь 3 кучки. Опять же, интересная ситуация - две четные кучки, одна нечетная, скажем, 2k+1, 2n, 2m, где 2m < 2n. Тогда мы можем сделать следующее:
(2n,2m,2k+1) --> (2n-2m,4m,2k+1) --(см пункт 1)-->(2n-2m,2m,2k+2m+1).
Нечетная кучка подросла, продолжаем до истощения сил. |
|
|
| номер сообщения: 49-2-3465 |
|
|
|
|
| Игорь: Ждать другие решения, закинуть мне известное? |
Закиньте, если не трудно - интересно сравнить. |
|
|
| номер сообщения: 49-2-3490 |
|
|
|
|
iourique: | Игорь: Ждать другие решения, закинуть мне известное? |
Закиньте, если не трудно - интересно сравнить. |
Ваше решение красивое, кажется они это и имели в виду. Только они таки говорят о квадрате и если честно я у Вас лог не увидел, так как Вы же не каждый раз пополам делите. Может я чего-то не понял.
Их решение поразило меня. Допустим три кучки A, B, C с размерами a<b<c. b=qa+r. Расмотрим бинарное представление q, так что самый главный бит 1 (т.е. без лишних нулей слева). Тогда сделаем следуюшие шаги: бежим по q справа налево и для каждого 0 в бинарном представлении перекидываем монетки из С в А, а для 1 из B в А. Легко проверить что все сходится и законы нигде не будут нарушены. С другой стороны в B останется после этого дела ровно r, что по определению меньше а. Т.е. как минимум на один уменьшили, при этом сделав лог шагов. Т.е. в худшем случе nlogn. Только уменьшение на 1 будет происходить если в q все нули кроме одного. К тому же n тоже что-то не очевидное. Тут надо думать, а у меня все никак не получается.
П.С. я вот сижу и тупо смотрю на пару (10,8) и думаю как поделить пополам?
__________________________
ИМХО |
|
|
| номер сообщения: 49-2-3523 |
|
|
|
|
Игорь: Только они таки говорят о квадрате и если честно я у Вас лог не увидел, так как Вы же не каждый раз пополам делите. Может я чего-то не понял.
|
Там два типа операций: одна - переход от (4n, 2k+1) к (2n, 2k+2n+1). Это занимает порядка (2n+k) шагов в худшем случае [пример: (4,7)->(3,8)->(5,6)->(1,10)->(2,9)], т.е. линейно по общему числу монет. Вторая операция - создание кучки, делящейся на 4. Это можно сделать за один шаг [(2m,2n)->(2m-2n,4n)], а можно потратить еще несколько шагов (порядка log(m+n)) и добиться того, что бы вторая кучка стала больше первой. Т.е. мы перешли от (2m,2n,2k+1) к (2p,4q,2k+1), где 4q > 2p. После следующей операции ((2p,4q,2k+1)->(2p,2q,2k+2q+1)) число монет в двух четных кучках уменьшилось как минимум на четверть, а значит всего таких итераций потребуется порядка log(m+n). Общая оценка - c S log S, где c - константа, а S - общее число монет.
| Их решение поразило меня. |
Безумное решение. Я что-то такое начал нащупывать для случая, когда одна из кучек содержит 1 монетку, но обобщить мне бы и в голову не пришло.
| П.С. я вот сижу и тупо смотрю на пару (10,8) и думаю как поделить пополам? |
(8,10)->(2,16)->(4,14). Но вообще-то речь шла о паре четный-нечетный. |
|
|
| номер сообщения: 49-2-3534 |
|
|
|
|
Да, теперь я Вашу идею понял окончательно. Мне очень понравилось.
__________________________
ИМХО |
|
|
| номер сообщения: 49-2-3535 |
|
|
|
|
| Игорь: А мулька в том, что можно только увеличивать в двое. Т.е. не на любое количество, а только в 2 раза. |
N - количество монет в большой куче
n - количество монет в малой куче
k + m = N/n k - натуральное целое число ; m - дробная част 0<m<1
p - количество перемещении
Решение:
За 1 перемещение N = n
За 2 р N = n + 1 до 3n
За 3 р N = 3n + 1 до 7n
За 4 р N = 7n + 1 до 15n
За 5 р N = 15n + 1 до 31n
За 6 р N = 31n + 1 до 63n
За 7 р N = 63n + 1 до 127n
За 8 р N = 127n + 1 до 255n
За 9 р N = 255n + 1 до 511n
За 10 р N = 511n + 1 до 1023n
За 11 р N = 1023n +1 до 2047n
За 12 р N = 2047n +1 до 4095n
За 13 р N = 4095n +1 до 8191n
 |
|
|
| номер сообщения: 49-2-3537 |
|
|
|
|
LatchezarS: | Игорь: А мулька в том, что можно только увеличивать в двое. Т.е. не на любое количество, а только в 2 раза. |
N - количество монет в большой куче
n - количество монет в малой куче
k + m = N/n k - натуральное целое число ; m - дробная част 0<m<1
p - количество перемещении
Решение:
За 1 перемещение N = n
За 2 р N = n + 1 до 3n
За 3 р N = 3n + 1 до 7n
За 4 р N = 7n + 1 до 15n
За 5 р N = 15n + 1 до 31n
За 6 р N = 31n + 1 до 63n
За 7 р N = 63n + 1 до 127n
За 8 р N = 127n + 1 до 255n
За 9 р N = 255n + 1 до 511n
За 10 р N = 511n + 1 до 1023n
За 11 р N = 1023n +1 до 2047n
За 12 р N = 2047n +1 до 4095n
За 13 р N = 4095n +1 до 8191n
|
Я знаком со степенями двойки, спасибо. Вы немного другую задачу решали, мне кажется.
__________________________
ИМХО |
|
|
| номер сообщения: 49-2-3540 |
|
|
|
|
На сайте Using your Head is Permitted опубликовали забавную, хотя вроде бы известную (но не мне) задачку. Как это водится, про узников и колпаки.
В тюрьме сидит 100 заключенных. В один прекрасный день им объявляют, что сегодня вечером, после того, как их разведут по их одиночным камерам, им выдадут по два колпака, белый и черный, а завтра с утра они должны будут надеть один из колпаков, после чего их выведут на плац и расставят в шеренгу в уже определенном начальником тюрьмы порядке. Если окажется, что цвета колпаков строго чередуются (б-ч-б-ч-.. или ч-б-ч-б...), их всех отпустят. Одновременно с раздачей колпаков каждому из них расскажут, в каком порядке будут расставлены все остальные, но не сообщат его место в шеренге. До заката у заключенных есть время посовещаться и выработать общую стратегию. Какой она должна быть? |
|
|
| номер сообщения: 49-2-3564 |
|
|
|
|
Юрик, хоть и удивительно, но я с самого начала стал думать о числе перемещений и сдвигов отдельных книг  . Недавно заострили внимание на том, что речь идёт скорее о числе n-перестановок на пути к упорядочению. Как ни странно, эта естественная идея сторонилась башки моей, а ведь практически библиотекарь стал бы сдвигать книги пачками, а не одну за другой 
Теперича мне интересен вот такой вопрос: каковы мотивация/происхождение самой идеи о степенях именно 2-ки? Лишь эти степени пересчитывают n-перестановки одну за другой, если начать с нулевой суммы и брать правую книгу. Мне кажется, что нужно увидеть аналогию с ... системами счисления и выбрать единственную среди них, пересчитывающую перестановки - двоичную  |
|
|
| номер сообщения: 49-2-3575 |
|
|
|
|
| Хайдук:Теперича мне интересен вот такой вопрос: каковы мотивация/происхождение самой идеи о степенях именно 2-ки? |
Идея нехитрая - мы ищем полуинвариант, т.е. какую-то величину, которая растет с каждым ходом и ограничена сверху. Поскольку на каждом ходу одна из книг попадает на свое место, то довольно естественно привязать полуинвариант к книгам, стоящим на своих местах. При этом, на каждом ходу, книги, стоящие правее той, что мы поставили на место, могут со своего места уйти, поэтому наш полуинвариант должен ценить любую книгу выше, чем все книги, стоящие правее нее, вместе взятые. Степени двойки - минимальная функция, обладающая таким свойством. Степени тройки сгодились бы, если бы нас интересовала только сходимость процесса, а не число ходов. А вот то, что верхняя оценка, данная полуинвариантом, реализуется конкретной перестановкой (и оказывается, таким образом, точной)- чистое везение. |
|
|
| номер сообщения: 49-2-3576 |
|
|
|
|
| номер сообщения: 49-2-3577 |
|
|
|
|
Кстати, Юрик, как Вы относитесь к потугам мнениям Дорона (Зейлбергера)? |
|
|
| номер сообщения: 49-2-3578 |
|
|
|
|
| Пребывал в неведении по поводу этого персонажа и препочел бы в нем остаться - у каждого идиота есть выход в интернет, что среднему качеству высказываемых в нем мнений ни разу не способствует. |
|
|
| номер сообщения: 49-2-3579 |
|
|
|
|
Видел выше, что в связи с последней задачкой упоминают корифея Ногу Алона, а Дорон любит щеголять ссылками на него  |
|
|
| номер сообщения: 49-2-3580 |
|
|
|
|
| номер сообщения: 49-2-3582 |
|
|
|
|
Ну ок, не идиот. К сожалению, большая часть его мнений лучше всего описывается его собственным выражением - snooty drivel. |
|
|
| номер сообщения: 49-2-3583 |
|
|
|
|
| iourique: большая часть его мнений лучше всего описывается его собственным выражением - snooty drivel. |
Я бы заменил snooty на stupid... |
|
|
| номер сообщения: 49-2-3585 |
|
|
|
|
| Юрик, почему называем сумму двоек ПОЛУинвариантом? |
|
|
| номер сообщения: 49-2-3595 |
|
|
|
|
| Уж больно тут заумные граждане собрались. Предлагаю им немного расслабиться и оценить с математической точки зрения правильность решения следующей задачки. |
|
|
| номер сообщения: 49-2-3596 |
|
|
| |
|
|
|
|
|
|
|
| Copyright chesspro.ru 2004-2024 гг. |
|
|
|
