Динамическое программирование. Спичечная модель

[agul]

Хотелось бы задачку посложнее и интереснее)

Перенесите в блог «Алгоритмы» или «Спортивное программирование».

[zaitsevyan]

еще кармы нету, это мой первый топик

[Laytlas]

Хотите задачку посложнее? Задаю.
У нас есть N-мерное пространство. На сколько подпространств оно разобьется, если провести K (N-1)-мерных непараллельных пространств?
К примеру, для прямой N = 2, K точек разбивают её на K + 1 часть.
Задача достаточно распространённая, так что не лезьте в интернет. Хотя, честно говоря, строгого обощения решения этой задачи на N-мерное пространство и я не знаю, но по образу и подобию случаев для N = 1, 2, 3 можно догадаться.
P.S. Да, формула есть, но она на столь очевидна, как предыдущая.

[Mrrl]

Это, должно быть, 1+C(K,1)+C(K,2)+...+C(K,N)?
В Интернете не искал, считал в уме.

[Mrrl]

P.S. А я думал, для прямой N=1…

[zaitsevyan]

что-то я раз 5 перечитал условие, но не понял его до конца:
проводить K N-1-мерных пространств можно по разному, в задаче нужно указать на какое наибольшее количество подпространств оно разобьется? если минимум = это значит они будут параллельны, но это указано в условии.
простейший пример:
N — некая двухмерная плоскость
N-1 — линия
1-а линия — 2 подпространства
2-е линии — 3(паралельно) — 4(пересечение) подпространства
3-и линии — 4(паралельно) — 6(пересечение в 1 точке) — 7(пересечение в 3 разных точках) подпространства
и т.д.

[zaitsevyan]

и я думаю, что максимум будет достигаться когда все (N-1)-мерные пространства будут пересекаться каждый с каждым и в тоже время в одном месте не будет одновременно пересечения больше 2 пространств

[Mrrl]

Почти правильно. Любые N подпространств должны иметь ровно одну общую точку, и при этом никакие N+1 подпространства общей точки иметь не могут. Если N<K — то пересечение всех подпространств должно быть непустым и иметь размерность K-N. В этом случае (называется «в общем положении») число частей будет максимальным.

[zaitsevyan]

и еще, не знаешь где эту задачу можно найти на неком портале что бы попробовать сдать? или найти тесты к ней, так как я своим решениям без проверки не доверяю :)

[Mrrl]

Я не знаю. Когда-то предлагал задачу про разбиение гиперкуба (она сложнее, т.к. область разбиения ограничена), судьбу ее не знаю. Вероятно, пошла на какой-то Гран При Москвы, но где их теперь можно найти, не представляю. Чукча не решатель, чукча писатель :p

[mixrin]

aichallenge.org/

Вот вполне себе задачка на пару месяцев ;)

[Mrrl]

Более или менее первая попавшаяся эвристика выглядит так:

        static int NCube(int n) {
            int c1=(int)(Math.Pow(n,1.0/3)+0.5);
            int c2=(int)(Math.Sqrt(n/c1)+0.5);
            int c3=n/(c1*c2);
            int S=3*c1*c2*c3+2*(c1*c2+c1*c3+c2*c3)+(c1+c2+c3);
            int h=n-c1*c2*c3;
            if(h!=0) {
                int d1=(int)(Math.Sqrt(h)+0.5);
                if(d1*d1>h) d1--;
                int d2=h/d1;
                S+=3*d1*d2+2*(d1+d2)+1;
                h-=d1*d2;
                if(h!=0) S+=3*h+2;
            }
            return S;
        }

Интересно, когда она в первый раз ошибется.

[zaitsevyan]

в принципе, ты написал как раз формулу для 3D случая с учетом корректировок, c1 — количество полных кубов, с2 — количество полных квадратов с корректировкой и т.д.

[Mrrl]

Да, но ответ сильно зависит от конфигурации — сколько в модели внутренних ребер и внутренних вершин. Чем их больше, тем меньше спичек в модели. Поэтому задача эвристики — угадать, как надо строить модель: сколько полных двумерных рядов и какого они размера, сколько одномерных рядов и какой они длины, сколько кубиков осталось в неполном одномерном ряду. Если не угадает, то ответ может оказаться неправильным.

[alexeygrigorev]

Спасибо, люблю подобный материал по спортивному программированию.