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

Автор PR_0202, история, 3 года назад, По-английски

Let's discuss the various approaches used to get the maximum points. :)

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

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

Use dp approach

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

We used Alltheirmothers technique.

»
3 года назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится
We actually saw that the skill increases if it's equal to the required one in the last 30 minutes :(
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Reply your scores in this thread ≧◠‿◠≦

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

$$$>$$$ teammate tries int func(project a) { return (a.b * a.s) / a.d; } as a discriminant between projects

$$$>$$$ teammate writes 220 line code sorting those projects by that discriminant

$$$>$$$ teammate leaves

$$$>$$$ "team" gets 3038681 points

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

When will they unfreeze the scoreboard ╥﹏╥

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

Why does it have to take so long to reveal the results? :(

We repeatedly took the task with maximum "score upon completion" / "total hours needed to complete". Used some bipartite matching stuff to find earliest time we can start a task. This was good for 3.486434 million points.

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

    Do you mind explaining the bipartite matching part? We thought about it but got notwhere

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

      We ignored mentoring except in easily solvable special cases, which makes it possible to use bipartite matching to figure out if you can do a job with a given set of people.

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

Not sure if practice is broken, but my solution for D was few mins late https://twitter.com/FakePsyho/status/1496973852093685760/photo/1

Edit: Posting pictures is hard, Got 2M on D in practice

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

    Our story is also the same. No difference.

    Our total would have been ~3754630. Missed potential WFs. :/

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

    Nice! What is your solution doing? Is there something special in the test structure?

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

      No special structure. The trick was in mentoring.

      I believe D was designed in a way that's fully solvable with an extremely narrow path. Each contributor starts with a single skill, but some projects have 2 roles requiring the same skill. Most probably for some of those projects you only have 1 contributor with that starting skill so you have to train another one.

      If all of your people have single skill there two way of learning another skill:

      • If you have 2 roles with the same skill and one of them is lvl 1, you need a mentor + any other contributor (and they will get lvl 1)

      • If you have two lvl 1 roles with different skills, you can take those contributors and swap them: instead of getting (potentially) to level 2, they will become mentor to each other and learn a skill.

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

    Impressive! Could you elaborate on how SA can be applied here?

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

      I didn't do SA, but my teammate (sullyper) did.

      You can do SA on the order of projects. This should work fairly well even if your "matching" (subproblem of finding contributors for specific project) is not fully deterministic. Alternatively, you could add a "seed" to each project that makes matching more reliable. Then, your state transition is either moving projects or changing seeds.

      His SA that ran for 4H got 3.1M (out of ~3.2M max). In my case (random order of projects), I got a score of 2M around once per 1000 runs, but each run took less than 0.1s.

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

This was my first hashcode and I was overjoyed with our performance. Though we did greedy we managed to place ~1K globally (≧▽≦). Edit: Got around 2.4 Million with it

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

What was your approach for F? Its name "Find great mentors" suggested that maybe you should prioritize mentoring somehow, but the obvious approach of greedily selecting people to increase their level or otherwise to select people with lots of skills only got around 250K. How do you get to 500K+?

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

    We got 770k+ on F (on practice) greedily selecting the project which maximizes $$$\frac{score}{timestamp_{completed} \cdot r}$$$.

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

    Priorotizing people with low skill levels got us to 600k

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

Weren't they supposed to announce the finalists by now? Did anyone hear anything from them?

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

Score distribution of qualifier round

Score distribution of subtasks and previous years here. Source files and code here.

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

I made a GitHub repository of solutions scoring more than 5.7M in total (at the moment I write this message)

Input Score at end of contest Score after contest
A — An example 33 33
B — Better start small 897157 1003496
C — Collaboration 228971 242898
D — Dense schedule 251751 2178519
E — Exceptional skills 1640416 1648976
F — Find great mentors 635791 866644
Total 3654119 5940566
Rank 31st 1st