Привет, друзья)
Уже скоро состоится очередной раунд Codeforces #171 для участников Div. 2. Как всегда, участники Div. 1 могут поучаствовать в соревновании вне конкурса.
Вновь и вновь для вас старалась уже знакомая группа авторов в составе: Павел Холкин (HolkinPV), Игорь Кудряшов (Igor_Kudryashov), Николай Кузнецов (NALP) и Геральд Агапов (Gerald). Традиционно хотим поблагодарить Михаила Мирзаянова (MikeMirzayanov) за системы Codeforces и Polygon, а также Марию Белову (Delinur) за перевод условий задач.
UPD: распределение баллов по задачам будет немного нестандартным: 500, 1000, 1500, 2000, 2000.
Надеемся, что соревнование окажется удачным для всех участников. Мы желаем всем высокого рейтинга, успешных взломов и хорошего настроения)
UPD2: соревнование завершено, надеемся оно вам понравилось)
Поздравляем победителей:
1) study_english
2) ipip2005
3) rng_50216
4) bfrcns197
5) csavky103
UPD3: разбор задач можно найти здесь
Hope this contest will be great as all the others.Good luck to everyone!!!
I love Russian thinking in preparing contest problems ,Hope short statements & easy English words . GL & HF
Согласен =)
haha
?
Starting to prepare includes...
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.
Hi everyone, I has just viewed dj3500's screencast: CodeForces #169 div2. I saw the "hightail" program and go to https://github.com/dj3500/hightail but I don't know how to install it. Can someone help me?
Again and again only div2 contest :( .
I think that they want to increase the number of Div1 users, because Div1 contests make many users become div2 users.
Hope me can change the rating color to purple!!Keep Calm and type the code more quickly! the same to everbody! but, it seems that i got fever:(, It's feel terrible Now:(
Павел, только не забрасывай написание контестов. Эти контесты хорошая тренировка для нас.
Hey guys, no hope for a late reg? Please! I was just 3 mins late
well i was just a few seconds late, but i guess the show must go on
it sounds like 50216 is a popular number. (rng_50216)
The user bfrcns197 solved problem E in 3'rd minute! Seems strange to me..
...
4 minutes before end of contest!
Простите, но я не думаю, что многие это прочли!
Perhaps you shouldn't have written it in here — it has affected the scoreboard!
tourist harlem shake
I was really surprised to see that E was identical with D from a past Div.1 round (132D - Constants in the language of Shakespeare). I just copy & pasted, commented out a single line, and got pretest passed...
Can someone please give me a more simple example than test 10 of why my greedy approach is failing? http://mirror.codeforces.com/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 !
well i guess here is your problems
for 1counter:
if you have two blocks of 1 with more than 2 numbers seperated by only a number 0 (11011) you will only need to change the 2nd group into (11100) in 1 steps, so you get another block of number 1. to convert it you need 2 steps. so 3 in total.
however, based on your solution, cause you have 2 blocks of '1' size 2, you need 4 steps.
testing pretest 3, you luckily right because the number of '0'. but when they increase 1counter and 0couter by adding '100', your 1counter is far bigger than 0counter, so the ans must be based on 1counter.
sorry for bad English
Gracias!
Как решалась D за O(2^n * n)?
http://mirror.codeforces.com/blog/entry/3302
Я не про Е спрашиваю.
Сделаем предподсчет m[mask] — маска чисел из a которые мы можем получить попарными суммами чисел из a которые есть в маске mask. Это делается за O(2nn) убиванием младшей единицы в mask взятием маски от полученной маски и дальше поинтером идем по отсортированному a чтобы проапдейтить m[mask] попарными суммами содержащими младший (убитый) бит. Дальше динамика z[idx][mask] — сколько итераций прошло и какая маска, но понятно что idx — это просто позиция старшей единицы в mask, поэтому idx в состоянии не нужен. И осталось перебрать переход за O(n).
Не, ну ребята, я заявляю свои авторские права!:) http://mirror.codeforces.com/contest/132/submission/1098610 http://mirror.codeforces.com/contest/279/submission/3249012
Приношу свои извинения!
тогда все OK, да.
Это была шутка, можете копировать мои решения сколько угодно, я польщен:)
удивительно, а в чем смысл, какая у нее цель? высокий рейтинг? как то тупо!
А в чем цель писать задачу, к которой есть в кармане решение, заново? Высокий рейтинг на клавогонках по словарю своего языка?
На Codeforces уже столько задач, что скоро можно будет рандомно выбирать 5терку из архива..
За 6 минут до конца получил TL. Переписал рекурсивную динамику на итеративную. Не заработало. За 10 секунд до конца исправил баг. За 7 секунд до конца послал. Получил Претесты пройдены со временем работы 2000мс.
Какие ставки пройдет/не пройдет?
UPD: прошла)))
На первом контесте в первом моем ПТЗ, мы долго пихали какую-то задачку. Добавляли лишние предподсчеты. В итоге пихнули. После контеста, нам сказали, что мы сдали задачу с запасом в 20мс от TL, 1MB от ML и 15 секунд до frozen.
E решалось жадно? и такая задача уже вроде была на кф, называлась, кажется, Шекспир.
Я решал динамикой z[i,j] сколько позиций обработали и какая степень двойки уже набрана в позиции i (-2 <= j <= 2). Перебираем еще сколько возьмем текущей степени (-3,3) и делаем переходы. Здесь везде границы конечно должны быть от (-1,1) я просто не хотел разбираться со случаями.
Я решал жадиной. Начиная с конца строки искал первую единицу и смотрел что перед этой единицой. Если тоже 1, то к строке делал прибавление числа (1<<разряд). Если 0, то вычитал 1<<разряд.
На дорешивании прошло.
:( Я считал, что в задаче B книги расставлены по кругу, и нужно выбрать книгу, с которой лучше начать движение по кругу, затем читать, пока можно. Более часа потратил на дебаг, в итоге не успел дописать C , epicfail и 923е место.
да всяко бывает) я теперь наверное сопьюсь от того, куда поставили задачу А) Технично так вынесли ею мозг в начале раунда. После этого про Б что только ни подумал — и про круг, и про параллелепипедик.
+1 давать задачу на довольно трудоемкую реализацию в Div2 A есть не хорошо
См. мой комментарий чуть ниже.
Меня А-шка тоже вначале слегка сбила с толку. Хотел начать писать симуляцию, потом быстро одумался и написал разбор случаев.
А эмуляция уже не в моде? Я вот за 6 минут написал и норм, фиолетовый. (:
Не у всех красных такая бешеная скорость, как у Вас, я уже не говорю про остальных. Кому-то проще дольше подумать и закодить короткий разбор случаев.
P.S. Поздравляю с выходом в див1 :).
E was easier than A, what a terrible contest !!! .... :o
Is there any easier way to solve it rather than simulate the spiral per coordinate ? (Problem A)
You can 'push' the given coordinates to the corner. Then handle the corner cases. Then it's just O(1) math stuff per query
I suppose 'easier' meant faster. So calculating all the formulas was time-consuming, while writing simple emulation took 6 minutes only. (:
So we learned the knowledge, and to grow in experience.
I wish every rating updates were as fast as the sysTests :)
Неужели я один неправильно понял это предложение в задаче B и потратил из-за этого уйму времени?
" Каждую книгу Валера читает целиком, то есть он не читает книгу, которую не успеет дочитать до конца из-за нехватки свободного времени."
Я почему-то понял это так: можно пропустить книгу, если не хватит времени ее прочитать, и продолжить дальше читать следующие книги. Кстати, кто-нибудь знает, как решать задачу в этой формулировке?
http://en.wikipedia.org/wiki/Longest_increasing_subsequence
upd: Человек спросил, можно ли решить задачу в формулировке, в которой он ее понял, я дал ему линк на то, о чем он спросил, внимание вопрос: за что минусуют?
9 человек не понимают, как наибольшая возрастающая подпоследовательность относится к этой задаче
для вашего случая: отсортируем массив и возьмем максимальное количество книг которые можем прочитать. очевидно, что найдется такая книга из выбранных что все остальные выбранные книги лежат правее от нее в исходном массиве. будем читать начиная с выбранной книги и пропускать те книги, которые не вошли в выбранные.
Это неверно: n=5, t=7, a={3,4,2,4,2}, правильный ответ 2 (исправил тест, раньше было неправильно)
По всей видимости, имелось ввиду решение задачи в той формулировке, в которой понял I_love_Chelsea.
Ну оно неверное, выше приведен контртест
отсортировали: 2 2 3 4 4. под t=7 подходят первые 3 элемента — 2 2 3. Среди них самый левый в исходном массиве — 3. начинаем читать с него, пропуская все ненужные книги.
Вот только после прочтения первой книги мы обязаны читать вторую, так как времени на нее хватит
Да, я не заметил разницы между "Можно пропускать книги, если не хватает времени" и "можно пропускать книги, если мы захотим".
------------------------------------------------------------ расширяйте посты)
Если я правильно понял, I_love_Chelsea подразумевал возможность пропускать лишь книги, которые нельзя прочитать. А Вы хотите пропустить вторую книгу в исходном массиве с "ценой" 4, а 4 + 3 <= 7.
Am i the only one who thinks that final testing on the last few contests run much quickly than earlier ?
Странно, что задача Е уже была Д див 1, а сегодня стоила столько, сколько д див 2=) Может, потому что баян?)
Прошу прощения, если обидел авторов шуткой. Все-таки трудно отследить все задачи.
Неужели авторы хранят обиду вот уже четыре года?
Am I the only one who couldn't hack? I couldn't even see source codes.
With Chrome I couldn't see either. Had to use IE for hacking.
Could someone help me find out why my code for problem C is failing? Here is my code . It got WA in test 21.
It must be a strongly tricky case, lots of submissions got WA in this particular case.
that's a case like,
My output is 'Yes'. Isn't it correct?
Try this
It must be three "Yes". And i have the same mistake like you have ->My Submission Even the the same line .. ^^
Oh, now I can see what was wrong. Thanx.
thanks bro...i can now see where i failed system testing hopefully now i can use this lesson to do better algorithms in future...
NP guys.I just want to be a nice person in CF but look my contribution ...
Sen kalbimizdesin bro...
Really helpful.... Thanks
По задаче E:
11:42
Просто вспомнилось :)
Спасибо за интересные задачи. Но мне показалось что задача C легче A.
Мне кажется, что задача А — чистая реализация или математика, кому как. Задача С была хоть и несложной, но всё-таки более идейной, чем А. Так что порядок вполне логичен (это моё сугубо личное мнение).
За что мне спасибо? :)
Объясните пожалуйста, почему в C нельзя было за один проход для каждого элемента посчитать, где заканчивается лестница, начавшаяся на нём, а потом при обработке запросов смотреть ближе ли левая граница запроса, чем посчитанное число?
Почему же нельзя? Можно! Многие так и делали, насколько я видел.
P.S. Надеюсь, "за один проход для каждого элемента" подразумевало один проход для всех элементов? (:
Да, я имел ввиду для всех за 1 проход. Спасибо!
I think one of the reason behind low solve of Problem D is Poor Description.. I have read it more than 5 times, still i haven't understood what is the problem !!
what's the relationship between rng_58 and rng_50216?
rng_50216 is the child of rng_58 and peter50216.
the last drop of ethic.
lol :D :D
and..which one is the mom ?
No!My boyfriend is sevenkplus!
Lots of solutions for D gave incorrect answer for the following test case:
2 1 1
Edit: My test is wrong. The numbers are distinct
I can't see what 's wrong with my solution to problem C Can anyone help me with that? submission : 3245705
Check test: 3 1 2 1 1 1 3
Strange that it passes all the previous tests.
Very thanks. I found the bug; if we get another array for the size of good sequence which ends with "i", it would be ok!
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".
задача Б
10 15
10 9 1 1 5 10 5 3 7 2
Вывод:5 {читаем с книги №3} разве не так?
а никак не 3
Как раз-таки 3, а не 5: если читать с книги №3, мы успеем прочитать 3-ю, 4-ую, 5-ую и потратим на это 7 минут. А 6-ую нам уже не успеть, ибо 7 + 10 > 15. Мы же можем только подряд книги читать, а пропускать нам никто не разрешал. Кажется, это уже обсуждалось здесь.
мы ж ее не успеваем прочитать, а значит не берем.. Спасибо за отсылку
"Каждую книгу Валера читает целиком, то есть он не читает книгу, которую не успеет дочитать до конца из-за нехватки свободного времени."
Can anyone explain Problem B (279B — Books)? This is how I understood the problem:
We are given an array A and an integer t. We have to search for a "sub-array" of A whose sum of elements is at most t. The answer should be the maximum length of such a sub-array.
However, I must have misinterpreted the problem. I have looked at some submitted solutions and they involve forming the sum of the first j elements of the array A and then substracting the elements A[k], A[k+1]... A[L]. Somehow two "pointers" j and k are involved which I do not understand.
I'd be grateful if someone could explain this. Thanks.
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
Your explanation is excellent! I first tried to solve it by searching for subarrays (substrings) [i..j] with maximal length and sum<=t by using two loops and got a timelimit exceeded, I guess since it results in O(n^2) runtime.
Your algorithm is a clever idea with only O(n) runtime. Thank you PetarV!
You also could have done it in O(n*log n) by keeping d[i]=sum{a[1..i]} and for each j=1..n binary search for the largest k>=j such that d[k] <= d[j-1] + t.
I don't get it, why does it works?
how can we solve problem D ? I gave a solution with complexity O((n^2)*(2^n)) but definitely it gets TL.
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...
You mean you got o(n^3) solution ?
It's been quite a while since the contest ended. When will the editorial be published?
The editorial is late... can some1 please explain E.. I saw many codes.. but i dont understand how they arrived at that solution...
+1 I used the greedy method to solve this problem,but i don't know how to use DP to solve. can some1 explain?
It's been quite a while since the contest ended. When will the editorial be published?
Editorial please? Thanks!
Please publish the tutorial quickly
When is the editorial?
please publish the editorial as you said.
Comon guys, some of us are still very curious to see how dynamic programming applies to D and E.
This is how I solved the problem, hopefully the reasoning is right For E using dp, Let a single move = addition of 2^k or 2^-k s = the binary string, s[0] being the first digit = the last character in the string
Let dp[POS][i] = minimum number of moves needed to get a string l such that l[0..i] exactly match s[0..i] and l[i+1 ..] = 0 Let dp[NEG][i] = (same as above) l such that l[0..i] exactly match s[0..i] and l[i+1 ..] = 1
If s[i] == 0, then dp[POS][i] = dp[POS][i-1], since you don't have to make any additional move. For dp[NEG][i], we can either make our move from a [POS][i-1] state, where we have to turn all bits from l[i+1....] to 1, but leave l[i] =0, so this takes 1+dp[POS][i-1] (just a single move, note that a negative power of 2 turns all bits to the left to 1, but leave the right bits unchanged -> -2^k = 11111... 000..). Or, we can make our move from a [NEG][i-1], which means we have to turn the ith bit to 0. This we can do by adding a single positive power of 2, which means only 1 extra move. Thus. dp[NEG][i-1] = 1+ Min(dp[POS][i-1], dp[NEG][i-1])
And for s[i]==1 case, similar reasoning. Base case -> dp[POS][0] = 0 if first bit is 0, 1 if first bit is 1, dp[NEG][0] = 1, because you still have to make the bits to your left =11111...
EDIT: whoops, something is wrong with my reasoning.. Hold on... EDIT EDIT: k nvm, I was confused about something else. Hopefully someone can agree/point out mistakes?
А почему товарищу albert96 дали +83 за этот раунд? Он вроде был в 1-ом диве и участвовал вне конкурса
When will the editorials of this round come out? The editorials of the next 5 rounds are already published. @admin: please prepare it as soon as possible.
Very good
tutorial please ?!
tutorial please ?! really need it !
Editorial -> when? please. Thnakyou.
Can someone tell me the logic behind this problem? 279C - Ladder
I've tried reading other people solutions but I dont understand properly.
Vicennial Did you find it out? If possible, could you explain the solution idea?
As explained in the editorial , for each index you should find
i) lowest index i where decrement occurs (most people implemented it as array moving right to left and noting index where a[i] > a[i+1])
ii) largest index j(before that index) where increase occurs , (implemented as array from left to right noting most recent index where a[i] > a[i-1] )
now for subarray [x,y] ,if most recent decrement for index x is 'i' and most recent increment for index y is 'j' then, if( i <= j ) then segment is a ladder 35071213
Can you explain the logic please? :)
now for subarray [x,y] ,if most recent decrement for index x is 'i' and most recent increment for index y is 'j' then, if( i <= j ) then segment is a ladder.
Explanation : think of it this way — if the segment is a ladder first all the increments should occur then all the decrements. eg 1 2 3 4 2 1
Now for 'x' we look at the closest index on its right where decrement occurs . (say A) , Also for 'y' we look closest index to left where increment occurs say(say 'B') . Now A < B will only happen when the segment is a ladder . Try out some cases to verify this
Got it.. Thanks! :))
Why am I getting WA in 19th test case for problem C ? Is there some extreme tricky case ? Here is my submission — Submission
Consider the case, 4 1 2 1 1 2 1 4
I also made the same mistake :P
You should have posted the editorial as the questions were good. Hope you do it atleast now. @HolkinPV
Could anyone explain why my code is wrong. Means could anyone give a possible test case/explanation of why my code is wrong. Link of submission attached-> (https://mirror.codeforces.com/contest/279/submission/101634918)
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