Thursday, November 14, 2019

A six-in-a-row week

Google Code Jam 2019 Final Round was the main event of the Aug 5 - Aug 11 week (problems, results, top 5 on the left). There was a lot of movement at the top of the scoreboard during the round, since we did not know which submissions were solving just the visible input, and which tried to get both. After the dust had settled, things were much less suprising :) Gennady has won it for the 6th time in a row, incredible!

I have prepared the easiest problem in this round, Board Meeting: there are several kings on an infinite chessboard. You don't know neither the number nor the locations of the kings, only that there are at most 10 and their coordinates are at most a million in absolute value. You can send at most 1000 requests, in each request you choose a cell on the chessboard and are told the sum of distances between this cell and the locations of the kings. The distance between two cells (a,b) and (c,d) for a king is max(abs(a-c),abs(b-d)). Your goal is to learn to answer such requests yourself: after you've done sending requests, the judging system will in turn send you 1000 such requests, and for each request you need to reply with the sum of distances from the locations of the kings to the request location.

Can you see how to solve the problem, and why did we use such elaborate two-phase process instead of just asking to determine the locations of the kings?

TopCoder SRM 764 took place on the weekend (problems, results, top 5 on the left, my screencast, analysis). There were five problems instead of the usual three, and the divisions were combined. I can't say I enjoyed this format too much, but I did enjoy solving the cute mathematical puzzle that was the 500-point problem: given four squares that sum to an even number, find four squares that sum to half that number. Can you find a way to do it?

Thanks for reading, and check back for more!

2 comments:

  1. Hi Petr,
    can u tell me the exetension name which you use to create task or file .

    ReplyDelete
    Replies
    1. It's called CHelper: https://codeforces.com/blog/entry/3273

      Delete