Можно ли узнать распределение взломов по задачам?
P.S. Впечатления от раунда только положительные! Было интересно решать предложенные задачи.

The idea of educational rounds is very good, i think many div2 users will learn a lot from this rounds.
Thanks for this type of rounds.

eagerly waiting for Educational Codeforces Round 2 :) I think it was really a great idea :) thanks mike :)

Если существует авторское решение по С, можно ли его посмотреть?

Really??

Nice round though. Looking forwards to Educational Round #2 :)

Разбор задачи C.

Найдём все углы относительно вектора 0 1. Например:

Так найдём углы всех векторов. К примеру, мы получили следующие углы (я указываю в градусах, хотя в решении они будут в радианах, поскольку стандартные функции возвращают значения именно в этих единицах):

180 60 45 30 20 90 1 358 15

Сортируем значения:

1 15 20 30 45 60 90 180 358

И самое главное, не забудем добавить в конец минимальный угол + 2 * PI (в градусах — 360 градусов):

1 15 20 30 45 60 90 180 358 361

Всё, что нам осталось сделать — это отыскать минимальную разность между соседними элементами (в моём примере это 358 361.

И ещё. Необходимо всё хранить в long double. Точности double, как показали взломы, не хватает.

Итоговая сложность: O(n log n)

Код: 14237043

Разбор задачи D.

Для каждой пустой клетки мы найдём количество картин, которые мы из неё можем посмотреть. Для примера

*****
*...*
*...*
*..**
*****

количества равны

0 0 0 0 0
0 2 1 2 0
0 1 0 2 0 
0 2 2 0 0
0 0 0 0 0

Теперь с помощью DFS или BFS мы разделяем карту на области так, чтобы из клеток одной области нельзя было попасть в клетки другой. Далее мы считаем для каждой области суммарное количество картин во всех клетках области.

Теперь, чтобы посчитать ответ для очередной клетки, мы должны определить, к какой области она относится, и вывести суммарное количество картин во всех клетках этой области. Так как мы предпосчитали это всё ранее, мы сделаем это за О(1).

Итоговая сложность: O(n * m + k)

Код: 14233048

Разбор задачи E.

Эта задача решается с помощью динамического программирования.

Пусть dp[i][j][k] — минимальная стоимость, чтобы съесть k долек из шоколадки i на j. Как же мы будем считать эту динамику?

Начнём с начальных значений.

1. Если i * j < k, то dp[i][j][k] = INFINITY.

2. dp[1][1][1] = 0.

3. dp[i][j][0] = 0.

4. Также необходимо найти начальные значения при i = 1 и j = 1. Но это связано с основным решением, так что об этом позже.

Теперь перейдём к основному решению. Пусть у нас есть шоколадка i на j. Как мы модем её разделить? Пусть мы будем ломать шоколадку вдоль верхней границы (см. рисунок).

Переберём все возможные высоты верхней части (ni на рисунке). Это значение будет от 1 до i - 1. Тогда высота нижней части равна i - ni. Также переберём nk — количество долек, которые мы съедим в верхней части (может быть от 0 до k). В нижней части мы съедим k - nk долек. Длина разреза равна j * j. Итак, ответ на этот вариант — dp[ni][j][nk] + dp[i - ni][j][k - nk] + (j * j).

Перебор разрезов вдоль левой границы осуществляется аналогично.

Ответом будет минимум из всех таких возможных вариантов.

Теперь про случаи с i = 1 и j = 1. Они аналогичны остальным случаям, за исключением того, что резать можно только вдоль одной из сторон.

Код: 14234802

Итоговая сложность: O(t + mn ^ 3 * mk ^ 2) (mn — максимальное значение m и n, mk — максимальное значение k, в условии mn = 30 и mk = 50).

Вот и всё :-)

Is it possible to extend this idea to normal round? It's ok if the in-contest result are kept the same (and used to update rating). But for training purpose, I believe it's better if we can have improved tests. On many occasions, it was found after the round that test data is weak and it seems no one does anything about it.

It was so interesting for me. Maybe next time it should be rated. xD

I think I would also like to see data on each problem and the amount of hacks it received.

Can someone please explain how to solve the 3rd question?

I sorted all the vectors according to the angles they make with the X-axis, and then just checked the angles between consecutive (sorted) vectors, and also checked the angle between the first and last vector at the end.

But, I'm getting Wrong Answer for the test case :

