Всем привет!
Скоро (9 августа, 19:30 MSK) состоится очередной Codeforces Round #195 для участников Div. 2. Как обычно, Div. 1 участники смогут поучаствовать в этом раунде вне конкурса.
Автором раунда являюсь я. Выражаю благодарность Геральду Агапову (Gerald) за помощь в подготовке задач, Евгению Соболеву (Seyaua), Виталию Аксёнову (Aksenov239) и Сергею Сухову (Serega) за тестирование задач, Александру Игнатьеву (aiMR) за тестирование задач и перевод разбора на английский, Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon, Марии Беловой (Delinur) за перевод задач на английский язык.
Всем удачи и высокого рейтинга!
UPD: Разбор задач
UPD: Поздравляем победителей:
Отдельно хочется поздравить Егора Куликова (Egor) — единственного человека, который сдал все задачи!
Надеюсь задачи будут не как в прошлый раз, что никакой красный не смог решить все, это же Div2 контест.
Не дождешься... :) В этот раз красные, наверное, решат, но Div2 — вряд ли
Про множественное число в слове "красные" не угадал.
Да жесть вообще. А Egor поздравляем с победой :)
Сегодня только один красный все решил.
Растем. Еще несколько сотен раундов от этого автора и тогда простые смертные смогут решить 4-5 задач.
Здравствуйте! Хочу спросить совета: я в олимпиадном программировании новичок, задачки получается решать плохо, алгоритмы знаю только сортировок. Ну немного ещё понял идею динамических и жадных алгоритмов. Ну так вот, в чём вопрос... стоит ли участвовать в подобных раундах, или сначала нужно выучить все базовые алгоритмы (ну или хотя бы дочитать Лезерсона? :))
P.S. Если вопрос глупый, прошу тухлыми помидорами не кидать.
Я советую порешать задачки из архива из прошлых Div-2 раундов (преимущественно A,B) и на основе этого принять решение.
Теорию полезно совмещать с практикой, так что стоит как учить алгоритмы, так и участвовать в раундах. Сложность Div. 2 раундов допускает участие с (почти) любым уровнем подготовки, к тому же во время соревнования приобретается ценный опыт.
Конечно, стоит! Это же весело! Я, когда написал свой первый контест, из сортировок знал только выбором)
P.S. Что за Лезерсон? Яндекс находит только повара(
P.P.S. Может имелся ввиду Лейзерсон?
Угум, именно он)
P.S. Спасибо за совет, буду участвовать.
Удивительно книгу "Алгоритмы. Построение и анализ" называть Лейзерсоном, а не Корменом :)
Ты сейчас про Ривеста? ;)
Который Ривест-Адельман-Шамир? А причём тут RSA и криптография? ;)
Он соавтор "построения и анализа".
*тег <юмор> я потерял
how and when can I be sure that I am registered for the contest ??
about 18 hours before the round , you can find the registration link , in contest page.
Hi . first login then Go to the hereand see your name and all registerant or goto the here see your name and friend name if your name is be there your register . Excuse me for my bad writing .
The Div.1 participants will be rated???
Are you a Div.1 participant !? :))
hehe...No..U can know through the color of my name...
Just Kidding!! :D
No. Codeforces Round #195 (Div. 2)
i think this contest should be "Eid Special" :)
hhhhhhhhhhhhhhh (y)
hhhhhhhhhhhh==heheheheehehehehehehe???
happy feast to all muslims :)
I hope a non-russian-speaking person had the chance to proofread the problem statements
Ans scoring system ???
Scoring system will be announced later
Later means after the contest ?
edited
The website is too busy... terrible T T
boring problem set, specially problem B :-| Really miss interesting problems on CF
For some reason when we have only div2 rounds they are much harder than when we have both div1 and div2 rounds.
I wonder why this is the case.
During the last year, there were a lot of div2 contests where I managed to solve all the five problems. However, solving A-B-C in div1 contest was a rare thing for me.
http://codeforces.me/blog/entry/8424#comment-142084
This one follows the rules too!
Почему задача"Б" такая тяжелая ? Объясните , как ее решать (после окончания раунда ).
Особенно интересно, что за 3 претест :(
Ну поймём для начала, что мухи будут бегать из каждой нижней в каждую верхнюю.
Далее решим за О(1) для каждой нижней. ЧТобы сходить прямо вверх нужно 2*r, чтобы в соседнюю — (2 + sqrt(2))*r, дальше (2 * k + 2sqrt(2))*r. Используем формулу суммы арифм.прогрессии.
Код
any further explanation for problem C ?? .. i think it's not clear atleast for me :D
dirty problemset :| [kaCf]
Is anyone else having problems with problem b? It says my answer for the second pretest is wrong, but it gives the answer for the second example (I guess that's also the second pretest?) as 5.4142135624 and mine is 5.41421356237, which is less than the 10^-6 error they allow, but is still graded wrong
Please don't discuss problems until the contest ends.
your code prints
7.41421356237
for me (note first symbol)I enjoyed this problemset, though most people probably don't like tricky cases.
Edit : Express your opinion and get downvoted. Communism for the win.
Problems was bad! But Thanks for fast system testing!
Your avarar shows typical Div2 participant's face after this round ended I guess :) Cool problems, but a bit harder, than Div2 used to be
Что означает wrong output format Unexpected end of file — int32 expected?
В одном из случаев ты ничего не выводишь
Благодарю
How fast the system testing!!
What's the solution for problem C? Thanks.
for every bit position (0 to 32), consider numbers in the array that have this bit set (= 1). Take bitwise and of all these numbers for each position i in [0,32), this takes O(32*n) time. Note that AND has "the more, the better" scenario, ie, for a particular v let set S be solution; if (v+1)th bit is set for a number N, then N \union S will also be a set with solution v. Using this, calculate above array. Now find maximum i 0<=i<32 such that the "bitwise and" calculated above has all bits 0 to i-1 unset (=0). This is the solution
Make 30 buckets (vectors) and if a number from array has i-th bit turned on (0 <= i < 30) put the number in i-th bucket.
After that for each bucket calculate the bit-wise and of all the numbers in that bucket and if that sum is divisible by 2^i output all the numbers in that bucket and the size of the bucket, of course choose i to be as high as possible.
Edit: got ninja'd by the user above me :D
same as c0d3junki3, but i use a builtin function named __builtin_ctz . It returns the number of trailing 0-bits in x, starting at the least significant bit position.(I think it's faster than %)
Wow system test is so fast now...I like it. Problems are great, a little bit too much math though. Have enjoyed it. Thanks to authors!
Кто-нибудь знает почему попытка может быть проигнорирована, если я решение повторно не посылал?
why this submission skipped???it's correct![submission:4249620] please help!
I think there is something wrong in the description of the problem C. I wonder how to understand this sentence in problem C: "If such number v doesn't exist (that is, for any non-negative integer v, number b1 and b2 and ... and bk is divisible by 2v without a remainder), " if v doesn't exit,number b1 and b2...and bk is divisible by 2^v should with a remainder,am I right?
meaning if bitwise and is zero, then v can be as large as you want. In this case, answer is -1
thanks,i get it.
if b1&b2&...&bk == 0 it divides to all 2^v, and we don't have maximum v
yes,so there must be a solution.
Really, all this sentence is saying is that the number (b1 and b2 and ... and bk) should not be 0. If it was 0, it would be divisibly by 2v for any non-negative integer v.
It was hard to understand though. I wish they just said "(b1 and b2 and ... and bk) should not be 0".
thanks for your explain:)
Может кто-то объяснить почему для теста 3 1 ответ 3,25?
Та же самая просьба !
Присоединяюсь. Я уверен, где-то очень туплю но у меня выходит 3,387.
Пересчитывал руками, вроде бы так-же. Для крайних выходит (2 + (2+sqrt(2)) + (2+sqrt(2)+2)) (учитываем дважды) Для центральной (2+(2+sqrt(2))+(2+sqrt(2))) И того 22+6*sqrt(2) Делим на 9 получаем 3,387
между крайними ответ 2+2sqrt(2) чутьвправо, подиагонали до верха, чуть вправо
Точно. Спасибо
Вот здесь зеленый путь короче.
Спасибо
why not make a scoring board for Div.2 only without the out of competition participants ? To know your real ranking during the contest
you can unchecklist "show unofficial" :|
In top right corner of scoreboard is checkbox "show unofficial". Just uncheck it and you've got it :)
You can see the Div. 2 only scoreboard by unchecking the "show unofficial" checkbox in the top right corner
Click that "show unofficial" checkbox (in particular, untick it).
EDIT: TOO MANY SNIPES
Is there a problem with the contest list? round 196(div 1) is 4 days later than round 196(div 2)!
For problem A, if you see sample test 1, input: 10 5 output : 0 15 15 0 But how about 0 9 23 0 ? The conditions are still held, moreover its area is smaller. What would you say?
Oh, it's my bad. I thought "isosceles" is right angle because it was written as "isosceles(<ABC is right)". Should have looked up.
The triangle must be isosceles which means that the two sides are equal in length.
why this submission skipped???it's correct![submission:4249620] please help!during the contest this submission had accept!why now is skipped??:(
See http://codeforces.me/blog/entry/7007
Maybe, You submit the same code with another handle.
well,i have 2 account!and i submit for them!:|
Yeah! But it's against the rules of Codeforces.
неужели координаторы задач не видят, что этот раунд сложнее обычного див2? неужели так сложно было в этом случае сделать динамическую разбаловку, раз уж задачи такие получились?
неужели в задаче Д было сложно сделать в примерах тест, когда n != m???
500 3000 3000 3000 3000
Мне раунд тоже не очень понравился. По-моему, у этого автора вечно что-то нужно посчитать, типа ДП или комбы какой-то. Я с конца в этот раз начал читать задачи. После того как видел "выведите количество вариантов по модулю 1000000007" у двух последних задач, дальше и не читал даже. Кому-то такие задачи нравятся, а кому-то наоборот нет. Мне кажется, что нужно придерживаться определенного баланса в этом смысле.
Whats wrong with this solution? C WA6
http://codeforces.me/contest/336/submission/4257324
actually my beauty is 29 :|
I've got the same question. My solution write beauty 29 too.
The beauty of your answer is 21 not 29, the remainder with 2^29 is not 0.
I was thinking why they are telling their solution's beauty is 29 instead of 21!
Note that if you claim the beauty to be 29, then the AND of all numbers you pick must be divisible by 229. In your case, the AND of all numbers you pick is actually 229 + 221, which means it's not evenly divisible by 229. (The actual beauty in this case is 21; 229 + 221 is divisible by 221 (giving a quotient of 28 + 20 = 257).)
I suppose you misunderstand the problem.
Did you find out what's wrong with that ur approach? Now even i'm curious..
If I registered and didn't attempt any problem, will my rating be calculated.??
no
not at all
ABCE's name is "Vasily the Bear .."
and D's name is "Bear Vasily"
What's the point?
The problem title might be limited at either 35 or 36 characters; "Vasily the Bear" for D causes the problem title to go to 37 characters. (The next longest is E at 35 characters.)
I'm not sure about what you say! For example problem 319C's name is "Kalila and Dimna in the Logging Industry" which has a length of 40!
"Bear Vasily and Beautiful Strings" can change to "Vasily the Bear and Beautiful Strings" which has a length of 37. (37 < 40) ! Maybe it has another reason!
Can anyone tell me, why was this round JUST AND JUST geometry?!
C and D are not !
nope Pedrams
Quick question...
On 336b, the one with the circles and the ant, I am getting a different answer when I run my code than what the tester is getting. I'm using python 2.7, and when I enter
2 2
for the second test, I get 5.41421356237 in my python interpreter, but the tester is getting 7.41421356237 when it runs my code. Does anyone know why this is happening? I did not import any external libraries and all my code is pretty standard...Even when computing manually (by hand, not by an interpreter), I got 7.414 as your output. Are you sure you didn't misread 5 as 7?
Oh, whoops...I edited one file and submitted a different one xD Sorry about that
почему раунд 196 для див1 и для див2 будет проходить в разные дни? автор подготовил 10 задач?(уже исправили)
Why the rating not change?
sorry for my bad English
your english is okay enough
deleted. was about repeated topic
The beauty of such sequence is -1 according to the problem statement
when will rating change?
have patience vidyut
codeforces is not bad
I think gridnevvvit doesn't want to write the editorial of this contest!
P.S: Ratings changed!!!
Можно поинтересоваться почему во второй задаче ответ: 5,41421356237309 считается неверным, при том что верный:5.4142135624
Дело в другом, 5,41421356237309 -> 5.41421356237309
Не понял, честно сказать.. 1..6 знаки правильные
wrong output format Expected double, but "5,41421356237309" found
В условии об этом не сказано. Сказано только о погрешности..
Дело не в погрешности, а в том, что у Вас число неправильно написано, после целой части должна идти точка, а затем дробная часть. А у Вас стоит запятая вместо точки.
Может я туплю : но мне одному кажется что это один и тот же код просто на разных языках ?) 4254254 4255478
Problem D is quite nice.
Classic Contest
Почему не Медведь Дима?
how to prove problem A in simple out 1 I think (0,10),(20,0) is more small than (0,15),(15,0)
The triangle must be isosceles.
ooo thx I am so stuipd.,,.
My first time facing a floating point problem on codeforces. The custom test case was outputting -0.0000 for all my answers on g++ 4.7 using printf. What is the reason for this ?
Can you show a testcase where it doesn't work?
Sure. Here is the code : ( Problem C : http://codeforces.me/problemset/problem/336/B ) http://ideone.com/SxkStn Run it on any test case 2 2 or 1 1 The same code gave me AC on submitting using setprecision
You're right, there seems to be something wrong with GCC on Codeforces: even the following program
outputs
-30329013470001650000000000000000000000000000.000000
instead of the correct answer.I got wrong on Pretest 1 twice. So thankfully no negative points, but wasted 20 minutes to figure out was going on.
solve problem a in a few minutes, and try to understand other problems for about 2h...
Sorry but I really can't hold it anymore. With all respect the way the problems are written is not clear at all. Well not all of them but some.
Дорогие организаторы! Это div-2 контест! Пожалуйста, не забудьте это!
До контеста еще -3 дня, не надо паниковать, не забудут