Доброго времени суток! Скоро состоится мероприятие под названием Codeforces Round #214 (Div. 2), автором которого являюсь я, Дмитрий Березин. Это мой второй раунд, и Сережа надеется, что последний :)
Личная жизнь — такое дело, в котором много счастья не бывает, поэтому вам снова нужно будет помочь Диме и Инне. И да, Сережа вовсе не выступает в роли негативного персонажа, скорее, в роли обстоятельств, с которыми вам придется порой бороться...
Большое спасибо Геральду Агапову (Gerald) за помощь в подготовке раунда, Марии Беловой (Delinur) за перевод задач, и Сереже Нагину (Sereja) за то, что любезно (покидает комнату) согласился помочь в тестировании.
Сережа передает привет, и настоятельно рекомендует прочитать условия ВСЕХ задач.
Разбалловку скажу, честно. А разбалловка 500-1000-1500-2000-2500.
Спасибо за внимание, хорошего раунда!
По просьбе человека, чье имя обещал не разглашать, за то, что он помог мне тестировать раунд, размещаю здесь небольшой пиар. (в правке)
Хм, кто бы это мог быть... Думаю, сообществу никогда не раскрыть эту тайну.
Сопоставляя ваши габариты, я с трудом верю в то, что это была просьба..
Надо обещания выполнять:
http://codeforces.com/blog/entry/9625#comment-151291
Ох, так и вижу, что теперь полуголый Sereja будет появляться в комментариях каждого нового раунда на codeforces... :)
Не стоит. Тут и так уже начинаются комментарии, что я несу "разврат в кодфорсес", думаю, пора остановится :)
Как по мне в ваших задачах ничего такого нет.Легенды довольно забавные, и поэтому задачи приятно читать.
С каждым раундом все меньше и меньше одежды!
Hope, there will be nice problem statements for English version ... :)
Most probably, I hoped a wrong thing... :/
"и Сережа надеется, что последний"<--Сережа конкурентов убирает:)
Комнату не забудь убрать, качественно!
МЫ с первого курса вместе, и за мусор в комнате отвечать мы будем тоже вместе :)
ОНИ плохо закончили)
Это так мило :)
Study for exams or do CF round? Hmm. Screw exams. :D
same here :(
classical situation.
Go to sleep or do CF round? Hmm. Stay aside please, sleeping. :D
This is my first round with "Java" and I hope not the last
If it will help you, author solved his own tasks in java also :) I can recomend you to use "fastReader" you can find it in any code of any participant in java with high reiting. Have a nice round!
Good choice, my friend :)
http://apps.topcoder.com/forums/?module=Thread&threadID=804294&start=0&mc=2
Can someone help me with above problem ? It is related to LRUcache. I use STL map and set but i get WA. Does anyone know of any test case where it fails ?
If you ask for help, make a new blog post for it. Don't do it in the comment's section of something completely unrelated. This way, you won't get an answer, but just low contribution.
I was studying and hope to do well in this contest.
Своевременная разбалловка — это так прекрасно!
Ну и убожество в условиях.
Вот и зови школьников писать див2 раунды :(
Ну вот я прочитал условия и не вижу ничего убожеского. Легенды забавные, но небольшие и не отвлекают, и вроде бы в каждой задаче понятно, что просят сделать.
Пожалуйста, аргументируйте. Мы стараемся учитывать мнения участников по поводу условий. Что конкретно вам не нравится?
Ну, теоретически в них есть подтекст, который 16+ или 18+. Наверное претензия именно в этом.
Согласитесь, читать такое 12 летнему ребенку — не стоит.
Ого. Даже не знаю, что и сказать. Укажите, пожалуйста, место в условии, которое может смутить ребенка. Если оно действительно есть, прошу прощения, ибо никаких подтекстов в мыслях не держал :)
"Дима, Инна и Сережа собрались в комнате. Правильно, кое-кто лишний."
Наверное, все же поторопился, насчет 18+ подтекста, видимо просто для взрослого все так "очевидно" или может опыт жизни в общежитии подсказывает :)
UPD. В любом случае нельзя забывать, что то, что забавно для 20 летнего, может быть чересчур откровенным для 12 (а то и 10) летнего школьника
А Вы любите проводить свидание с девушкой в присутствии соседа (пусть и очень хорошего) ?
Я люблю не писать о своих отношениях везде, где могу. Тем более в условиях задач по олимпиадному программированию.
То-есть если б автор контеста написал вместо своего имени — любое другое, всё было б нормально? =)
Нет, было бы нормально серьезно относиться к составлению задач, а не писать любовные истории.
Если такой умный чего ты контесты не даешь?
================================================================ Как по мне, автор достаточно серьёзно отнёсся к подготовке соревнования. Задачи интересные и в меру сложные. А легенда задаче так или иначе нужна. Или интереснее было бы, например, в первой задаче прочесть что-нибудь такое:
"Даны четыре четвёрки чисел a,b,c,d. Если среди них есть такая, для которой выполняется min(a, b) + min(c, d) < n + 1, выведите её номер, min(a, b) и n - min(a, b)"?
В таком случае это уже было бы не условие, а решение)
почему Сергей Соседов сам не поет? :)
Естественно нет. Легенды забавны и приятны для чтения с этим не поспоришь.
Но теперь представьте, вы бы хотели чтобы Ваш сын в 10 лет читал об этом? Повторюсь, я не юрист, и не моралист, но теоретически существует ситуация что чтение легенд может нанести будущим звездам спортивного программирования "психический, физический и нравственный ущерб"
Пока смотрю вики, на предмет точных формулировок.
Я думаю, что "испорченных" детей такими текстами не испортить, а чистые душой ничего такого в них и не заметят. Это обсуждение и занятая моралофагами радикальная позиция намного вреднее самих условий, имхо
Вы правда считаете, что дети в 10 лет о чем-то не знают?
Интересно, много десятилетних детей решают раунды КФ?
Если человек в 10 лет уже в состоянии программировать, то он достаточно взросл, чтобы узнать всю правду о нелегких отношениях Димы и Инны)
А это что то меняет?
В следующей раз почаще пишите что Инна и Дима любят друг друга, это очень важная информация. В каждом условии есть "Дима любит Инну", "Инна любит Диму", "Сережа "лишний"" и т.д. и т.п. Еще добавьте в следующий раз поцелуев в задачку, чтобы нам еще интереснее было. Можно еще интриги: "Инна ревнует Диму", "Дима пришел позже чем обычно". Ну и конечно побольше подробностей из их жизни вроде "Дима и кровать" и т.п.
Неужели нельзя составить нормальные условия, вырезав все сопли, а не выставлять свои эмоции и чувства на показ!? Не каждому приятно такое читать, не потому что завидно или т.п., а потому что напрягает просто само по себе.
Сопли и разврат, это если бы было написано: "я ее любил, а она мне не дала".
Знаешь, не каждому приятно читать что то вроде: "в Берляндии живет Ариктафен" или подобное. Всегда будут недовольствия, и без этого никак.
А запрещать писать что то конкретное, у нас тут демократия как никак. Каждый имеет право на что то свое, возможно необычное. И свои недовольства большая просьба не навязывать. Хотел бы скинуть картинку по этому поводу, но боюсь это уже будет из категории "18+".
Может Вам просто завидно что Вы прыщавый задрот, и у Вас нет девушки?
О вкусах не спорят. Математическая формулировка задачи ясна (я надеюсь). Некоторые участники (клянусь, они не подкуплены!) считают, что мои легенды забавны и приятны для чтения, и даже не мешают решать задачи!
Спасибо за критику, впрочем, не в той форме, в которой бы ее хотелось читать.
Оооооо! Задачи интиресные, думаю тут не поспорят. И условие тоже, вроде, без всяких замыслов
Действительно, куда интереснее "Диме подарили на день рождения массив".
ахахах, да-да, даже помню была задачка, где ему подарили очередь, стек и дек =)
Я тоже хочу на день рождение в подарок, красивый массив и очередь ^_^
Мда, видимо, это было слишком резко, извините.
С другой стороны, надеюсь, автору не очень обидно, раз уж он считает ежедневную ругань по любому поводу забавной, нормальной и подходящей для легенды.
Конкретно не нравится сеттинг, весь целиком. Объявление нормой описанных в легендах отношений с этим самым пилежом, подкупом жалких вахтерш, девушкой, роль которой сводится к тому, чтобы пилить и стругать салатики; соседом, которого надо заставлять уходить из его комнаты — ну и все такое, мне не хочется опять открывать условия, чтобы написать точнее. Честно, очень тоскливое впечатление от них.
О Г-ди! Куда же катится моя жизнь! Прочел, так страшно стало :)
Могу лишь посоветовать немного проще относится к жизни. Можно начать с условий моих задач :)
Мне жаль, что условия не пришлись Вам по вкусу, но нравится всем, согласитесь, желание не очень.
Извините еще раз, если затронул чего-то или кого обидел. Не хотел.
А вот формулировки оскорбляющие прекрасную девушку, добродушную вахту и хорошего соседа, я считаю, неуместны. Особенно учитывая, что это реальные люди. Не стоит их обижать.
Ну, не стоит — так и не обижайте. Можно подумать, это я тут вывешивала неприятные подробности ваших отношений с девушкой.
подкупом жалких вахтерш
девушкой, роль которой сводится к тому, чтобы пилить и стругать салатики;
Читать не приятно, при том, что это не так. Ругаете за то, что условия слишком переплетены с реальностью, не подумав, что есть и часть вымысла, и сами строите транспонированный граф.
Почему не подумав? Да пусть они хоть полностью вымышленные, эти условия — вымысел-то все равно неприятный.
А в прошлом раунде от этого автора, Codeforces Round 208 (Div. 2) Sereja надавал Berezin пинков. Вот и ещё один затравленный персонаж появился — хилый Berezin, который не может за себя постоять =(
Наталья, поверьте, то, что Дмитрий описал в своих задачах (с долей вымысла и гиперболы), не имеет ничего общего с настоящими проблемами жизни в некоторых общагах. Честно.
Вот если бы был сделан контест по мотивам этих проблем — тогда бы реально ему нужно было бы ставить возрастной рейтинг наподобие 16+, а то и 18+. Там реально были бы вещи, от которых детей стоит ограждать.
Так что попробуйте, пожалуйста, отнестись попроще к сегодняшним задачам. Вам же будет легче...
Да я верю, что можно было написать еще хуже, чего тут обсуждать.
Вы с автором оба так просите, чтобы я отнеслась к этим задачам попроще, что мне кажется, что это вам от этого станет легче, а не мне :)
Но мое-то к ним отношение и так проще некуда... Вот автору, наверно, стоило бы как раз посложнее отнестись к своим легендам. Повдумчивее. Ну не знаю, поменять, например, мысленно себя местами со своей девушкой в этих условиях и прикинуть, насколько ему было бы приятно это читать.
Смотрите: Вы восприняли ситуацию в негативном ключе — в итоге испортили настроение по меньшей мере двум людям: себе и автору контеста.
А я просто пытаюсь склонить Вас к тому, что такой юмор на самом деле не настолько плохой, чтобы из-за него у кого-то портилось настроение.
Кстати, весьма вероятно, что девушка автора прочитала условия и от души над ними посмеялась :).
Спасибо за защиту :)
Настроение не испортилось, а, скорее, поднялось :)
Правда забавно было тут про разврат почитать.
Девушка, я вам больше скажу, помогала придумывать условия, за что ей большое спасибо :)
Ну, я немного по-другому на это смотрю: автор испортил настроение мне, я — ему, все честно. До итога дело еще не дошло — может, в итоге в следующий раз условия будут получше?
Охотно верю, что этот юмор про отношения вам кажется неплохим. Как и анекдоты про тупых блондинок, например (по-моему, того же уровня творчество в среднем). Но не понимаю, зачем вы меня пытаетесь в этом убедить. Я бы еще поняла, если бы там вас выставляли в некрасивом свете. Скажем, автор столь же смешно шутил бы про то, что все казахи читерят на контестах — тогда у вас были бы какие-то основания за него вступаться. А так-то что?
Рекомендую почитать следующий раунд :)
Я уже даже придумал условие на всю эту тему :)
Заключающий пост в ветке: 1) такое надо выяснять в личку, это неприятно читать многим. 2) не надо мне портить настроение :) 3) в сумме в ваших комментариях негатива для чтения гораздо больше, чем во всех моих 10-ти условиях (моё скромное личное мнение).
Спасибо за то, что посетили раунд. Хорошего дня!
Выскажу свое мнение.
Конечно, не стОит писать автору контеста, что его условия убоги, это довольно неприятно читать, да и не соответствует действительности. Условия имеют необычный стиль, близкий к разговорной речи, но это не очень принципиально (хотя лично я сторонник более литературных текстов, пусть они и получаются немного длиннее в некоторых случаях). Куда важнее то, что даже при беглом прочтении условий бросается в глаза большое количество грамматических и пунктуационных ляпов в условии (есть и просто опечатки в виде перепутанных букв). Например, разберем условие первой задачи.
1) "Каждая вахта состоит из двух вахтерш." — ну, казалось бы, вахтерши работают на вахте, а не вахта из них состоит :)
2) "Чтобы пройти через некоторую вахту нужно задобрить обоих вахтерш." — пропущена запятая, да и вахтерши стали мужского пола
3) "любой целой цены начиная от 1" — аналогично
4) "Единственный способ потратить 10 рублей, ..., будет купить" — криво с точки зрения грамматики
5) "Чтобы задобрить первую вахту нужно" — нет запятой.
6) "вахта, которую мы модем задобрить — третья" — во-первых, опечатка, во-вторых, запятой нет.
Возможно, есть и другие ошибки, которые я пропустил при беглом просмотре.
Я понимаю, что есть масса людей, для которых подобные опечатки не важны, однако лично мне даже мелкие ошибки всегда бросаются в глаза. Именно поэтому я перед контестом всегда по много раз перечитываю свои условия, стараясь найти и исправить мельчайшие ошибки. Странно, что координатор раундов ничего не заметил в этот раз ;)
Спасибо большое за Вашу критику. Читать ее действительно приятнее.
Приношу свои извинения за подобные "ляпы", в свое оправдание могу лишь сказать, что объем работы большой, и не всегда сил хватает в сотый раз вычитывать условие, хочется отдать предпочтение составлению тестов и т.д.
А по факту да, действительно, не должно быть такого, буду работать надо собой.
Спасибо
Мне в основном не нравится легенда в задаче B:
Благодаря вам Дима чудесно провел выходные, но пришло время делать дела. Естественно, что Дима, как и все мужчины, у которых есть женщина, все делает не правильно.
Инна и Дима сейчас вместе в одной комнате. Инна ругает Диму за каждое дело, которое он делает в ее присутствии. Поругав Диму за какое-то дело, Инна удаляется в другую комнату и там ходит по кругу, причитая, какой у нее непутевый суженый. За это время Дима спокойно успевает сделать k - 1 дело. Затем Инна возвращается и за следующее дело, сделанное в ее присутствии, вновь ругает Диму, после чего снова удаляется в другую комнату. Описанное продолжается до тех пор, пока Дима не сделает все свои дела.
...
Не любая история подходит для легенды. Эта конкретная история мне кажется неподходящей для широкого круга читателей. Я считаю её некорректной.
(Например, я ни разу не видел задачи, условие которой построено на сортирном юморе. Считаю, что она была бы примерно настолько же некорректна.)
Не понимаю как можно сравнивать такие вещи. Если есть желание объяснить мне, можем поговорить в личке.
Зря вы набрасываетесь на авторов из-за условий. Во-первых, я не думаю, что заключённая в условиях сторонняя информация может разложить или поспособствовать деградации детской психики в той степени, чтобы об этом так яро писалось в комментариях к данному посту. Во-вторых, лично я даже положительно отношусь к ноткам юмора в задачах. Они вызывают улыбку и я не думаю, что она неуместна. В конце концов, это не чемпионат мира или что-либо такого же уровня, чтобы шутки были недопустимы. Это уже ставший обыденным контест, направленный на тренировку ваших интеллектуальных и профессиональных способностей. А юмор немного разбавляет напряжённую обстановку соревнования. Поэтому спасибо большое авторам за проявленное чувство юмора и интересные задачи.
Жду новых приключений:D
Надеюсь, будет разбор, а то уж ооочень интересные задачи :D
Очень скоро будет
Как решалась D?
Переберем минимальное значения они только можно быт lk значении. Для каждое значние находим такой путь, нижний предел не больше lk и минималное значение верхних пределов будет максимално. Этого можно делат с Алгоритмом дейкстры с кучам. Если это значение d[n], тогда лояльность равно (d[n]-lk+1). Обновим ответ этим значением.
Как решать С?
Крутая задача, очень понравилась.
sum(a) / sum(b) = k
sum(a) = k * sum(b)
Домножим все b-шки на k, тогда нужно набрать так, чтобы sum(a) = sum(b).
Как это делать: Преобразуем каждый предмет из пары (a,b) в одно число (a-b), наберем подмножество с нулевым таким весом и максимальной стоимости.
Итого: O(n*k*max_cost)
Но как найти такой подмножество?
Рюкзак же.
Вес: (А — Б), стоимость: (А), запускаем самый обыкновенный рюкзак (с отрицательными весами), максимизирующий стоимость, и выводим ответ для нулевого веса.
Подробнее, пожалуйста..
Рюкзак с линией памяти.
Тут лучше код посмотреть, так понятнее будет: http://pastie.org/8505500
А как объяснить то, что такой рюкзак с линией памяти, в этой задаче работает? Почему не происходит занесение в массив несуществующих значений?
Гораздо более понятна реализация с dp[n][max_cost].
Присоединяюсь.
Всё, до чего смог додуматься — все калорийности домножить на k..
Вместо них в принципе можно хранить разности вкусности и калорийности. Тогда требование будет выполняться при таком наборе ингредиентов, у которого сумма таких разностей будет равняться нулю. Вопрос остался только в том, как найти такую сумму с максимальной суммарной вкусностью за 3 цикла..
The terrible English problem statements ....
seems I'm not alone...
What is the approach for C? I tried subset sum type memoization with a variation but got wa on 6th pretest ....
me too, i got TLE on 6th pretest
It is subset sum, or knapsack. For each fruit i, assign an object with volume a[i] — kb[i] and value a[i], and the answer is the set with maximum value and zero volume.
why does the solution considering the subset with max(total taste/ total calories) won't work ? it gives wrong answer on pretest 6
The problem is get k = (total taste/total calories) where total taste is as big as possible.
Задачи интересные. Условия забавные. Автор молодец. А я дурачок =_=
Поздравляю!
не один ты "дурачок". Из-за невнимательности у меня не пошли ни А, ни В. стоило только изменить в А один символ, а в В -- добавить один символ --> все пошло
Бывает.
С чем поздравляешь-то?) Я в А тоже опечатался. Про остальные свои косяки уже товарищам нанылся :)
Я сначала закодил решение для трех вахт. Я даже не читал значения для четвертой вахты, ибо думал, что их всего 3. Хорошо(да-да, именно хорошо, потому что я успел исправить решение), что взломали решение.
Можно ли было в Е заранее подсчитать 8 координат для каждой ноты (самая верхняя-левая, самая верхняя-правая, итд) и далее просто пройтись по массиву q, попутно релаксируя ответ?
Это wa7.
C. dima and salad:-
i had a n! solution in mind..
lol
where can i get its solution/editorial
А почему условии второй задачи вывод при втором наборе входных данных 3 4 6, а не 3 4 4?
Нужно потратить ровно N рублей. Во втором примере N = 10, поэтому потратить 8 рублей недопустимо, так что можно купить одной из вахтерш более дорогой подарок.
Потому что сумма должна равняться 10.
I'm unable to tell in words about problem description !!!! :/
solution or ediorial ?
Got AC?
(you edited your comment and made mine look silly :P)
I just want to know... if an user registers 3 hours before the contest for Div2, and then gets the first place... Isn't quite obvious that he is an Div1 user...?
I don't think so. A lot of people register 10 minutes before the contest even .
I mean, register in the website, not in the contest itself.
hmm then it may be but anyways its not that important to discuss here .
For sure. This happens every round. Just relax and enjoy problems and process of solving them.
The statement was as terrible and lengthy as last Round Codeforces Round 208 (Div. 2). So time-consuming to read them...
True story :)
The statements was very funny =), Problem D was my favorite (although I got WA), I get confused with a simple dijkstra but when I realized about that it need to be careful with segments, the contest was finishing.
Although some people are complaining about the English, I had no problems with the statements (some were lengthy indeed, but hey, that's part of a contest :P).
For me, the problem selection was very nice (although I was not able to perform well :P). Some dp and graph problems with some easier ad hocs, that's more ICPC style than many other rounds (and for me, who wants to practice for next year's ICPC, it was good :)
Nice job!
can any one explain what "Denial of judgement" is ? it got one on 'C' problem today .
can any body explain what "Denial of judgement" is ?
i got one on problem 'C' this round .
Anyone got WA on test 9 at problem D? I don't know what this test case has in particular
it has something to do with multiple edges between the same pair of vertices
Can you give an example, please?
or
The answer is 3 for both tests, but your solution might fail on one of them
My solution works for both :S
Well, my first attempt failed on 9th test and fails on one of these. After I made it work on these tests, got AC. Sorry I wasn't able to help you :)
Thanks, but it passed both the tests.
Почему такой ответ в задаче А не верный 100000
25000 50000 75001 50001
25000 50000 75001 50001
25000 50000 75001 50001
25000 50000 75001 50001
Мой ответ 1 75000 25000
Верный ответ 1 25000 75000
потому что для второй вахтерши за 25000 ничего путного не купишь...
Вы заплатили за подарок второй вахтерше меньше, чем ей нужно хотя бы на один из подарков.
Вы покупаете подарок для второй вахтерши за 25000, тогда как подарок для второй вахтерши должен стоить как минимум 50001.
Не существует второго вахтёра, который бы был доволен подарком за 25000.
servers seem to be responding well to the loads now . There was much less glitches than previous times .
Спасибо за интересные задачи.
Good Problems :D
На самом деле вы оскорбили Кобейна
А кто такой Кобейн?
https://en.wikipedia.org/wiki/Kurt_Cobain
http://codeforces.com/contest/366/problem/E?locale=en
Извините, не читал Е-шку! :|
Правильно этот вопрос надо задавать так: Link
Хе, хе КурткО Бейн
Непонятный комментарий. Произносится "курткабэйн". На этом и построена шутка.
Не хотел оскорбить. Всего лишь дань уважения через филологическую шутку :)
I am wondering why the time limit of E is 3s ? Please see the solution http://codeforces.com/contest/366/submission/5228621
It's so that slower solutions that don't use a certain mighty trick could pass, too :D
how much of that code is part of your template? :D
Замечательные задачки, с удовольствием порешала что смогла, остальное буду дорешивать позже. Похоже, третью можно решить с помощью дерева Фенвика, четвёртая — образцово-показательное дин.программирование, по пятой пока не понятно (кроме как злобным перебором). Желаю счастья в личной жизни Диме и Инне, а Серёже — терпения и удачи! :)
Третья задача — это ДП(рюкзак).
Rating?
Я думал,что я один опечатался в A.У этой задачи какае-то карма волшебная:)
кстати, опечатались мы с тобой в одном месте вот код
Ахахахаха.Вот это я понимаю совпадение:D
In the first page of the rank list there is only 6 regular blue coders in top 20. Rest 14 contestants are new participant(holding top 5 in today's rank list). I was wondering what is the secret behind it??? If after a codeforces round, the change of rating depends on the position in the rank list then it is a very annoying and heartbreaking for div-2 coders if div-1 coders participate with a new handle in each div2-only contest. I have one more question. Will my handle be banned if my contribution underflows 32 bit signed integer for any of my post???
Why is rating updation so slow? zzzzzz
maybe because Berezin didn't thank MikeMirzayanov for faster judging system .
It's that :)
I just miss the clarification about problem C and can't solve it in contest time. Bad luck for me. :(
bad luck ...
rating:1696 TvT
missed the contest, coz of semester exams ... diverse set of questions # :)
В задаче "С" надо выбрать отрезок???
net
It is hard to understand Pro D. Can anybody tell me what's the result about these tests: test1: 4 4 1 2 4 8 1 3 1 3 2 3 4 8 3 4 4 8
test2: 4 4 1 2 4 8 1 3 1 4 2 3 4 8 3 4 4 8
5 and 1?
In the last sentences It show "return to his room as quickly as possible!"...
can anyone please give link to a similar problem or tutorial to problem C : Dima and Salad
You can first try simple subset sum problem and knapsack problem and then try to relate this problem with those two concepts .
It is a tricky variant of classical subset sum problem(at least i felt so). The observation I made during the contest was something like this:
we have three conditions : 1.a/b should be exactly K; 2.We have to maximize a; 3.we have to pick at least one;
condition one: a/b= k => a=b*k =>a-bk = 0 since k is only 10 a,b<=100 , a-bk should fit in 2*10^4 , I kept abs(a-bk) and a flag(say signflag) that distinguishes state a<=bk or a>b in previous choices.
then from each position we have two choices, whether we select the current one or not.
I also kept another flag(say takenflag) to keep track of whether i have taken at least one salad or not. When i have decided to take some ai,bi, I have updated my current difference according to the status of my signflag that tells me whether in previous choices a<=bk or a>bk.and then updating the takenflag into 1. Therefore, Our next call would be a[pos]+rec(pos+1,newdiff,newsignflag,1); see taken flag is 1, we have choose at least one.
And if we don't choose current position, our another possible option is: rec(pos+1,olddiff,oldsignflag,takenflag); just an increment in position keeping other values unchanged.
now we must have to take maximum between these two options: therefore we return dp[pos][olddiff][oldsignflag][takenflag]=max(a[pos]+rec(pos+1,newdiff,newsignflag,1),rec(pos+1,olddiff,oldsignflag,takenflag)); why do we keep max??? because we have to maximize a in a/b=k;
base case:
if(pos==N) we have no choices left, its time to decide by observing what happened in past. Form the states we can say what happened in past. If oldiff==0 then we can say the way we came to pos==N maintains a-bk=0 => a=bk => a/b=k. Also we have to check the takenflag whether we took any salad or not. SO, if(pos==N and olddiff==0 and takenflag==1)return 0; else return -inf;//inf=any large integer
Now we are sure that if there is such path to choose from the given sets such that a/b=k, we shall definitely reach at if(pos==N and olddiff==0 and takenflag==1)return 0; and get a positive answer. Otherwise, whenever we have no option to choose we are returning -inf which is a very large negative number. That means our maximization process returns a negative number when there is no way to satisfy a/b=k for given set.
It was a very naive formulation by me. But there are plenty of excellent source codes that will reduce the state and your coding complexity but the idea is almost same. For example if you start from a very large number and in the base case you reach at that same number then you can say that there is a way, because you are actually shifting all integers by a large value(20000 should be enough) and thus you don't need the signflag.
Sorry for poor English.
can't appreciate language used in problem description, had to go through test cases first and then tried to understand.. btw where can i find editorials?
won't there be any discussion post on the problems of this round?? i'm trying to find out in which pattern i should save the results in problem C Div 2
editorials to the problems have been posted here