| 21 Чернацкий Евгений Геннадьевич, 28 июля 2018 г. 14:06:15 |
| Также решается с помощью перебора по маскам и кода Грея. Простой перебор по маскам дает сложность O(2^N*N), а в коде Грея соседние маски отличаются одним битиком и асимптотика улучшается до O(2^N)
|
|
|
| 22 Строганов Никита Сергеевич, 25 июля 2018 г. 21:33:21 |
| Спасибо предыдущему комментатору, освоил meet-in-the-middle)
|
|
|
| 23 Яндулов Богдан, 19 июля 2018 г. 17:45:39 |
Не прошёл полный перебор (хотя там всё на битовых операциях было) и пришлось воспользоваться техникой meet-in-the-middle (почитайте, отличная вещь). Итоговая асимптотика: O(2^(N/2) * N), что в худшем случае даёт ~50 000 операций. Так что можно смело увеличивать N до 40.
Можно перебор за O(2^N). Главное не пересчитывать сумму для каждого варианта, чтобы не стало O(N*2^N).
|
|
|
| 24 Данилыч, 16 октября 2015 г. 14:28:50 |
| многовато 56%,. Лёгкая задачка.
|
|
|
| 25 Луффи, 04 июля 2015 г. 19:14:19 |
| Лучше хранить ответ с помощью маски
|
|
|
| 26 Шуршилов Артём Александрович, 06 мая 2014 г. 10:57:46 |
| перебор естественно от 0 до ( 2 в степени N-1 )-1 ,очевидно же : )
|
|
|
| 27 Шуршилов Артём Александрович, 06 мая 2014 г. 10:53:34 |
Значит так
1) Решение мне пришло моментально, а именно перебор по всем двоичным числам от 0 до N-1, но я реализовал это с помошью строк и функции toBinaryString в java, она работает медленно
2)спустя много времени я понял что можно не переводить в двоичную, так как все числа в памяти и так в двоичном виде то просто сдвигамии битовым и можно брать бит , скорость увеличилась в разы, но всеравно не хватало
3) тогда я разбил все на несколько потоков и скорость стала пол секунды и задача прошла
P.S. но на медленном сервере (кто не знает тут работает 2 проверяющих сервера) задача всеравно по времени не проходила. Так как я предполагаю там плохо работают потоки в связи со устаревшим процессором.
|
|
|
| 28 Неизвестный, 16 марта 2013 г. 14:16:42 |
| За что 56%?? Эта задача намного легче задачи "Арифметическое выражение".......
|
|
|
| 29 Тушов ®услан, 13 января 2013 г. 8:04:53 |
А что выводить при тесте
24 -589200265
39385534 30476916 15911293 38371549 21530652 45043938 12621967 42525363 2134761 14111218 9238325 43955014 16000617 3519470 49174155 14322640 17458132 48699570 47268475 42502438 22440056 6954642 45947784 38376824
|
|
|
| 30 Алтыбай Назарбек, 06 января 2013 г. 9:09:45 |
| с первого раза!)
|
|
|
| 31 Глейх Андрей Артурович, 31 мая 2012 г. 20:47:07 |
| если пишете на C++ с использованием векторов - передавай в рекурсивную функцию ссылку на вектор и тайм лимита не будет
|
|
|
| 32 Шах Егор Алексеевич, 27 декабря 2011 г. 1:12:56 |
| Совет для тех, кто пишет на c++. Не используйте string для передачи знаков( ответа), он очень медленный и выполняется очень долго, лучше использовать массив char( не передавая его в рекурсии)
|
|
|
| 33 Трубловский Владислав Витальевич, 03 ноября 2011 г. 23:26:13 |
| решение за линию... LOL
|
|
|
| 34 Горохов Артём Владимирович, 31 октября 2011 г. 20:34:48 |
| классная)
|
|
|
| 35 Кудаков Вадим Сергеевич, 06 июля 2011 г. 11:47:02 |
Мда... это явно не та задача, с которой стоит начинать изучение рекурсии >_>
А без рекурсии она банальна. Даже решение "в лоб" прошло за 0.97...
|
|
|
| 36 Девятко Александр Игоревич, 25 марта 2011 г. 19:57:53 |
| требую увеличить n! а так она совершенно банальна.
|
|
|
| 37 Ситдиков Рузаль Раилевич, 22 октября 2010 г. 16:12:13 |
я перебираю всевозможные расстановки знаков и проверяю - подходит или нет, если да то - вывожу.
а как можно ускорить мою программу?возможно ли проверять не все расстановки знаков?если не лень, посмотрите пожалуйста?(1004824)
проверять не все расстановки знаков возможно, но это не даст во мноих случаях больших преимуществ. в ограничениях данной задачи решение возможно полным перебором. Здесь в любом случае получается менее 10 млн. вариантов расстановки плюсов и минусов. Неоптимальность вашего решения заключается в том, что вы определяете массив знаков, а в конце считаете результат в то время, когда подсчет можно вести в процессе рекурсивного перебора, тогда многие операции не прийдется повторять (в рек. вызове можно передавать текущую накопленную сумму).
|
|
|
| 38 Маскин М.В., 17 июля 2010 г. 23:59:45 |
Забыл убрать отладочный вывод на консоль и в итоге получил ТЛЕ
Тоже думал как же можно сократить перебор, но в этой задаче полный перебор в любом случае на яве
(по крайней мере тест такой можно составить точно, чтобы был полный перебор)
В итоге увидел свою оплошность и решение хоть и не быстро, но прошло
Вывод: будьте внимательны=)
|
|
|
| 39 Рубаненко Роман Сергеевич, 28 февраля 2010 г. 22:24:18 |
Ухты...У вас на сервере 2^24 операций выполняются за 1.5 сек..Классно.
Вообще то это всего 16 млн. операций. За 1 сек. может выполнится более 100 млн. простейших операций (например, xor, или даже сложнение) Ну а у вас на самом деле более 1.5 сек. это выполняется, просто наша система не дает работать вашей программе дольше.
|
|
|
| 40 Травин Андрей Юрьевич, 21 декабря 2009 г. 14:53:23 |
тогда получается, что в тесте
5 -10
2 2 2 2 2
должно быть
No solution?
Именно так.
|
|
|
