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

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

Всем привет!

Как уже многие знают, 13 сентября в СГАУ состоялся отборочный контест на четвертьфинал мира по программированию. Разумеется, мы не только развесили плакаты о мероприятии в стенах родного университета, но и сделали множество репостов в контакте, а также пообщались лично с тренерами других вузов, так что популяризация ACM в Самаре вышла на новый уровень. Помимо этого, в отличие от некоторых других организаторов некоторых других отборочных соревнований, мы неизменно выкладываем наши контесты в публичный доступ на тренировки Codeforces, где абсолютно любой желающий мог бы их решать. Так что уже в эту субботу, 14 ноября, в 11.00 MSK все желающие смогут проникнуться неповторимой атмосферой нашего отбора.

Контест пройдет в тренировках Codeforces, будет нерейтинговым и будет длиться 5 часов. Задачи готовили craus и Shlakoblock.

А вот полный список наших предыдущих контестов:

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

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

ummmm..... gym contest :D

tnx dalex :D

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

Reminder: the contest starts in 10 minutes.

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

you write solutions on C++ it regularly happens than input reading through std::cin appears to be slow because of the large input size. Certainly is more correct in such cases to write data reading more effectively — at least using scanf. But if the testing system uses GNU C++ (checked on MinGW 4.4.1, but I think it works on other versions too), and you don't want to rewrite input reading, it is possible to improve performance by only one line placed in the beginning of the program: ios_base::sync_with_stdio(0).

On my example where it was required to find the sum of one million integers, it has accelerated the program in 4.5 times. Tried to do the same test on MS Visual C ++ 9.0 — but it hasn't accelerated the reading.

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

How to solve A and H?

In H, my team were thinking of drawing all lines connecting points P1, P2 and origin. Then, the original circle is divided into 6 arcs and then applying ternary search on each arc about where the new circle should touch the arc. For evaluating maximum radius if new circle is touching at certain point on the arc, we can apply binary search on the radius of new circle.

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

    H: Show that the largest circle always touches the boundary of the garden. Binary search the radius. Now for a fixed radius r we know that the answer lies on the circumference of the circle with center (0, 0) and radius R - r, where R is the radius of the garden.

    So we are only interested in the polar angle of the answer. Notice that if this angle is atan2(y1, x1) + PI, we get the most distant point from (x1, y1) we can get. Find such delta that angles from atan2(y1, x1) + PI - delta to atan2(y1, x1) + PI + delta are distant enough from (x1, y1), and the rest of the angles are not. You can do it with another binary search or with acos, but don't forget that sometimes the whole circle is good and delta = PI, and sometimes even atan2(y1, x1) + PI is not good enough.

    Now we have two ranges of angles. Those that are good for (x1, y1) and those that are good for (x2, y2). If the ranges have at least one common angle, this radius is good, else it isn't.

    A: For each guy, calculate how much he owes minus how much he is owed. For some guys the number will be positive, for some guys negative. The sum is, of course, zero. Greedily connect the positive guys with the negative ones.

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

    I finally upsolved H, and it turned out to be very easy. Solution above is written on drugs, so this is the normal solution.

    Solution of H

    I'm surprised many high rated people couldn't solve it. People should learn that "geometry" doesn't mean "hard".

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

How to G?

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

how To solve problem K?

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

How to solve C?

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

How to solve problem B? Thanks you :D

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

    Use map to keep how many times each pattern appears.

    Make sure you ignore the judge who includes more than 15 or less than 8 tasks

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

How to solve J and L ?

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

How can I solve problem C, please?

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

how to solve A?

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

How to slove B and L ?

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

    The problem L can be solved using extended euclidean. You will divide it into 3 cases.

    1. $$$n*x = m*y$$$ -> answer is $$$LCM(n, m)$$$

    2. $$$n*x + 1 = m*y$$$ -> solve: $$$m*y - n*x = 1$$$

    3. $$$n*x = m*y + 1$$$ -> solve: $$$n*x - m*y = 1$$$

    You need to treat individually when $$$n = 1$$$ or $$$m = 1$$$.

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