chrome's blog

TopCoder SRM 625
By chrome, 10 years ago, translation, In English

Hello, everyone!

Tomorrow will take place TopCoder SRM 625. Don't miss!

GL & HF

  • Vote: I like it
  • +40
  • Vote: I do not like it

Comments Comments (17)
| Write comment?
»
10 years ago, # |
  Vote: I like it +22 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +87 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +20 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 2   Vote: I like it +14 Vote: I do not like it

        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.

        → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

How was Div2 C to be solved?

EDIT: Just found the editorial written by vexorian.

→ Reply
»
10 years ago, # |
  Vote: I like it +7 Vote: I do not like it

How to solve Div 1 problem B ?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Max-flow min-cut

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

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

      → Reply
»
10 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it +11 Vote: I do not like it

How to solve 900 Div 1?

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 5   Vote: I like it +8 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -12 Vote: I do not like it

      Can someone please explain why this works?

      → Reply