P
это как выложить Online Assesment от Амазона - он есть в инете, но делать этого нельзя...
Тебе никто не навязывает участие в контесте.
Ну и никто не пытается наложить, например, штраф или посадить.
Size: a a a
2020 September 08
PO
Но вот дисквал наложить можно)
А
Число всевозможных разбиений на 2 множества = 2 ^ k. Самый простой способ понять почему: каждый элемент принадлежит либо одному множеству либо второму. 2 варианта на каждый из k элементов. Итого 2 ^ k
А вот тут есть один момент. Это так если порядок важен, то есть если для нас разбиения [1,2,3] на [1],[2,3] и [2,3],[1] - это два разных разбиения. А если нет то, число разбиений множества равно числу Стирлинга второго рода. The number of ways of partitioning a set of n elements into m nonempty sets (i.e., m set blocks), also called a Stirling set number. For example, the set {1,2,3} can be partitioned into three subsets in one way: {{1},{2},{3}}; into two subsets in three ways: {{1,2},{3}}, {{1,3},{2}}, and {{1},{2,3}}
А
Насколько я понимаю в приведенной мной задаче порядок не важен
MB
Но вот дисквал наложить можно)
Да, и это целиком и полностью находится на усмотрении авторов контеста.
MB
По идее, их решения никуда обжаловать нельзя.
MB
По идее, их решения никуда обжаловать нельзя.
Кстати интересно: может ли все-таки возникнуть ситуация, когда суду придется проверять корректность жюри?
PO
Возможно, на всероссе каком-нибудь
DY
Алексей
А вот тут есть один момент. Это так если порядок важен, то есть если для нас разбиения [1,2,3] на [1],[2,3] и [2,3],[1] - это два разных разбиения. А если нет то, число разбиений множества равно числу Стирлинга второго рода. The number of ways of partitioning a set of n elements into m nonempty sets (i.e., m set blocks), also called a Stirling set number. For example, the set {1,2,3} can be partitioned into three subsets in one way: {{1},{2},{3}}; into two subsets in three ways: {{1,2},{3}}, {{1,3},{2}}, and {{1},{2,3}}
Ты считаешь разбиение на сколько угодно множеств. Я посчитал только разбиения на 2 множества. И это уже 2^k. Число Cтиглинга растет еще быстрее, чем 2 ^ x.
IB
Кстати интересно: может ли все-таки возникнуть ситуация, когда суду придется проверять корректность жюри?
А
Ты считаешь разбиение на сколько угодно множеств. Я посчитал только разбиения на 2 множества. И это уже 2^k. Число Cтиглинга растет еще быстрее, чем 2 ^ x.
Не быстрее. Например - разбиение 3 элементов на 2 группы - Число Стирлинга - 3. Разбиение 5 элементов на 2 группы - Число Стирлинга - 15. Разбиение 10 элементов на 2 группы - Число Стирлинга - 511. Разбиение 40 элементов на 2 - Число Стирлинга 549,755,813,887
А
Проверь
А
Посчитай тоже для 2^k
А
А
Все статью читать не обязательно - Важна первая страница. Идет постановка задачи как я описал (Я надеюсь)!. А дальше идет фраза: Let n be the number of numbers, k the number of subsets, and m the maximum possible value. Problems with small n are easy since there are only k^n partitions. As n grows, the number of partitions grows as k^n, but the number of different possible values for the difference of the subset sums grows only as n·m.
А
the number of different possible values for the difference of the subset sums grows only as n·m. 😊 Эта фраза очень озадачивает меня!
2020 September 09
AT
Мне надо n разных хешей (для фильтра Блума, например). От int, к примеру. Нормально будет, если я подсолю этот int другим int-ом (всего будет n констант) и применю crc32?
AT
Имею ввиду конкатенацию