Решаю задачу. Ссылка на задачу. Пробую решить 2мя способами. 1й - перебор всех вариантов и сравнение + фильтр. 2й - бинарный поиск. 1й способ проходит 9 тестов (их содержание не знаю), а на 10й тестирующая программа говорит о превышении лимита времени. 2м способом решается только 2 теста, а на 3й выдаётся неправильный ответ. Что исправить? В каком направлении грести?
1й способ (перебор)


2й способ (бинарный поиск) 

Не знаю, что у вас неправильно, но если память не жалко (а там дается 16мб, что веселит), то потратьте вы жалкие 64кб на массив типа bool.
Перый лист отметит true в существующих индексах, по прохождению второго списка, от 10000 отнимаем число и проверяем стоит ли true для этого индекса (если это не превышает 32767 разумеется)
Смысл надеюсь поняли? 

Или вам конкретно хотелось бы узнать свои ошибки?

Вот о чем я говорю, берет 256кб (видимо bool берет все же по 4 байта... очень подозрительно), проходить все тесты. Да, решение не оптимальное, но первое что пришло в голову, когда увидели 16мб   


Это сообщение отредактировал(а) sQu1rr - 3.1.2012, 19:43

У Вас как минимум пропадают результаты вызовов bSearch в функции bSearch же.
В результате из bSearch возвращается неизвестно что.
Нужно хотя бы

Добавлено через 2 минуты и 52 секунды
И тонкий намёк: отсортированы оба массива (хотя, может, и так проскочит).
От рекурсивной функции я бы отказался (хотя, опять же, и так сойдёт))))

Здесь вообще не нужен ни бинарный поиск, ни перебор всех вариантов. Задача решается за один проход.
Даже более того, если бы это были 2 списка из разных файлов, то и память не нужна бы была.
Здесь сложность что списки идут по очереди из stdin, и поэтому приходится запоминать 1 список в каком-то массиве.
массив лучше брать не статический, так как полагать что максисальный размер будет

неверно.
По условию

он может быть и больше, так как элементы могут быть равны. например 1,1,1,1,1,2,2,2,2,2,3,3,3,3,3, и так до 50000  
членов будет гораздо больше чем 50000, ваш статический массив переполнится и произойдет крах программы.
Лучше всего заюзать что-нибудь из стл.



Повторюсь, если бы списки шли из разных файлов, то программа бы упростилась вообще до 2-3 строчек.

Эээ, нет. Условие 1 <= Ni <= 50000 ставится именно на число элементов в списке, а не на значение элемента в списке. Последнее же выглядит как –32768 <= элемент <= 32767. Поэтому

правильно (может, единичка лишняя, это не принципиально). Другое дело, что не всегда стоит доверять входным данным...


А вот это как раз и есть следствие отсортированности двух массивов сразу   
Но дайте человеку самому дойти до истины   

feodorv, да, действительно, немного не внимательно прочел условие, вы правы, 

Ну правилльно, то оно правильно, но стоит ли объяснять преимущества динамических массивов перед жестко заданным статическим массивом в 50001 элементов.

Так что от стл отказываться не стоит даже в этом случае.

В принципе, надо себя уже приучать к динамическим массивам. Просто в данном случае важнее само решение, нежели экономия стека.

Преимущество в экономии памяти, но скорость доступа к ячейке уменьшается в разы
В таких алгоритмах важна скорость, тем более когда лимит памяти сверх нужного (16МБ)
СТЛ нужно использовать везде по возможности, если от него что-то требуется (в моем примере стл ну просто лишний, например), что самому писать и лень и глупо да и не стоит, с этим соглашусь.

sQu1rr, не в разы. При переходе с простых массивов на стл, скорость если и уменьшается, то на очень небольшие проценты.
Чаще всего скорость вообще, не уменьшается, т.е. 1:1
Сказывается правильность библиотеки и оптимизация компилятора.
Проверено неоднократно.

Нет, я ж не спорю, это смотря что выбрать, если вектор, то да, но, извините, чем он отличается от обычного массива, просто его местонахождение будет в стеке, что сыграет свою роль на скорости но настолько маленькую, что забудем. А под

вы скорее имели ввиду чтото вроде std::set или map или даже лист сойдет.
Так вот
Если доступ к ячейке обычного массива или вектора константен O(1), то
скорость доступа к set или map O(logn), заметьте я ничего не придумываю, это написано в документации, а
найти нужный элемент в списке O(n) в худшем случает. Так вот.
Значит при массиве в 50000 элементов каждый поиск будет стоит для мапа или сета будет стоить 15 операций, а список в худшем случае обойдется во все 50000.
Используя вектор в стл получем константное время, но опять же, если использование ограничено созданием вектора и дуступе к его элементам, не вижу смысла в использовании стл, это
стоит лишних заголовков и символов. Только для общего стиля, как говорится )