4
-6285 -6427
-5267 -5386
7239 -3898
7252 -3905

I know my logic is right, but how to handle cases where the difference between angles cannot be taken properly in double? :|

Guys, here is the bug: after someone hacked one of my solutions, I still see on contests page like I solved 4 problems:

Very interesting; 1-day hacks + crowd-sourced editorials. Post upvoted immediately!

problem C : Can someone please tell me why my answer for test case number 127 is wrong ? :\

this is my solution : 14235169

4
-9901 9900
-10000 9899
9899 9801
9899 9900

my answer is : 1 2

jury's answer is : 3 4

angels of vectors is :

135.002893580
135.290809791
44.714977661
45.002893872

angel[2] — angel[1] = angel[4] — angel[3] = 0.287916211

:\

I think my idea for problem C is quite simple and easy to understand.

I split the vectors into 2 sets, vectors with +ve y and vectors with -ve y, then take 2 reference vectors which I chose the vector ( 1 , 0 ) and the vector ( -1 , 0 ). then I calculate the angle between each vector and the chosen 2 reference vectors. and then sort the vector by their angles between the first reference vector. so the answer will be one of 3 cases.

1. the minimal difference between the angles of 2 consecutive vectors in each set.

2. the first vector in each set if the sum of their angles less than the minimal angle calculated in 1st step.

3. the last vector in each set if the sum of their angle "the angle between the 2nd reference vector" is less than the minimal angle calculated in the last 2 steps.

This is my code 14260106 to fully understand the idea.

For test case #119, this is what I can see :

link

It's written that : v1=1.47669e-008 v2=1.47669e-008

and still it's showing wrong answer! is it a bug?

thanks for this great idea :)

Who did discover test case #128 in problem C, and how he came up with this evil test case?

and how to avoid double errors in the future? :D

Mother of geometry!! only 30 solutions accepted in C, and 1 in F !!!

