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

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

Всем привет!

Сегодня в 20.00 MSK состоится Topcoder SRM 640.

Давайте обсудим задачи после контеста

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

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

Thank you for reminding me, you care about me more than TC : pp.

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

    To everyone who missed this SRM because of the reschedule: add the topcoder event calendar to your google calendar, then check "notify me one day before each event". This even sends out e-mails with your local time zone!

    TC emails have never been reliable, but at least Google has never failed me so far.

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

Hmm, I can't log in.

UPD: Now, I can. Match postponed by 1 hour.

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

According to topcoder event calendar SRM 640 was on sunday, glad I saw your post, thanx.

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

    Something's wrong with the old Topcoder theme events calendar. SRM 640 was on tuesday there some time ago but now it's messed up)
    Looks like new theme calendar is the only choice.

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

An hour delay. Looks like I've no chance to participate =(

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

This java application is the biggest shit that I ever seen.

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

I admit it, problem 550 div1 caused me to waste a lot of paper ,and in the end hasn't solved it!

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

    +1. I wonder how to practise the skills which are required to solve such problems and what the skills are. I tried so many ways to connect the edges and for each of them I realized (not always immediately) that it does not work.

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

      Well, the first thing I realized immediately (this grammatic construction is cool, it has 2 meanings :D): I can draw the first ans vertices on the left, on the right and connect the corresponding pairs.

      Next: one unmatched vertex has to be connected to d matched ones (it obviously can't be connected to unmatched ones), and we can connect all other unmatched vertices to these as well. That's one biclique on each side.

      Similarly, we can make these matched vertices into a biclique with their matching counterparts.

      There are some more steps, like splitting the matched vertices into 2 bicliques, where one of them has d vertices in each part and the other has ans - d, and each biclique has one part connected to n1 - ans / n2 - ans unmatched vertices, and then figuring out that we can make another biclique between 2 parts of these 2 bicliques, but it's hard to explain without pictures. The result is very simple, though.

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

Ну наконец-то нормально SRM написал. Почелленджил все три харда у себя в комнате, room winner и 12 место в диве.

Как 550 делать? Во всех решениях почти одна и та же формула, но я не могу понять, откуда она берется.

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

    О, а не расскажешь как делать 1000? У неё настолько простое условие, что совершенно нет идей, как её не в лоб решать.

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

      Основной факт: если у x[i] и y[j] одинаковый остаток по модулю p, то p прибавляется к ответу с соответствующим коэффициентом (если x[i] и y[j] при этом не равны).

      Теперь решение. Переберем модуль до корня. Для каждого остатка сохраним список x[i], имеющих такой остаток по этому модулю. Для каждого y[j] пробежимся по списку с соответствующим остатком и обновим ответ. Всего операций будет не больше, чем 1000 * 1000 * log(10^9).

      Таким образом мы учли все делители меньше корня. Для того, чтобы учесть остальные, будем хранить матрицу xy[i][j], в которой поддерживать в актуальном виде разность x[i]-y[j]. В конце пробегаемся по этой матрице, если в какой-то клетке стоит не 1 и не 0, то обновляем ответ.

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

    Размер максимального паросочетания равен размеру минимального вершинного покрытия. Назначим x вершин из левой доли и ans — x вершин из правой доли вершинами минимального вершинного покрытия. Проведем из всех вершин ребра к вершинам покрытия из противоположной доли. Всего таких ребер x * n1 + (ans — x) * n2 — x * (ans — x). Нужно найти максимум этой функции.

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

I was very lucky in 550. I made 2 errors in formulas and 2 errors in thought process, but 3 of them "xored" to correct formula and fourth error turned out to be nondangerous xD.

I had sth like  - 2a·ans + 2a2 = a( - ans + a) and I forget to add all edges between two groups of vertices of a and b elements, but in my solution ans = a + b, so difference I made because of wrong formula resulted in having a·(ans - a) more edges and difference caused by forgetting those edges resulted in having ab less edges, but a·(ans - a) = ab, so it all cancelled xD. Moreover I thought that I need to search for a minimum value of quadratic function but I messed up signs and it turned out that it was completely unnessecary, because it was sufficient to check them only on boundaries :P.

But nevermind, got accepted and 6th place :D.

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

Right now, in the practice room on 1000:

Execution Time: 1.288s

Peak memory used: 67.543MB

The code execution time exceeded the 2.000 second time limit.

Uhh... what?

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

Какое решение для див2 1000. Я придумал одно, но не успел дописать. Правильно ли оно или нет?

Мое решение состояло в том что надо найти НОД всех подмножеств и пытаться оптимизировать наш ответ. Если НОД = 1 то за модуль я беру 2(скорее всего это не оптимально).

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

Hello,what is the approach to solve Div1 250?

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

    Remove edges between vertices with the same color and count a number of connected components. Subtract 1 and that's your answer.