Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

rng_58's blog

By rng_58, history, 9 months ago, In English

We will hold Dwango Programming Contest 6th.

The point values will be announced later.

We are looking forward to your participation!

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

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope this contest isnt unrated too.

»
8 months ago, # |
  Vote: I like it +4 Vote: I do not like it

How do you solve task B? I didn't even understand the statement.

»
8 months ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve D?

  • »
    »
    8 months ago, # ^ |
    Rev. 2   Vote: I like it +22 Vote: I do not like it

    I was adding numbers one by one from postion $$$1$$$ to position $$$n$$$. Let's say we are adding currently element at position $$$i$$$ (there is $$$n-i+1$$$ possible values). In case some element can not be right for all other elements (rest $$$n-i$$$ elements have same $$$a_i$$$ value), then put that element on position $$$i$$$. Otherwise put smallest or second smallest element on position $$$i$$$.

    Obviously we can not get smaller lex permutation than this one, but also it is possible that last two elements are bad in the permutation:

    For example case:

    $$$ n = 5$$$

    $$$a = [2, 3, 1, 5, 4]$$$

    My algorithm will give result: $$$[1, 3, 2, 4, 5]$$$ and it is incorrect result. But we can make it better, just pick last three elements and try every permutation — at least one of permatutions will be valid (that is reason because there is no answer just for $$$n = 2$$$).

»
8 months ago, # |
  Vote: I like it -64 Vote: I do not like it

I would had much apreciated to get a "warning" or something before haveing submitted A. Because then I would had read the other problems beforehand, and propably would not have participated at all.

»
8 months ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve C?

  • »
    »
    8 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    There is an editorial available. editorial

    Edit: Just saw that the english version is not available for all problems, sorry.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Here's a nice analogy: you can interpret the problem as follows- There's a $$$k\times n$$$ grid. First you have to distribute $$$a_i$$$ black hokey pucks among the $$$n$$$ cells of the $$$i$$$-th row (for each $$$i$$$). Then you have to distribute $$$n$$$ red hockey pucks on top of the $$$\sum a_i$$$ black pucks such that every column has exactly one red puck. Count how many ways are there to do that.

»
8 months ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve B , i did not understood the editorial

»
8 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Did it say that the English version of the Editorial would come out today?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I still don't know how to solve C

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If you get it from somewhere or translate and understand using the Google-Translate Api then please share it here.

»
8 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Hi, it's been more than a day and the editorials are not out, as promised. It would be great if you could upload them since the questions were interesting :)

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem B editorial how to prove the probabilities stated are correct. For example it is given In order for Slime i − 2 to cover the section from xi to xi+1, both Slime i − 1 and i need to be chosen earlier than Slime i − 2, so pi,i = 1/3. How to prove it ?

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Where can we see the data? I found that it isn't in the dropbox...

»
8 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

can someone please explain the solution for problem C? I am not able to understand tutorial for the problem