Блог пользователя MikeMirzayanov

Автор MikeMirzayanov, история, 9 лет назад, По-русски

Закончен Educational Codeforces Round 1. 24 часа после окончания фазы основного участия многие из вас пытались взломать соперников, и у многих это получилось!

Всего было сделано 573 успешных взлома, а общее число "взломщиков" — 101. Вот самые результативные из них:

Хэндл Кол-во успешных взломов
1 yashkumar18 36
2 halyavin 31
3 TrungPhan 26
4 Orenji.Sora 25
5 ykaya 24
6 NotPassedCET4 23
7 greencis 22
8 kondranin 20
9 Allanur 19
10 bayram98 18
11 waterfall 17
12 kalimm 17
13 muratt 13
14 lifecodemohit 11
15 hnust_zhaozhixuan 11
16 BigBag 11
17 Luqman 10
18 choosemyname 10
19 White_Bear 10
20 liao772002 9

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

Как я и говорил, у меня есть желание краудсорсить разборы с помощью участников. Кто готов помочь с разбором задач C-F, пожалуйста, отпишитесь в комментариях. Конечно, вы должны быть из тех, кто решил эти задачи :)

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

  • Проголосовать: нравится
  • +220
  • Проголосовать: не нравится

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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.

»
9 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

 Really??

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

»
9 лет назад, # |
Rev. 5   Проголосовать: нравится +36 Проголосовать: не нравится

Разбор задачи 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).

Вот и всё :-)

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Вы два раза скинули ссылку на авторское решение D Нет ссылки на авторское решение С

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      Спасибо, пофиксил :). Однако, это не авторские решения, а всего лишь мои, которые я придумал еще во время контеста :)

  • »
    »
    9 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

    Моё решение задачи C:

    1) сортируем по четвертям, а в одной четверти по |a||b|sinθ

    2) проходим циклом и считаем для соседних векторов:

    3) s = ( |a||b|sinθ )^2

    4) c = |a||b|cosθ

    5) l = ( |a| )^2 * ( |b| )^2

    6) if(c < 0) s = 4*l — s //Обрабатываем углы больше 90

    7) if( prevS*l >= prevL*s ){ prevS = s; prevL = l; } //Мы нашли угол меньше!

    Поскольку:

    Скалярное произведение векторов |a||b|cosθ = x1x2 + y1y2

    Косое произведение векторов |a||b|sinθ = x1y2 — x2y1

    Модуль вектора |a| = sqrt(x1*x1+y1*y1)

    То получаем целочисленное решение (без использования вычислений с плавающей точкой). В строках (3) и (5) используем возведение в квадрат, чтоб избавится от корня, в строке (7) приводим дроби к общему знаменателю и сравниваем полученные числители. Так же стоит учесть, что в строке (7) мы получим числа порядка ((10000^2)^2)^2, поэтому надо использовать длинную арифметику.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    Спасибо большое

»
9 лет назад, # |
  Проголосовать: нравится +116 Проголосовать: не нравится

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.

»
9 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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? :|

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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

»
9 лет назад, # |
Rev. 5   Проголосовать: нравится +6 Проголосовать: не нравится

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

:\

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    change doubles to long doubles

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      no change ! :(

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I have the same problem... Can try not to use standard functions of search of a corner, and it is simple to consider y/x? And to use type of data of decimal (if you have C#)? Excuse for bad English, I translated this text through the translator.

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    It simply does not print enough decimal places to show that the numbers are different (expected smaller).

»
9 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    Test 128 is probably one of mine. I just enumerated all pairs of vectors in some area and then sorted all angles between them. Then I looked at all neighbor angles and choose all pairs where the difference is below 1e-15. To avoid precision problems, I used 64-bit integers in calculations — all angles and difference between them can be represented as arctan(p/q). I was only interested in angles less than pi/2, so arctan range was not a problem.

    For test 127, I used enumeration for vectors with coordinates less than 100 and then I noticed the pattern in the worst case. So I created the similar test for coordinates up to 10000.

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +31 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
9 лет назад, # |
Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

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".

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I would like to see F, too. But also I eager to see proper solution for C, because long double does not work for me. I am pretty sure that's because of some build-in functions that I am using, such as "acos" and "sqrt", but not sure enough about this.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      You can see mine. link

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      You have two problems. First of all usage of double — just throw #define double long double on top of code (or use it properly — defines tend to obscure stuff...). Secondly, never ever hard code PI by yourself. Better use M_PI (though AFAIK M_PI precision is not defined in standard...) or even better acos(-1).

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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.

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Problem D: Your 3 nested loops (under long long ans=0) are problem. It can go up to 10^12. In test that your solution fails it is about 10^10 operations. Limit for 1s solution is around 10^8.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 :\

»
9 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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).

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

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

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

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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!!

»
9 лет назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

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 108 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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    I'm not allowed to view the context of the link.

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

      I can't view the link either.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Could you tell me why this would get TLE? https://codeforces.me/contest/598/submission/127645132

      • »
        »
        »
        »
        3 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Two problems:

        • using Strings as keys for a hashset/hashmap is a really bad idea. Working with strings is slow, better use integers (e.g. use a pair of integers, or combine the two coordinates with something like x*width+y or just don't use hashset/hashmap and just use a 2d array).
        • If you do a DFS for one area, you should store the answer for all cells in the area, not just for one. If one cell inside the area gives the answer x, then all others also give the answer x and there is no need to recompute everything.
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Nice trick. I wish I'd come up with that. Instead I decided that it is possible to compare the angles by comparing there respective cos. The bigger the cos, the smaller the angle. And cos(a,b) = dot(a,b)/|a||b|. |a| contains sqrt, so instead we can compare sign(cos(a,b)) * cos(a,b)^2. This way we will no longer need doubles. The only problem is that numerator would be of order 10^16 and so would be the denominator. Because of this I had to resort to using big integers...

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +61 Проголосовать: не нравится

      It is possible to compare fractions using only long long if both the numerator and denominator are at most 1016. Instead of clearing denominators and comparing directly, we compare the continued fraction expansions of the two fractions.

      We look at the integer parts of each fraction first. If they are unequal, then we know which is larger. Otherwise, we can discard their integer parts and consider only their fractional parts. To compare these, we take the reciprocals of the two fractional parts and apply this process recursively. (Note the similarities between this algorithm and the Euclidean algorithm---both run in .)

      My implementation is here: http://codeforces.me/contest/598/submission/14257824

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 .

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is there any update about the editorial ?

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

https://codeforces.me/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.

»
5 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

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.