Shafaet's blog

Game Theory Contest in HackerRank
By Shafaet, history, 9 years ago, In English

Hi Codeforces Community,

HackerRank is going to arrange a game theory educational contest on May 13th.

The contest will be 5 days long. In each day we will release 2-4 problems. The first day will contain adhoc games, the second day will contain Nim games, the third day will contain Grundy games and last two days will contain some interesting games involving DP, greedy and Mathematics.

The problem-setters for this round are allllekssssa, forthright48 and me. Thanks to wanbo for helping to prepare the round.

The contest will be interesting to anyone who just started learning Game Theory. Last two days will contain interesting problems for everyone.

Top 10 in the leader-board will get a t-shirt.

Hope everyone will enjoy the contest!

Happy coding.

Update: The contest is starting in less than an hour.

Update: The contest has ended. I hope you learned something new from this contest. The editorials are now available. Please share your opinion in comments.

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

Comments Comments (24)
| Write comment?
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I have your bangla tutorial. Is there any other good source or advice to learn another game theory you can provide which could be included in the contest? thanks in advance.

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

vhaia can not access your blog.any reason??

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

    There is some problems with some plugins, front page is not loading but articles are fine. I am trying to fix. Sorry.

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

Guys, let's wait the beginning of round :D I think that contest covers all important topics about game theory in usual competitive programming.

I would like to hear opinion about tasks at the end of round ( I think whether we should add more tasks of some certain topic ) or we forgot something completely :)

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

Why did you put this link — http://www.timeanddate.com/worldclock/fixedtime.html?msg=HackerRank+Game+Theory+Contest&iso=20160513T17&p1=%3A, now I see that the contest is running?

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

    Ooops! Extremely sorry, I am putting the right link now.

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

Thanks for this interesting concept. I'm having a lot of fun with this contest, and with my knowledge of game theory (not much beyond basic Nim) I know I'm going to learn a lot!

One comment — in a contest like this where problems are released day by day, it doesn't really make sense for the scoring tiebreaker to be time of last submission. Basically this means that time taken on any day except the last (2 problems) is irrelevant. If there are prizes for the top 10, wouldn't other tiebreakers would make more sense?

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

    XD The day after I post this, I cannot start the contest until an hour after problems are released. Yeah for a multiday contest it doesn't seem realistic to assume everyone can be on time each of the 5 days, so I guess I don't know what the best scoring method is. Any other ideas?

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

      Thanks for your opinions. As this an educational round, we are not really very worried about scoring, the t-shirts are for some extra encouragement.

      I will interested to hear if someone can give a great solution for scoring problems in multi-day contests. What should be the best way to break ties?

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

        I agree with waterfalls, scoring is not adecuate for this kind of competition. One idea might be decreasing score throuhg time (with different starting scores)

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

        I think that scoring like Week of Code is good for long contests. We have cheating but top 100-200 participants don't need worry about it.

        Also for my opinion the best option is contest with approximate task, but that tasks aren't usual on rounds and also I think it is harder to invent and prepare such task.

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

Thanks for such great contest! I have been looking forward to learning game theory for some time

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

    Thanks. Hope you will become purple soon :D.

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

Please share your opinions. Did you like the contest or was it bad? More importantly, did you learn something new? The editorials are good enough?

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

    The problems were really good. Especially the last few. This contest was focused on Game Theory. Would it be possible to have more educational contests like this, for other topics (eg. Strings)? :)

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

      Thanks for comment, feedback is really important for us ! If you have some advice about round and you think something was wrong, tell us :)

      I don't know whether HackerRank is planning to organize more contests like this. At beginning we were thinking about several topic and decided for this one, because for my opinion it is the most interesting.

      Our ideas for contest were graph theory, greedy, dynamic programming. Strings are very useful topic, I don't have a lot of experience about it, except hashing :)

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

      Thanks for your feedback.

      We have plans to arrange more educational contests in HackerRank :).

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

    I thoroughly enjoyed the contest. Added concepts like mex, nim-addition, grundy numbers, colon principle to my bag of tricks.

    I felt five days was little longer the contest could have been for three days with reduced easier problems. Also did not understand why some problems did not have higher constraints. e.g. Deforestation could have had higher constraints.

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

Can someone help with the proof of optimal moves for day 4 — fun game ?

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    I solved it like this. Consider player 1. He wants to maximize (A[i] of the positions P1 takes) — (B[i] of the positions P2 takes). This is same as (A[i]s of the positions P1 takes) — (sum of B[i]s — B[i] of the positions P1 takes). This reduces to (A[i]+B[i] of the positions P1 takes) — constant. So he wants to maximize the sum of A[i]+B[i] of the positions he chooses. Please let me know if this seems incorrect. :)

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

    My proof is same as satyaki3794 proof, but maybe if you didn't understand his words, here is my proof :

    Let's value SumA= A1 + A2.. + An If first player choose indeces (i1, i2..., ik) and second player choose indeces (j1, j2.., ju) then Ai1 + Ai2 + ... + Aik = SumA  - Aj1 - Aj2 - ... - Aju

    Now we need to check following two sums SumA  - Aj1 - Aj2 - ... - Aju and Bj1 + Bj2 + ... + Bju and it is obviously equal with checking SumA and sum of values Aji + Bji . So the optimal strategy for first player is choosing maximum Ai + Bi.

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

The contest was nice with set of good and new problems.The Editorials are super awesome. Hope to see more such contests coming !!

→ Reply