Sunday, September 2, 2018

A Skyglow week

Codeforces Round 497 took place during the Jul 9 - Jul 15 week (problems, results, top 5 on the left, analysis). The last 3 problems were, shall we say, more challenging than usual: only 9 accepted solutions for C, 3 for D, and 0 for E. Yosupo was one of those 12 people, and he solved the right set of problems in the right order to claim the first place. Congratulations!

Just a day later, AtCoder held its Grand Contest 026 (problems, results, top 5 on the left, analysis). yutaka1999 was unbeatable on the day, finishing all problems more than half an hour before anybody else. Congratulations on the dominant win!

I found the last problem very nice: two players play a game on an array of integers ai with at most 300000 elements. The players make alternating turns, and on each turn a player takes a number from the array that is not previously taken. Moreover, when possible, a player must take a number adjacent to a number taken by the other player on the last turn. When taking such adjacent number is not possible (on first turn, or after a player has taken a number which has both neighbors either taken or nonexistent), any number can be taken. The game ends when all numbers have been taken, and each player tries to maximize the sum of the numbers they take. Which sum will each player get if both play optimally?

Thanks for reading, and check back for the solution!