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

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

Всем привет!

Завтра, в 15.00 MSK состоится Topcoder SRM 625.

Предлагаю после контеста обсудить здесь задачи.

GL & HF

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

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

[topcoder] Single Round Match 625 is dedicated to [topcoder] member Harsha Suryanarayana known under his handle humblefool. He tragically died after being hit by a car on June 15, 2014. humblefool was a [topcoder] member since October, 2005. During his more than 8 years with [topcoder], he competed in 238 algorithm matches where he reached red rating in October, 2007. At the current moment, Harsha is the highest rated [topcoder] member in algorithm track among all 2281 active coders from India. He was also very active in component design track, submitting in 86 competitions and winning 45 of them.

The match will award $5,000 in prizes in honor of humblefool. The prizes of $200 will be awarded to best 20 performers in Div-1 and the prizes of $100 will be awarded to best 10 performers in Div-2. All members will be given an option to donate their prizes to Harsha's wife.

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

    My sincere condolence to family and friends.

    I will probably get lots of minuses, but I need to say it being student of courses about ethics and irrational human behavior.

    I don't think it was a good idea of offering prizes with such option attached. It's like a prize money given away, but if you keep it you are of low morale qualities. So you do can take it, but if you take it you are an a@#$ole. I don't have anything against donating prize money (I am thinking about doing pledge about my own prize money if I ever win anything in the future), but I think in this particular situation TopCoder puts winners in "moral hot spot".

    Much better option would be something like this (IMHO): - as humblefool was an inspiration to many many Indian coders; - as he was very good at TopCoder competition;

    why not something like:

    "TopCoder donates $10 to Harsha's wife for every previously registered Indian coder participating in SRM 625".

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

      I don't know what other countries do in this situation when I read this mail from topcoder (the mail I wrote above ) I was confused a little bit this man die and you distribute gifts to contestants I know ~90% of winners will check to donate Harsha's wife but really this situation is strange to me too
      but I believe that they have a good intentions or as I told maybe different cultures.

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

        Being an accountant, my first thought was that this is somehow related to taxation issues — maybe Topcoder as organization can claim prize money as tax-deductible expenses, but can't do the same for donations. But if they "distribute" prize money to contestants and then contestants choose to donate, that might mitigate tax risks for TopCoder.

        If this is the case, I can understand that, but for many people it looks awkward.

        Side note — above theory is a good example of what being professional accountant does to your brain.

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

How was Div2 C to be solved?

EDIT: Just found the editorial written by vexorian.

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

Оффтоп: сегодня решил написать на новой машине. Все настроил вроде бы через moj. Однако, темплейт взял какой-то левый, которым раньше не пользовался. Как побороть проблему с isnan isinf (слышал раньше, но сам не сталкивался)? Все возможные инклюды(cfloat, float.h, cmath, math.h, climits, limmits.h) подключены.

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

How to solve Div 1 problem B ?

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

    Max-flow min-cut

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

    We can use maxflow. Build a graph, whose vertices are elements of a given grid that are reachable from '$' by several steps of length 3, and edges are between vertices separated by two elements. Edges may have capacity 0, 1, 2 or INF (it depends on the number of '.', 'H' and 'b' between two vertices) and vertices may have capacity 0, 1 or INF (means 'H', '.' and 'b').

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

      For the second round in a raw they set VERY standard problems for 250 and 500. It looks really strange.

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

I believe Div1 500 was inspired by http://www.bloxorzgame.com/

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

How to solve 900 Div 1?

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

    Let's fix the position of the first element: we have n choices to do that. z[1][1] = n

    Now if we fixed i elements and have j groups for the next element we have three choices:

    • New element will merge some two groups: z[i + 1][j — 1] += z[i][j] * j

      coefficient is equals to j because we can choose what two neighboring groups we will merge

    • New element will be in a new group: z[i + 1][j + 1] += z[i][j] * j

      because we can choose between what two neighboring groups we insert new group

    • New element will extend some group: z[i + 1][j] += z[i][j] * j * ((i + 1 == n) ? 1 : 2)

      coefficient 2 because we can choose from where extend group: left or right

      coefficient j because we can choose what group extend

    In the end we should sum z[k][i] for all i from 1 to g with coefficient C[n — k — 1][i — 1] for positions of spaces