Согласен =)

Instead of preparing them before every contest, I advise you to set all things in your default source of whatever compiler you might be using, so that when you create a new file( program ) you will have already the predefined code. It will spare you a lot of time.

I think that they want to increase the number of Div1 users, because Div1 contests make many users become div2 users.

well i was just a few seconds late, but i guess the show must go on

...

Can someone please give me a more simple example than test 10 of why my greedy approach is failing? http://codeforces.net/contest/279/submission/3248428

I keep 2 counters, number of zeros and number of ones. I look at all groups of consecutive 0's and consecutive 1's. If such a group has size 1 , i increment the corrsponding counter, else, I increase by 2 the corresponding counter. In the end, the result should be min(number 1's , number 0's + 2), representing that either we erase all ones or try to convert all 0's into 1's and do 2 more operations at the end.

Thanks !

http://codeforces.net/blog/entry/3302

Сделаем предподсчет m[mask] — маска чисел из a которые мы можем получить попарными суммами чисел из a которые есть в маске mask. Это делается за O(2ⁿn) убиванием младшей единицы в mask взятием маски от полученной маски и дальше поинтером идем по отсортированному a чтобы проапдейтить m[mask] попарными суммами содержащими младший (убитый) бит. Дальше динамика z[idx][mask] — сколько итераций прошло и какая маска, но понятно что idx — это просто позиция старшей единицы в mask, поэтому idx в состоянии не нужен. И осталось перебрать переход за O(n).

Приношу свои извинения!

удивительно, а в чем смысл, какая у нее цель? высокий рейтинг? как то тупо!

На Codeforces уже столько задач, что скоро можно будет рандомно выбирать 5терку из архива..

На первом контесте в первом моем ПТЗ, мы долго пихали какую-то задачку. Добавляли лишние предподсчеты. В итоге пихнули. После контеста, нам сказали, что мы сдали задачу с запасом в 20мс от TL, 1MB от ML и 15 секунд до frozen.

Я решал динамикой z[i,j] сколько позиций обработали и какая степень двойки уже набрана в позиции i (-2 <= j <= 2). Перебираем еще сколько возьмем текущей степени (-3,3) и делаем переходы. Здесь везде границы конечно должны быть от (-1,1) я просто не хотел разбираться со случаями.

Я решал жадиной. Начиная с конца строки искал первую единицу и смотрел что перед этой единицой. Если тоже 1, то к строке делал прибавление числа (1<<разряд). Если 0, то вычитал 1<<разряд.

На дорешивании прошло.

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

Is there any easier way to solve it rather than simulate the spiral per coordinate ? (Problem A)

So we learned the knowledge, and to grow in experience.

http://en.wikipedia.org/wiki/Longest_increasing_subsequence

upd: Человек спросил, можно ли решить задачу в формулировке, в которой он ее понял, я дал ему линк на то, о чем он спросил, внимание вопрос: за что минусуют?

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

Прошу прощения, если обидел авторов шуткой. Все-таки трудно отследить все задачи.

With Chrome I couldn't see either. Had to use IE for hacking.

It must be a strongly tricky case, lots of submissions got WA in this particular case.

that's a case like,

10 1
1 1 1 1 2 3 4 5 2 1
1 10

Try this

7 3
4 2 2 2 2 2 10
2 7
2 6
5 7

It must be three "Yes". And i have the same mistake like you have ->My Submission Even the the same line .. ^^

Спасибо за интересные задачи. Но мне показалось что задача C легче A.

Почему же нельзя? Можно! Многие так и делали, насколько я видел.

P.S. Надеюсь, "за один проход для каждого элемента" подразумевало один проход для всех элементов? (:

rng_50216 is the child of rng_58 and peter50216.

Check test: 3 1 2 1 1 1 3

Strange that it passes all the previous tests.

Input: 6 1 2 1 1 1 1 1 1 6

My solution prints "Yes" and it seems to be ok, but your solution prints "No".

Как раз-таки 3, а не 5: если читать с книги №3, мы успеем прочитать 3-ю, 4-ую, 5-ую и потратим на это 7 минут. А 6-ую нам уже не успеть, ибо 7 + 10 > 15. Мы же можем только подряд книги читать, а пропускать нам никто не разрешал. Кажется, это уже обсуждалось здесь.

You interpreted the task properly (if by subarray you mean a substring). You can calculate the solution in a single pass through the array, such that when you are at the j-th position, you also store the minimum i such that [i..j] is the maximum substring that ends in j. What you do is add the j-th value to the current sum, and while the sum is larger than t, subtract the i-th value and shift i one space forward. After each step is done, check whether the current interval size is larger than the maximum recorded so far and you're done.

Here's my code for that: 3240473

at first my solution was O((n^2)*(2^n)) and than I used that every number is distinct for precompution and got O((n^2)*n) . so think about it...

+1 I used the greedy method to solve this problem,but i don't know how to use DP to solve. can some1 explain?

Editorial please? Thanks!

When is the editorial?

Comon guys, some of us are still very curious to see how dynamic programming applies to D and E.

Vicennial Did you find it out? If possible, could you explain the solution idea?

Consider the case, 4 1 2 1 1 2 1 4

I also made the same mistake :P

I think this case 1 2 1 1 2 1 might fail your solution. For this case, array brr will always have zero values since if the query is L = 2 and R = 5, the answer should be No while your solution might output Yes