Кстати говоря в свете данной задачи мы говорим о разном, ведь используя ваше решение, стл действительно необходим и кроме преимуществ ничего отрицательного и не дает.
Я же говорил об использовании в своем решении или решении автора
  

Это сообщение отредактировал(а) sQu1rr - 4.1.2012, 03:59

Господа, я ещё маленький и не знаю стл((
sQu1rr, спасибо за решение. Оно прошло =)

sQu1rr, 

Ну естественно. Выбор типа контейнера лежит на совести программиста. И скорость работы, при переходе на стл, не будет падать только при разумном выборе нужного контеейнера, а не абы как - любого, какой придет в голову. В данной задаче не нужен ни мэп, ни сет. я использовал дек, причем работа идет только к крайним элементам, что оптимизировано, для данного контейнера.

sQu1rr, спор ни о чем. Я не критикую ваше решение, мне просто вчера захотелось решить эту задачку, вот и все. Не знаю даже почему. обычно здесь не очень интересные задачки, а здесь, вдруг захотелось  . И вовсе не потому что ваше решение плохое.
Это разные решения. У вашего метода есть плюс - ему не нужен отсортированный список, но есть и минус, при расширении диапазона значений, решение станет невозможным, т.к. память начнет потребляться немеряно.

Согласен, я уже признал это в предыдущем сообщении, извиняюсь за невнимательность   

Вы хоть разобрались как оно работает? И почему так несправедливо проигнорировали лаконичное и изящное решение, предложенное volatile? Его стОит пристально изучить и переписать без использования stl, если stl вызывает затруднения. И поняли, что не так у Вас в решениях?

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


Двойной break заставляет думать, что так автор хотел сразу выскочить из двойного цикла  А в результате происходил практически полный перебор N1 * N2 вариантов. 

Это сообщение отредактировал(а) feodorv - 4.1.2012, 23:26

Вставлю еще свои "пять копеек".
На АСМовских контестах предлагается решить ряд задач (10) за определенное время (3 часа). Эта задачка считается очень легкой и должна быть решена за 5-10 минут, сразу и без намека на отладку. Решение, предложенное volatile хорошее, быстрое, но не слишком ли "ненадежное"? (В том плане, что можно по неаккуратности ляп допустить) Для других исходных данных (допустим, N<200000), действительно необходимо линейное решение. А здесь прокатывает и O(NlogN):

По неаккуратности ляпы можно допустить где угодно   И первоначальный вопрос как раз и состоял в:

И ляпы там были...


Вот именно, для малых N годится и вариант с бинарным поиском (номер 2 в первом сообщении этой ветки). Просто он не учитывает все условия задания - отсортированности обоих списков, а лишь отсортированность второго. И даже если отталкиваться от бинарного поиска, то отсортированность первого списка приводит к сужению границ поиска во втором, а понимание того, как сужаются границы, приводит к варианту volatile. Но просто вариант с бинарным поиском прокатить может.


В данном случае мы не ограничены во времени и отладке. И даже если такой тест пришлось бы проходить, то после его прохождения всё равно стоило бы устроить разбор полётов в том стиле, как шахматисты пересматривают свои (и не только) партии. Это и есть обучение.


Вот и я тупо взял решение от sQu1rr, и вуаля, тест пройден. И в чём смысл такого "программирования"?

Silent, в Вашем решении я не понял эту строчку:

Откуда там взялось волшебное число 10000?

feodorv, это по условию задачи


Silent, ваш вариант ялвяется логическим развитием варианта sQu1rr. Там действительно была некая ненадежность. При выходе значений из диапазона (-0x7FFF, 0x7FFF), программа сорершала сегфолт. Ваш вариант надежней в этом плане. Но скорость!
Это тот случай, о котором и говорил

умножив на перебор всех элементов, итоговая сложность вашего алгоритма N*logN
Зачем?  , Как я уже писал:

т.е. O(N). Причем, учтите, что это самый неблагоприятный случай. В реале, будет даже быстрее.
(Кстати, ваш алгоритм уступает не только по времени, но и по памяти.)

Теперь о надежности. В чем не надежен мой алгоритм? Единственное условие - данные должны быть отсортированы. Но это прямое условие задачи. В конце концов, даже если сумасшедший пользователь   , даст на вход не отсортированые данные, моя програамка не совершит сегфолта. Просто будет неверный результат, что вполне естественно.
Вобще, надежность, это первое о чем я обычно думаю, и упрек в ненадежности, честно говоря меня несколько удивил...

Добавлено @ 00:14
---
зы:я говорю о надежности по отношению к данным пользователя (foolproof).
защититься от сумасшедшего сопровождения (maintenance) увы, невозможно.  

Это сообщение отредактировал(а) volatile - 13.1.2012, 00:40

Туплю