Всем привет!
В это воскресенье, 30 марта, в 11:00 MSK, состоится Codeforces Round #239 для участников обоих дивизионов. Обратите внимание на необычное время проведения раунда.
Автором задач являюсь я, izban. Большое спасибо команде Codeforces: координатору задач Геральду Агапову (Gerald) за неоценимый вклад в подготовку задач и Марии Беловой (Delinur), которая перевела задачи на английский язык. Также спасибо Ниязу Нигматуллину (niyaznigmatul) за прорешивание задач.
Желаю всем хорошо написать раунд и с удовольствием провести выходные!
UPD: Разбалловку вы можете увидеть на странице с задачами.
UPD2: Разбор вы можете найти по этой ссылке. Обратите внимание на бонусы в некоторых задачах!
Why is the time at 11:00 AM MSK rather than the usual 7:30 PM? Now the Americans won't be able to compete in the contest unless we stay up until 2AM or later in some parts
I think it's because TopCoder SRM 614
TopCoder SRM 614 will be held tonight, not Sunday.
For some people the time is inconvenient, for others it is convenient.
We have the same problem here, in Mongolia 19:30MSK is 23:30
I would say I'm in America, but I'm not American. Almost Americans won't care about this kind of competition, as well as Obama. In anyway, I will stay waiting and participate for this codeforces round.
In Vladivostok,usual time is inconvenient like far-east countries,I think.
I woke up at 2:30 am and did pretty well; it's not impossible :)
Если комментарий наберёт ровно 42 к концу контеста, опубликую крутую статью :)
====================================
If this comment will get exactly 42 to the end of the contest, I'll publish awesome blog entry :)
Is it ok to get 42 by absolute value? ;-)
Yes, sure ;)
If conscience allows it :)
-42 устроит? :)
Ты не понимаешь комментарий на английском выше? Какая жалость.
====================================
You don't understand English comment right above? Such a pity.
So close...
Not now :D
Just as promised.
Link
I think it coincides with March Lunchtime of Codechef :)
This time 's good for Asian. In Viet Nam it 's 2:00 PM, so I can go some where at Sunday night :)
I prefer weekend rounds. But it is probably due to NEERC this time.
#збаник_пряник3:00 pm. It'll be so perfect time for Chinese participants.
Please clarify the start time of the round. The link to the start time indicates the round will start at 10 am Bulgarian time while the counter says it will start at 9. Please note tonight whole europe will switch to summer time while AFAIK Russia no longer switches the clock. Could you please clarify the time in GMT to avoid confusion?
EDIT: please note that after my comment the authors did at the start time in UTC.
Actually both times point to 10am Bulgarian time after the switch which makes sense. Still please post the time in GMT for people who do not know that in Moscow no switch to summer time will happen.
Жаль что с утра еще CodeChef Lunch Time, хоть он и 3 часа идет и кончиться когда раунд уже как час идет,хотелось и то,и то успеть.
Что же наверное потом вирт. напишу
Какой кодчиф, чувак, ты чего?! Тут сам Збань контест даёт!
Поясните пожалуйста, что в этом особенного?
Да вы тут сговорились все, что ли?! Ты мне лучше скажи, что в этом неособенного?
Может быть потому что это обычный автор раунда, ничем не отличается от остальных авторов. У него получился такой же хороший раунд как у остальных. Что тут необычного?
Может, вы и в существовании вселенной не видите ничего необычного?
.
Ну, это бесспорно.
Good Luck for Everyone
http://rghost.ru/53592076.view Это ему конечно не поможет, но всеже.
since only 2 minutes left for round to start, can u please post the score distribution?
Hello. Please understand me, I am new to the site and I don't know where to post and I'm not a genius when it comes to English. What is the leg of length?
It means side of the triangle with given length (note that we generally exclude the hypotenuse). Only consider base and height.
Leg = one of the 2 shorter sides.
Leg of length a = the length of that leg is a.
Sad day for hackers.
Seriously?:) http://codeforces.com/contest/407/standings/page/1
DIV 2. Problem A, B I was talking about. :)
Кто-нибудь может объяснить, почему в этом коде DP[i] может оказаться меньше 0?
Так делать нельзя.
Нужно так:
А, понял. У нас же и pre[i], и pre[P[i]-1] по модулю. Хорошо хоть, NikitaPogodin своим взломом указал, что решение неправильное :)
Ограничения в задаче B Div-1 можно было бы сделать и по-жестче, существует несложный алгоритм ее решения за O(n).
А ещё можно было бы поменять её местами с A Div-1, IMHO.
0_о А как ее решать не за O(n)?
Именно поэтому я подумал, что ее надо решать за квадрат :)
Как решается А?
Может это и не самое простое решение, но можно было расположить одну из точек в центре координат x1 = y1 = 0. Тогда a^2 = x2^2+y2^2. Перебором найдем x2 и выведем по очевидным формулам y2 и координаты 3 точки.
Например, записав, что площадь треугольника a*b/2 = (x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2))/2, и вспомнив, что x1 = y1 = 0, получим, что a*b = x2*y3 — x3*y2 ; с другой стороны x3*x3 + y3*y3 = b*b . Находим x3,y3 .
Если все целочисленные и не параллельны осям (то есть попарно никакие координаты 2 не равны), мы нашли ответ. O( А )
А как найти координаты третьей точки? Перебрать икс внутри первого цикла?
Отредактировал
Можно решать аналитически — использовать тот факт,что треугольник прямоугольный, и строить нормаль.
А можно задачу вообще полным перебором решать — переберем все точки, которые на расстоянии а от начала координат, и все точки, которые на расстоянии b. Для каждой такой пары проверим, подходит ли она.
Ну если перебор заходит, то вообще бред. Это же Div-1, можно было бы сделать хотя бы a,b < 10^6.
Тогда могут быть некоторые проблемы с тем, чтобы
:)
Ну почему бред, первых точек будет O(log(A)), вторых точек будет O(log(B)), значит перебор работает быстро, за O(log(A) * log(B)). Разве что, нахождение всех точек делается за O(A + B), но можно и за O(sqrt(A) + sqrt(B)).
Я о том, что большинство решений работают за O(A*B).
Ну ваше решение тоже за такую сложность работает, разве нет?
Да :D
Я говорил, про О(A*B), простите
Ну как же, вот этот цикл выполняется за O(A):
Нехорошо редактировать комментарии на которые уже ответили.
Не бейте меня сильно, но у меня за О(A*B).
С большими ограничениями — по ощущениям, это уже как-то слишком для div1 A.
Да у меня тоже за O(A * B), просто изменить до O(A + B) можно секунд за 30, просто при таких ограничениях смысла в этом не было.
А откуда оценка в O(logA)?
ко-ко-ко, что-то ты разошелся, только решения за О(1), только автосркое решение должно заходить!
Если a был направлен из 0,0 по оси Y а b оттуда же по оси X, и мы немного повернули треугольник так что координаты конца b стали (xb, yb) то координаты конца a можно тупо по пропорции найти:
Если буквы не попутал. Но суть должна быть ясна — там в одном месте на тангенс надо поделить, в другом умножить — значит его самого и считать не надо.
Согласен, тоже так решал.
I figured the tricky case for A but somehow couldn't hack for the entire contest :(
I have tried using Chrome and IE in Windows, Chrome and Firefox in Linux. All I saw is a spinning black circle and unresponsive "Hack" button.
What is the flash player version I should have? Or is anyone having the same problem?
Огромное спасибо за замечательный контест. Задачи были очень интересные.
Wow fast system test.
wonder if this will happen again!
Well, ratings don't need to be updated really fast, unlike the systest. It's the place in the ranklist that's keeping us on edge; when we know it, we can estimate the rating change, but the exact value doesn't matter so much.
I guess people are used to superfast rating changes from TC. That's one of TC's biggest pluses (although it still doesn't balance out the Bad Idea Arena).
Of course, taking a week just to update ratings is not OK, like some sites do.
yes i guess ur right. sorry if i offended anyone.
anyway, today ratings were updated much faster. :)
В системе какая-то бага. Все мои посылки на Java8, прошедшие претесты, сейчас получили рантайм на 1 тесте. P.S посмотрел статус, видимо вообще все посылки под Java8 получили рантайм на 1 тесте.
P.P.S Все пофиксили.
Уже исправили.
Перетестировали, все посылки, прошедшие претесты (говорю про себя) прошли ;)
So close! 46th...
I know I can't be moved up the ranklist for no reason. But can I be moved down? Just 1 place, plz :D
Why do you want my place? :P
Because it's 47th! (42nd is fine too, but that'd require moving up) :D
You know, 46=47-4/4, it is a little bit lucky too.
is
47ur lucky number or something? :Dhussh.. Problem B div1 was easier than problem A.. :(
Very nice problems ! Congrats to the author ! I loved problems C and D ( and finally got solved D ).
Today was a good day for hacks (Div 1).
Задача С тест 21. Гипотенуза авторского ответа не подходит к тесту. У авторов треугольник не прямоугольный.
575 * 575 + 85 * 85 = 337850
(460 — 51) * (460 — 51) + (345 + 68) * (345 + 68) = 337850
Вроде сходится, не находишь?
Согласен, криво посчитал. :D
Уважаемые авторы, будет ли разбор раунда. Если да, то когда выложете? Надеюсь быть услышанным.
I mistakenly read the answer instead of output, Sorry for inconvenience.
I can not understand why is my answer wrong for this test case #33. I think that my answer is right, Any helps ??
408 765
My output is:
YES
0 0
360 192
-360 675
System test checker says "wrong answer side of a triangle is parallel to OX or OY".
Because it's the correct answer, not yours.
Never mind. PraveenDhinwa mistook the answer for output.
Yep, exactly. PraveenDhinwa posted the jury's answer for that test which is, of course, correct.
Yes, I mistakenly took the jury output :(
Actually I have considered this kind of test case while coding. I made a stupid comparison bug in Java, as this was 2nd time I was using Java.
I made wrong comparison like the below given example:(
Integer a = 3, b = 5; if (a == b) out.println ("matched");
I missed the point that their references are being compared rather than values :(, Nice point to take care in future
After system test fewer accepted problem A than B .. Seems that many don't figure out the third edge can't be parallel to x axis..
Most programs failed on test:
20 15В задаче B на контесте каким-то образом причудилось что длина строки до ста. Так и отправил. facepalm.
Too many hacks on A : /. kmjp reached 63rd place without solving any problem, because he got 15 hacks on A :P. It's a bad thing where there aren't any hacks but in my opinion so big number of people with >10 hacks is also undesirable. I suppose it's a hard task to make such pretests that some solutions can be hacked but not that big number of them :P.
Only problem A is tricky here, if pretests are a little bit stronger then it will be a no hack contest..
not just A, even problem B had a few (~30) hacks!
Div2 C: Can someone tell me why
is not a valid triangle?
в задаче Б див 2 долго не понимал условие. оказалось, так и не понял((( но блин претесты проходит решение, которое считает что нельзя 2 листа разрезать на 3 куска!!!
Если кол-во покупных листов 'a'(для примера) меньше, чем требуемых, то берем все это кол-во 'a' в первый строке. В противном случае берем все нужные листы для 'a'. так делаем для каждой буквы, второй строки. Ну и перед этим воткнуть проверку, что любая буква второй строки, есть в первой.
ну смотри как я думал. представь у тебя есть 2 листа и 3 позиции с таким же цветом. получается тебе надо разрезать эти на 2 листа на 3 куска. как это сделать? отрежем 2/3 от первого листа и положим на 1 позицию. отрежем от 2 листа 2/3 и положим на 2 позицию. останется еще одно место и 2 кусочка по 1/3. я подумал что нельзя склеивать их. и вот щас я прочитал условие и там написано, что необязательно делать одинаковые кусочки. т.е. можно было кинуть в 1 позицию целый лист. а в другие 2 позиции по половинке, например так. но мое понимание условия прошло претесты!!! т.е. в претестах было везде cnt2[i] % cnt1[i] == 0 для всех i! ну вот еще и зеленый((
все для взлома)))
Div2 C: Can someone tell me why
is not a valid triangle?
Edit: got it
6184905
This one is valid. But your ouput is: YES 0 0 9 12 -16 12
Your output
Thank you both :)
It seems the time limit of D was too tight. Many O(N^3) solutions timed out.
Hi, I think it's not. All our good solutions work <= 900, even Java solutions, even with n^3 memory. I think 3 times margin is enough. Of course there are some solutions with huge constant factor that shouldn't pass.
I guess the reason you making the TL so tight is to kill O(N^3 logN) solutions, but it doesn't work well: here
Maybe it'd be better to let O(N^3 logN) pass (and if you think it is too easy, we can use it as 1500p).
In POI there's a rule that constraints should be as small as they can not to let worse solution pass and there also one that making a distinction between solutions differing by a log factor is probably pointless. I guess noboby will be hurt if TL would be increased/constraints would be decreased, so their solutions can pass, because since they are in O(n^3), they deserve to. I'm a follower of an idea that every two solutions in the same complexity are equivalent :P.
Look at this page
The last rated participation in this contest siIlycross
sillycross and tourist both won IOI gold medals...
I wondered what siIlycross was doing...
Failed on all the problems, even tried to hack tourist for many times on problem A...
。
。
。
But finally, I found that siIlycross and sillycross were different people > _ <
It's hard to distinguish “I”(upper i) and "l"(lower L) sometimes on Codeforces...
wonder how siIlycross managed to stay Master despite finishing last! :D
It seems that there is some cap (different for different users), and your raiting can't decrease by more than ~100 points — does not matter how bad your performance is.
For example, look at TMandzu or Zlobober.
hmm, makes sense.
i guess the maximum increase/decrease of rating depends on number of contests user has participated before current round. the higher this number, the smaller the "cap" by which rating can change.
В задаче о прямоугольном треугольнике каким определением параллельных прямых пользовались составители тестов? В используемых в средней школе учебниках (авторы Атанасян или Погорелов) прямая не считается параллельной самой себе. Логично считать, что две вершины искомого треугольника могут находится на одной из координатных осей.
Т.е. если две прямые совпадают, то они уже не параллельны? Боюсь из-за вашего среднешкольного учебника придётся переписывать кучу научных трудов начиная с Евклидовых времён.
Да и если головой думать:
Как задача с таким неостроумным решением могла бы попасть выше чем в Div2-A?
Это довольно циркулярный аргумент.
Что значит "циркулярный"? :)
Ну пусть у нас есть треугольник с вершинами в точках:
Очевидно две его стороны паралельны осям координат. Сдвинем его на 1 по X или на 1 по Y — они всё равно остаются паралельны.
Однако если мы сдвинем его на -1 по X и на -1 по Y, то его стороны совпадут с осями!
Если бы совпадающие прямые не считать паралельными то мы во-первых имеем какую-то глупую сингулярность при сдвиге на (-1, -1), во-вторых сама задача сводилась бы к тому чтобы вывести координаты треугольника с катетами лежащими на осях. Выносить такую "сложную" задачу на соревнование было бы по меньшей мере нелогично.
Я согласен, что нелогично. Но вряд ли аргументом можно считать «если по вашему определению мое определение не работает, то ваше определение неправильно».
Хорошо, перейдём от защиты в нападение — пущай автор вопроса запостит определение паралельных прямых из его учебника — а мы его обсудим.
Я определений которые не допускали бы совпадающих прямых не видел. В том числе в http://en.wikipedia.org/wiki/Parallel_(geometry) .
UPD: Кроме того если совпадающие прямые считать не паралельными, то транзитивность паралельности пропадает. Наверное в свете философии это может иметь какую-то ценность, но в геометрии вряд ли.
Ну а если PAG покажет такое определение, что вы скажете?
Ну а если я приведу источник в котором утверждается что источник используемый PAG не заслуживает доверия, что вы скажете? :)
Вопрос на вопрос не ответ на вопрос. В любом случае, я уверен, что такой источник не заслуживает доверия. Однако не вина человека, что определение, которое ему учили, отличается от общепринятого.
Я и не говорю что человек виноват. Хотя учебника мы его так и не видели. Да и интернеты нынче есть — можно не слишком слепо учебникам следовать.
Но что предлагается-то? Обвинить автора контекста в том что кого-то из участников учили "не так"? Объявить раунд нерейтинговым (по весьма сомнительному поводу)? Требовать от администрации CodeForces всегда уточнять подобные случаи — но их слишком много — в задаче например не говорилось о том что геометрия Евклидова, не уточнялось что речь идёт о декартовой системе координат — а кроме того можно было задаться вопросом, выводить ли слова "YES" и "NO" с использованием кириллических букв E и O...
Это уже утрировано конечно, но действительно почти в каждой задаче есть место "общепринятым" понятиям — действительно, порой оказывается что кто-то использовал нестандартные трактовки (помню и сам прокололся с деревьями состоящими из одного только корня) — но что ж тут поделать.
Я уже указал источники.На пример в учебнике Атанасяна :"Две прямые на плоскости называются параллельными, если они не пересекаются" (п.24, изд.2009г) До этого в п.1 говорится о том, что "две прямые" — эти прямые различны. В предыдущей концепции школьной геометрии(линия учебников Маркушевича) прямая считалась параллельной себе. При этом была сноска о том, что это отличие от предыдущих учебников сделано для того, чтобы упростить формулировку и доказательство некоторых теорем на пример "Через каждую точку плоскости можно повести единственную прямую параллельную данной" или "Центральносимметричные прямые параллельны". Этот вопрос из ряда: "Ноль — натуральное число или нет?", "Единица — простое число или нет". Каждый автор соответствующего курса выбирает то определение, какое удобнее с его точки зрения для изложения. Конкретно по этой задаче я имел в виду, что ДВЕ вершины могут находится на какой-то оси, а не то, что вершина прямого угла совпадает с началом координат.
Please help with my Div1 A submission 6179184.On test 34,on my computer,my solution can give the correct output:
but on CF it gives NO.
I added 0. + to all sqrt's.
6188507
UPD Try to run your original code in "launch" using visual c++ 2010.
Thanks.I used TDM-GCC 4.7.1 on my computer,without -O2,I think that's the reason.
Precision error.
You should never work with floating point numbers when you can work with integers.
Что так массово писали в А, что хорошо ломается и при этом проходит претесты?
У меня гипотенуза была параллельна оси.
Скорее всего, что гипотенуза может быть параллельна осям. И посмотрел пару решений на плюсах в своей комнате, падали если использовали sqrt.
Использовал sqrt, не упало =(
ЧЯДНТ?
Видимо умеешь готовить sqrt :)
Я вот в себе не уверен и чтоб не пофейлиться в целых числах простенько всё сосчитал :D
UPD: вру, у меня нашёлся один sqrt, но его результат я заботливо скорректировал ;)
ну тогда незнаю. Вроде у тех у кого смотрел по финальной табличке, и кто учитывал параллельность гипотенузы, и использовали sqrt упало. У некоторых нет.
Интересно: несколько раз переписывая Div.2 C, под конец забыл добавить главное условие — проверку параллельности координатным осям. Тем не менее, удивительно, но решение прошло претесты. (на системном, естественно, выдало ошибку)
Я понимаю, что на вкус и цвет..., но, как по мне, если красный участник может потратить на решение матча 15-20 минут, после этого уйти — и все равно получить плюс, то баланс проблемсета — оставляет желать лучшего.
У меня обычно TopCoder проходит по такой схеме, "есть взлом — даже красный идет в большой плюс, быстрая 250 без взлома — в небольшой плюс, медленная 250 — в минус". И весь раунд сводится к первым 10 минутам:) А на СF уже привык к тому, что баланса ощутимо больше.
Зато такие матчи удобны для тех, у кого нету времени сидеть до конца)
Пожалуйста, кто-нибудь может объяснить пример
Моя программа выводит:
Правильный ответ:
Почему так ведь:
Если где-то ошибся, поправьте, пожалуйста!
Квадрат длины гипотенузы должен быть 1000^2 + 999^2 = 1998001. У вас же квадрат третьей стороны (960-324)^2+(945-(-280))^2 = 1905121. Он не прямоугольный, очевидно.
Спасибо большое! А я долго думал над ней во время контеста))
how to solve problem C in div1
I decompose a binomial coefficient
for i > l into
Take an array A[] whose j-th element is the k - j-th term of this sum (if i = l, then A[k] = 1 and A[j < k] = 0). When you increment i, A transforms into the array of its own suffix sums, because
where the first term is A[j] of the original A and the second is A[j + 1] after the transformation, which is the recurrence describing suffix sums.
This transformation is also additive — performing it on the sum of queries gives the same result as performing it on each of those queries separately and then summing up the results. That means you can use a sweepline with adding new queries (A[k] + + ) and removing them (you need to subtract bin. coefficients from the corresponding terms of A).
UPD: The exact formulas were wrong, also it wasn't prefix, but suffix sums. The confusion came about because I changed the indexing from the one used in my solution (6186385). Nevertheless, the original decomposition is unchanged.
This is a beautiful solution!
Good solution. But i still dont get how to save queries in each element and find the current element?
Find the current element: sum up the terms of array A — it's the same as computing the sum above.
Adding queries is trivial — just increment A[k] for the k of that query. When deleting queries, you'd need to subtract from A the values that would be there if you applied the same algorithm on only that one query — those are the bin. coefficients in the sum.
может быть что-то не так с чекером ? код 6188589
1 и 3 точки лежат на прямой, параллельной оси х
Гипотенуза параллельна оси Ox
Round Stats & Rating change
it's very Thriller contest 4 me.............
It was a nice contest. :) BTW can someone describe how to solve div-1 C? Edit : Sorry, I missed the Xellos comment.
I already did
I got the email announcing this contest during (or after) the contest!
i still havent got any email. hopefully i'll get it before the start of next contest (which is now less than 48 hours)! :D
Problem Div1 — A, Triangle.
For input 5 5
My program gives the following output.
I got Wrong answer. But two lengths of these three points are 5 and 5. Could anyone help me to find the place where I am doing mistake?
You don't have a right triangle.
Got it.
Thanks :)
div1B не SpaceChem'ом ли навеяна? =)