Форум Всеукраїнської інтернет-олімпіади NetOI
На форумі обговорюються лише питання, пов'язані з олімпіадою
Ви не зайшли.
Сторінок: 1
- Список
- » Третий тур NetOI-2006
- » Обсуждение решения задачи Areaplus (только после 23:59 04.01.07)
#1 2007-01-04 20:20:54
- FireTiger
- Новий користувач
- Звідки: Донецк
- Зареєстрований: 2006-09-27
- Повідомлень: 86
Обсуждение решения задачи Areaplus (только после 23:59 04.01.07)
Здесь я предлагаю обсудить решение задачи Areaplus
Если вы собрались написать сообщение в этой теме пожалуйста прочитайте следующие правила:
1. Постить только после окончания приёма решений. (без комментариев)
2. Постите код только если вас об этом попросили. (обилие кода делает тему нечитабельной)
3. Обсуждайте только задачу, которая указана в теме.
Надеюсь эти простые правила сделают обмен мнениями более плодотворным.
Відредаговано FireTiger (2007-01-04 20:34:38)
ICQ 339203772 - Если что-нибудь срочно необходимо - стучитесь, я отвечу!
----------------
Основная проблема с программистами заключается в том, что вы никогда не можете сказать, чем они занимаются, до тех пор, пока не будет слишком поздно.
Поза форумом
#2 2007-01-05 08:42:36
- Yevgeniy
- Новий користувач
- Зареєстрований: 2006-10-14
- Повідомлень: 67
Re: Обсуждение решения задачи Areaplus (только после 23:59 04.01.07)
Ідея базу.ться на формулі влючень-виключень
"Математика -- цариця наук, арифметика -- цариця математики."
Карл Фрідріх Гаусс (1777 - 1855) - КОРОЛЬ МАТЕМАТИКІВ.
Поза форумом
#3 2007-01-05 08:46:23
Re: Обсуждение решения задачи Areaplus (только после 23:59 04.01.07)
хм... а сложность ?? O(2^N) ??
мои два решения имеют сложность О(N^3) , O(N^2 Log[S]) (S - эт разница макс и мин ординаты)
а идея решений в сведение D-мерной задачи к (D-1)-мерной за O(N)
отправил O(N^3)
Відредаговано xXx (2007-01-05 08:50:00)
icq - 402174
Поза форумом
#4 2007-01-05 08:59:08
- Yevgeniy
- Новий користувач
- Зареєстрований: 2006-10-14
- Повідомлень: 67
Re: Обсуждение решения задачи Areaplus (только после 23:59 04.01.07)
не це якщо перебирати всі варіанти, то 2^N. В умові сказано, що тільки 10 % перетинаються по три і більше, тому використавши формулу включень виключень ми отримаємо розвязок даної задачі не перебираючи усіх варіантів.
"Математика -- цариця наук, арифметика -- цариця математики."
Карл Фрідріх Гаусс (1777 - 1855) - КОРОЛЬ МАТЕМАТИКІВ.
Поза форумом
#5 2007-01-05 09:01:11
- alex_kasycky
- Олімпієць
- Зареєстрований: 2005-10-09
- Повідомлень: 92
Re: Обсуждение решения задачи Areaplus (только после 23:59 04.01.07)
Yevgeniy написав:
Ідея базу.ться на формулі влючень-виключень
В моей реализации этого метода сложность выходит примерно O(N^3+2^(N/10)) так как не больше 10%. 2^10 не много. Но слал я нормальный куб без учета этих 10%
Этот аккаунт не работает... мой новый аккаунт - alexkasycky
Поза форумом
#6 2007-01-05 09:09:59
Re: Обсуждение решения задачи Areaplus (только после 23:59 04.01.07)
alex_kasycky написав:
Yevgeniy написав:
Ідея базу.ться на формулі влючень-виключень
В моей реализации этого метода сложность выходит примерно O(N^3+2^(N/10)) так как не больше 10%. 2^10 не много. Но слал я нормальный куб без учета этих 10%
а как, если не секрет, можно добиться +2^(N/10) ?
самое быстрое что вижу эт +2^(N/10)*С(N/10,N) ...
Відредаговано xXx (2007-01-05 09:13:07)
icq - 402174
Поза форумом
#7 2007-01-05 09:13:56
- Yevgeniy
- Новий користувач
- Зареєстрований: 2006-10-14
- Повідомлень: 67
Re: Обсуждение решения задачи Areaplus (только после 23:59 04.01.07)
Яких 2^10. В ній беруться сполучення. С(n,k) = (n!/(n - k)!k!). Взявши суму, при n = 10, С(n,0) + C(n,1) + C(n,2)+...+C(n,n) = 1023. Макс. комб., що ми перебираємо.
"Математика -- цариця наук, арифметика -- цариця математики."
Карл Фрідріх Гаусс (1777 - 1855) - КОРОЛЬ МАТЕМАТИКІВ.
Поза форумом
#8 2007-01-05 09:17:17
Re: Обсуждение решения задачи Areaplus (только после 23:59 04.01.07)
Yevgeniy написав:
Яких 2^10. В ній беруться сполучення. С(n,k) = (n!/(n - k)!k!). Взявши суму, при n = 10, С(n,0) + C(n,1) + C(n,2)+...+C(n,n) = 1023. Макс. комб., що ми перебираємо.
n = 100, С(n,0) + C(n,1) + C(n,2)+...+C(n,10) разве не так?
icq - 402174
Поза форумом
#9 2007-01-05 09:21:03
- Yevgeniy
- Новий користувач
- Зареєстрований: 2006-10-14
- Повідомлень: 67
Re: Обсуждение решения задачи Areaplus (только после 23:59 04.01.07)
НЕТ. n - це кількість тих, що перетинаються по три і більше. По умові - це 10% від загальної кількості, тому 1<= n <= 10
"Математика -- цариця наук, арифметика -- цариця математики."
Карл Фрідріх Гаусс (1777 - 1855) - КОРОЛЬ МАТЕМАТИКІВ.
Поза форумом
#11 2007-01-05 09:24:26
- Yevgeniy
- Новий користувач
- Зареєстрований: 2006-10-14
- Повідомлень: 67
Re: Обсуждение решения задачи Areaplus (только после 23:59 04.01.07)
Загальна складність в найгіршому випадку O(n*n + n *n/2 * (n/2) + 1024)
"Математика -- цариця наук, арифметика -- цариця математики."
Карл Фрідріх Гаусс (1777 - 1855) - КОРОЛЬ МАТЕМАТИКІВ.
Поза форумом
#12 2007-01-05 09:26:42
- Yevgeniy
- Новий користувач
- Зареєстрований: 2006-10-14
- Повідомлень: 67
Re: Обсуждение решения задачи Areaplus (только после 23:59 04.01.07)
Да але нам не потрібно всі, нам потрібно спочатку визначити, які коробки перетинаються по три, що легко зробити (по умові їх не більше 10%) і далі перебор.
"Математика -- цариця наук, арифметика -- цариця математики."
Карл Фрідріх Гаусс (1777 - 1855) - КОРОЛЬ МАТЕМАТИКІВ.
Поза форумом
#14 2007-01-05 09:30:09
Re: Обсуждение решения задачи Areaplus (только после 23:59 04.01.07)
Yevgeniy написав:
Да але нам не потрібно всі, нам потрібно спочатку визначити, які коробки перетинаються по три, що легко зробити (по умові їх не більше 10%) і далі перебор.
а.... а вот теперь всё ясно....
icq - 402174
Поза форумом
#15 2007-01-05 09:30:22
- alex_kasycky
- Олімпієць
- Зареєстрований: 2005-10-09
- Повідомлень: 92
Re: Обсуждение решения задачи Areaplus (только после 23:59 04.01.07)
Yevgeniy написав:
Яких 2^10. В ній беруться сполучення. С(n,k) = (n!/(n - k)!k!). Взявши суму, при n = 10, С(n,0) + C(n,1) + C(n,2)+...+C(n,n) = 1023. Макс. комб., що ми перебираємо.
С(n,0) + C(n,1) + C(n,2)+...+C(n,n) = 2^n (Бином Ньютона)
Но! Єто первый(не нулевой, а первый) С из 100, второй из 100, а третий уже нет! можно делать в тупую тоесть без эвристик. Когда третий тоже из ста - тогда куб, дальше все кто в тройных не участвовали откинутся. Это и есть моя реализация.
Этот аккаунт не работает... мой новый аккаунт - alexkasycky
Поза форумом
#16 2007-01-05 09:49:38
- Yevgeniy
- Новий користувач
- Зареєстрований: 2006-10-14
- Повідомлень: 67
Re: Обсуждение решения задачи Areaplus (только после 23:59 04.01.07)
alex_kasycky написав:
Yevgeniy написав:
Яких 2^10. В ній беруться сполучення. С(n,k) = (n!/(n - k)!k!). Взявши суму, при n = 10, С(n,0) + C(n,1) + C(n,2)+...+C(n,n) = 1023. Макс. комб., що ми перебираємо.
С(n,0) + C(n,1) + C(n,2)+...+C(n,n) = 2^n (Бином Ньютона)
Но! Єто первый(не нулевой, а первый) С из 100, второй из 100, а третий уже нет! можно делать в тупую тоесть без эвристик. Когда третий тоже из ста - тогда куб, дальше все кто в тройных не участвовали откинутся. Это и есть моя реализация.
1<=n<=10. 1<=N<=100
"Математика -- цариця наук, арифметика -- цариця математики."
Карл Фрідріх Гаусс (1777 - 1855) - КОРОЛЬ МАТЕМАТИКІВ.
Поза форумом
#17 2007-01-05 10:19:33
- Yevgeniy
- Новий користувач
- Зареєстрований: 2006-10-14
- Повідомлень: 67
Re: Обсуждение решения задачи Areaplus (только после 23:59 04.01.07)
Ось декілька тестів
4
1 3 0 7 10 1
6 7 0 8 12 1
7 1 0 11 9 1
5 0 0 8 8 1
86
7
1 3 0 7 10 10
6 7 0 8 12 10
7 1 0 11 9 10
5 0 0 8 8 10
2 6 0 6 9 10
5 0 0 9 11 10
6 0 1 12 4 5
924
3
8 8 10 3 3 0
5 1 0 9 6 10
12 11 0 6 5 10
650
9
-2 -1 -10 2 -6 10
1 -2 10 4 2 -10
-1 -2 -10 -4 2 10
-4 -9 10 -1 -5 -10
1 -5 10 4 -9 -10
-4 -1 -10 -1 -6 10
1 -1 -10 4 -6 10
-2 -9 -10 2 -5 10
-2 2 10 2 -2 -10
1760
"Математика -- цариця наук, арифметика -- цариця математики."
Карл Фрідріх Гаусс (1777 - 1855) - КОРОЛЬ МАТЕМАТИКІВ.
Поза форумом
#18 2007-01-05 10:54:35
- FireTiger
- Новий користувач
- Звідки: Донецк
- Зареєстрований: 2006-09-27
- Повідомлень: 86
Re: Обсуждение решения задачи Areaplus (только после 23:59 04.01.07)
Сошлось
ICQ 339203772 - Если что-нибудь срочно необходимо - стучитесь, я отвечу!
----------------
Основная проблема с программистами заключается в том, что вы никогда не можете сказать, чем они занимаются, до тех пор, пока не будет слишком поздно.
Поза форумом
#19 2007-01-05 11:03:02
Re: Обсуждение решения задачи Areaplus (только после 23:59 04.01.07)
тест для тех, кто писал O(N^3) и меньше....
100 1 -3 3 1 -2 3 3 3 -1 -1 0 -2 5 -2 -1 0 2 0 -2 0 0 1 -1 -1 0 3 2 5 -3 4 -1 2 0 0 0 -4 5 -1 -2 0 -1 -4 -3 -2 -1 5 -3 3 2 -3 0 -2 0 3 1 3 2 4 -1 -5 2 2 2 -3 -5 -1 -1 3 0 4 0 -3 3 2 0 -1 4 -1 2 -2 -1 -2 0 3 0 -2 0 2 -1 -1 2 -3 5 3 1 2 2 4 -1 1 0 -3 1 -2 -1 0 -1 -2 -1 -1 -3 3 3 4 -1 1 -3 -2 -3 -1 0 1 3 -3 0 3 -2 4 -1 -2 3 0 -3 0 -4 -2 2 -4 -1 -1 -2 1 -4 1 3 4 4 0 -1 1 1 0 -3 -4 4 0 -5 0 -3 0 -1 -5 -1 -5 -4 3 -3 2 2 2 2 -1 0 2 4 -2 -1 -4 3 -2 -5 2 4 -1 -1 -1 -5 -1 0 -3 2 -1 1 -3 2 2 1 -5 -3 -2 1 -2 3 2 -1 5 3 1 -4 0 1 -1 3 -3 0 -4 1 1 2 0 1 2 1 4 4 1 -3 -1 -1 3 2 4 1 -1 -2 0 -2 -2 0 2 0 2 4 4 0 2 4 0 2 2 -1 2 0 -5 -4 -4 2 1 -2 0 1 2 3 -2 -2 -1 2 1 -5 -1 -2 0 -4 -2 1 1 -4 0 3 1 1 5 0 -2 1 -4 -2 0 0 -4 0 -3 1 4 1 1 2 -2 1 1 -3 2 -1 -1 1 -2 -1 -1 1 1 2 -4 3 2 -5 -1 2 0 -2 1 -3 4 3 0 1 4 -3 -1 -5 3 -2 4 2 3 0 -2 -1 0 -1 2 0 -1 2 -5 -1 0 4 0 -3 -1 -3 0 4 1 -5 2 -3 -2 -1 1 -1 0 1 4 -1 0 1 -1 1 0 -1 -4 -1 3 -4 3 -2 0 1 4 -2 2 2 -1 2 -1 1 -1 2 0 2 -1 0 -3 1 0 -2 -1 -2 3 -2 1 -2 4 -4 0 -4 -3 1 -3 0 -4 -1 0 0 0 -2 4 -1 3 -4 -1 1 -3 4 2 -2 2 -3 4 0 -2 -2 2 0 -2 -1 -4 2 -4 -3 0 -3 -1 0 -3 4 1 5 3 -4 -3 0 4 -2 -4 1 -1 1 -1 1 3 1 -1 2 2 -2 5 -5 3 0 0 1 1 -2 -1 5 2 -1 -4 -1 -3 0 1 0 3 4 -2 -2 -2 2 1 0 0 0 0 5 0 -1 -1 -3 -1 1 2 0 3 1 -2 0 -1 2 -3 -3 2 1 -1 2 -5 -1 -1 3 2 2 4 -2 -3 -1 -4 -1 3 0 -2 3 -3 0 5 3 4 2 0 2 1 -2 -4 3 3 -2 3 1 3 0 2 -1 -1 1 2 -1 2 0 1 -1 0 1 0 2 -3 3 2 -1 -1 1 -3 3 2 -2 -1 0 4 -2 0 -1 2 -2 -1 0 1 2 5 2 4 4 0 1 3 -4 1 0 0 1 3
601
icq - 402174
Поза форумом
#20 2007-01-05 11:19:45
- Ilya Porublyov
- журі
- Зареєстрований: 2005-10-27
- Повідомлень: 130
Re: Обсуждение решения задачи Areaplus (только после 23:59 04.01.07)
Певне уявлення про мій (авторський) розв'язок можна отримати, прочитавши http://forum.osvita.ck.ua/files/page093.TIF та http://forum.osvita.ck.ua/files/page094.TIF
Але передивитися якимись іншими засобами щоб знайти де ті 10% -- теж непогано. В умовах коли твердо відомо про 10% і про перетини не більше як по два -- по суті, трохи гірша реалізація цієї ж ідеї. Але якщо конкретно 10% і конкретно двійки не буде, то...
Відредаговано Ilya Porublyov (2007-01-05 11:22:28)
Поза форумом
#21 2007-01-05 14:47:23
- Sleapwalker
- Новий користувач
- Зареєстрований: 2006-11-25
- Повідомлень: 17
Re: Обсуждение решения задачи Areaplus (только после 23:59 04.01.07)
В мене ідея базувалась на тому, що якщо якісь паралепіпеди перетинаються, то один з них лишається незмінним, а другий розбивається на шість менших, і так передивляються всі пари (і початкових, і утворених) паралепіпедів, і в кінці знаходим їх об'єм.
Close your eyes
Feel the ocean where passion lies
Silently the senses
Abandon all defences
Поза форумом
#22 2007-01-05 22:30:46
- FireTiger
- Новий користувач
- Звідки: Донецк
- Зареєстрований: 2006-09-27
- Повідомлень: 86
Re: Обсуждение решения задачи Areaplus (только после 23:59 04.01.07)
тест для тех, кто писал O(N^3) и меньше....
100 1 -3 3 1 -2 3 3 3 -1 -1 0 -2 5 -2 -1 0 2 0 -2 0 0 1 -1 -1 0 3 2 5 -3 4 -1 2 0 0 0 -4 5 -1 -2 0 -1 -4 -3 -2 -1 5 -3 3 2 -3 0 -2 0 3 1 3 2 4 -1 -5 2 2 2 -3 -5 -1 -1 3 0 4 0 -3 3 2 0 -1 4 -1 2 -2 -1 -2 0 3 0 -2 0 2 -1 -1 2 -3 5 3 1 2 2 4 -1 1 0 -3 1 -2 -1 0 -1 -2 -1 -1 -3 3 3 4 -1 1 -3 -2 -3 -1 0 1 3 -3 0 3 -2 4 -1 -2 3 0 -3 0 -4 -2 2 -4 -1 -1 -2 1 -4 1 3 4 4 0 -1 1 1 0 -3 -4 4 0 -5 0 -3 0 -1 -5 -1 -5 -4 3 -3 2 2 2 2 -1 0 2 4 -2 -1 -4 3 -2 -5 2 4 -1 -1 -1 -5 -1 0 -3 2 -1 1 -3 2 2 1 -5 -3 -2 1 -2 3 2 -1 5 3 1 -4 0 1 -1 3 -3 0 -4 1 1 2 0 1 2 1 4 4 1 -3 -1 -1 3 2 4 1 -1 -2 0 -2 -2 0 2 0 2 4 4 0 2 4 0 2 2 -1 2 0 -5 -4 -4 2 1 -2 0 1 2 3 -2 -2 -1 2 1 -5 -1 -2 0 -4 -2 1 1 -4 0 3 1 1 5 0 -2 1 -4 -2 0 0 -4 0 -3 1 4 1 1 2 -2 1 1 -3 2 -1 -1 1 -2 -1 -1 1 1 2 -4 3 2 -5 -1 2 0 -2 1 -3 4 3 0 1 4 -3 -1 -5 3 -2 4 2 3 0 -2 -1 0 -1 2 0 -1 2 -5 -1 0 4 0 -3 -1 -3 0 4 1 -5 2 -3 -2 -1 1 -1 0 1 4 -1 0 1 -1 1 0 -1 -4 -1 3 -4 3 -2 0 1 4 -2 2 2 -1 2 -1 1 -1 2 0 2 -1 0 -3 1 0 -2 -1 -2 3 -2 1 -2 4 -4 0 -4 -3 1 -3 0 -4 -1 0 0 0 -2 4 -1 3 -4 -1 1 -3 4 2 -2 2 -3 4 0 -2 -2 2 0 -2 -1 -4 2 -4 -3 0 -3 -1 0 -3 4 1 5 3 -4 -3 0 4 -2 -4 1 -1 1 -1 1 3 1 -1 2 2 -2 5 -5 3 0 0 1 1 -2 -1 5 2 -1 -4 -1 -3 0 1 0 3 4 -2 -2 -2 2 1 0 0 0 0 5 0 -1 -1 -3 -1 1 2 0 3 1 -2 0 -1 2 -3 -3 2 1 -1 2 -5 -1 -1 3 2 2 4 -2 -3 -1 -4 -1 3 0 -2 3 -3 0 5 3 4 2 0 2 1 -2 -4 3 3 -2 3 1 3 0 2 -1 -1 1 2 -1 2 0 1 -1 0 1 0 2 -3 3 2 -1 -1 1 -3 3 2 -2 -1 0 4 -2 0 -1 2 -2 -1 0 1 2 5 2 4 4 0 1 3 -4 1 0 0 1 3
601
Проходит... А я писал тупо... разбиение на маленькие параллелепипеды и для каждого считаю входит он в объем или нет...
ICQ 339203772 - Если что-нибудь срочно необходимо - стучитесь, я отвечу!
----------------
Основная проблема с программистами заключается в том, что вы никогда не можете сказать, чем они занимаются, до тех пор, пока не будет слишком поздно.
Поза форумом
Сторінок: 1
- Список
- » Третий тур NetOI-2006
- » Обсуждение решения задачи Areaplus (только после 23:59 04.01.07)