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.

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.

There is a good tutorial to start in topcoder, just search in google. Also you can read this book http://www.stat.berkeley.edu/~peres/gtlect.pdf.

http://www.suhendry.net/blog/?p=1612 I learnt some variations of nim from this blog, you can try this too.

You can read this too...

http://www.math.ucla.edu/~tom/Game_Theory/Contents.html

Thanks

vhaia can not access your blog.any reason??

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

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 :)

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?

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

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?

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?

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?

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)

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.

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

Thanks. Hope you will become purple soon :D.

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?

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)? :)

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 :)

Thanks for your feedback.

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

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.

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

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

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

Let's value SumA=

A_{1}+A_{2}.. +A_{n}If first player choose indeces (i_{1},i_{2}...,i_{k}) and second player choose indeces (j_{1},j_{2}..,j_{u}) thenA_{i1}+A_{i2}+ ... +A_{ik}= SumA -A_{j1}-A_{j2}- ... -A_{ju}Now we need to check following two sums SumA -

A_{j1}-A_{j2}- ... -A_{ju}andB_{j1}+B_{j2}+ ... +B_{ju}and it is obviously equal with checking SumA and sum of valuesA_{j}_{i}+B_{j}_{i}. So the optimal strategy for first player is choosing maximumA_{i}+B_{i}.The contest was nice with set of good and new problems.The Editorials are super awesome. Hope to see more such contests coming !!