Lesson learned: use long double when you have enough cpu-time and memory. Don`t be cheap...

На контесте было написано 4 задачи. Одна упала. В списке контестов осталось 4 решенных вместо 3-х.

Solution verdict: WRONG_ANSWER

Checker: v1=0.761852 v2=0.761852

wrong answer Jury answer is better than participant's :-)

Precision inaccurates are sad. It looks like that correct solution have to have "long doubles".

Want to see task F editorial. (btw, nobody solved it during contest)

This may be a dumb question but what was exactly "educational" about this round?

I am personally think that it is perfect idea to create rounds like this. Especially after failure on ACM ICPC, I am able to prepare carefully. I think rounds should and even must go on! I also think that it is good idea to show authors solutions and more rigorously explain solutions and ideas than in usual Codeforces rounds. My thoughts base on the fact that it is generation of young people in Estonia and Ukraine who do not have trainers, therefore, it is one the awesome possibilities to support their eager to be involved in Competitive Programming world. Special thank you for open hacks round, because many weaknesses were found from both sides.

I don't think using float in solving problem c is accurate( including atan2/acos etc.),That's why I use only integers.I'm wondering how is the standard solution written.My solution 14247557

Can someone please tell me what's wrong with my code for:

Problem C: https://ideone.com/OlaPog passed the pretest, then got hacked. Now it is stuck on test 45

Problem D: https://ideone.com/Z0fT1R got TLE on test 10

Thanks.

My solution for Problem F : main idea is to find where the cutting line intersects with polygon sides.. then we sort those points of intersection by X then Y..the line enters the polygon at the very first intersection point then gets out at the second intersection point then enters again and so one.. so we need to sum lengths of periods inside the polygon and this should be the answer if there's no corresponding lines ,but unfortunately there is :P try to figure out how to deal with corresponding lines ..if u couldn't this my code CODE if u still can't then lets all hope for good editorial because i'm suffering to explain the solution in english :\

There's a problem: The contest area shown that I have solved 5 problems for this round, but actually I have only solved 4 problems (my C got hacked).

А процесс взломов же можно автоматизировать например вот так:

Взять код человека с высоким рейтингом и какого-нибудь другого, затем начать стресс-тестить (скажем на ~1000 рандомных тестах).

Если разные ответы — то попытаться взломать тестом другого, если у него ок — то ломаем высокий рейтинг и переходим к следующему по рейтингу.

Минус такого подхода — если ответов несколько, то мб. надо что-то делать под конкретную задачу отдельно. Но на мой взгляд, разные ответы — это редкое явление.

Круто было бы, если бы через API можно было получать код решения и ломать его :)

I really think that having a 24-hour hacking period really helps the problem set to gain the best test cases(Perhaps we can extend this to other Codeforces rounds?). After failing several test cases that's well over a hundred, I really do think that the idea to open manual hacking to everyone over a long period of time, and allowing the hackers to copy-paste code for local testing, are undoubtedly the best decisions made on creating this round. It's amazing to see some short test cases but got tons of people WA verdicts. Without a doubt, this is the best way to gain best test cases for contests!

Great round and great rules, cheers!!

Problem C. Editorial.

The author solution works only with integers, so there are no precision problems. Firstly we should sort vectors by quadrants (or by semiplanes). Then we should sort all vectors in quadrants (semiplanes) by cross product sign.

Now we have some answer (a, b) and want to update answer by pair (c, d). Let's consider new coodinate system where vector b matches to x axes: the coordinates of vector b will be (dot(a, b), cross(a, b)) and also we should take cross(a, b) by absolute value, because we need the smallest angle between vectors. Let's do the same with vectors (c, d). The length of vector b can differ from length of vector (dot(a, b), cross(a, b)), but it's doesn't matter.

So now we have two vectors (dot(a, b), abs(cross(a, b))) and (dot(c, d), abs(cross(c, d))) with coordinates at most 10⁸ by absolute value. So we can compare them by quadrants and cross products and update answer.

14264085

P.S.: Validator in this problem is also user only integers and the same comparator.

Для краудсорсинга разборов можно использовать механизм wiki (тем более это соответствует духу сайта). Дать доступ на редактирование всем людям из первого дивизиона + тем, кто вызовется из второго. Выделить каждому прошедшему контесту и каждой задаче по странице. В итоге можно было бы получить разборы даже тех задач, для которых он не предполагался (например, 589L из четвертьфинала ACM).

my solution was wrong just for PI ... WA: 14235457 AC : 14265438 :(

For Problem E:

my approach is to go after k =min(k, w*h-k) through cutting the current bar from its width(the shorter side) with just rows from height enough for the next bar size to be above the required k by modifying height h = ceil((float)k/w) and calculating the cost in my way.

why this greedy approach fails?

verdict: WA on test 2. solution: 14270061

I hope there will be an editorial eventually .

101 people..? That's kinda unusual number lol.

For problem B: the constraints where small enough for brute-force, resulting in an solution, but this problem can be solved in expected time using an implicit cartesian tree, which would allow inputs with m, |S| upto, say, . Here is my accepted solution: 14232624.

Eagerly waiting for the editorials. When will it be posted?

Is there any update about the editorial ?

where is the editorial ? can someone plz give me the link for editorial I m not able to solve the problems.

https://codeforces.net/contest/598/submission/42694507 Somehow I use disjoint set in problem D, I've got TLE in test #23. Could anyone explain for me.

My idea : Using disjoint set to find connected components in the graph. While unifying disjoint set together I calculate the number of pictures of each component, which is the sum of the number of pictures in each cells.

Unfortunately I wasted a lot of time on problem (C), don't make the same mistake I did: you may know both formulas

$$$\lvert u\cdot v \rvert = |u||v| |\cos\theta|$$$

$$$\lvert u\times v \rvert = |u||v| |\sin\theta|$$$

And theoretically you could use either of them to distinguish between angles. However if test cases 1xx are giving you wrong answers due to floating point precision, then it will be wise to choose one over the other; as an example, let $$$\delta, \epsilon$$$ be very small angles like .0001 and .0002. Then it seems we can tell that $$$\delta<\epsilon$$$ either using $$$\cos\delta >\cos \epsilon$$$, OR because $$$\sin \delta < \sin \epsilon$$$. However one of the functions $$$\sin$$$, $$$\cos$$$ is much better, and that's because of derivatives. Notice that $$$\cos$$$ is very flat near $$$0$$$, while $$$\sin$$$ is almost the maximum steepness. So computationally it will be harder to use $$$\cos$$$ to tell which is bigger. Similarly if you are dealing with two angles near $$$\pi$$$. So in those cases it is better to use the cross product.

On the other hand, cross product is not always safe! The writers could also force a precision error by having 4, $$$u,v,w,z$$$ which are very small perturbations of the 4 main directions. In that case, $$$\cos$$$ would be better at detecting small differences.