Google Code Jam 2017 Round 1A

Google Code Jam 2017 Round 1A screen cast by eddy1021

Top 1000 to advance to round 2. A chance to practice before a bunch of contests.

A is a nice (maybe implementation) problem. Given a 25x25 table where some cells already filled with 'A' to 'Z', you should replace all '?' into one of 'A' to 'Z' which already exists. Such that, for each kind character, it occupies exactly a rectangle field.
For each row, we can expand each character to left and to right. Then, for each raw which contains at least one non-'?' character will satisfy the condition. Then, just expand each row to those all-'?' row.

B is maybe a reading test problem. I can't understand the problem well. Just implement something can check whether it matches the answer...
The problem is equivalent to: Given n kinds of intervals set, each contains p intervals, you should find the maximum number of match s.t. for each match, it contains each kind of interval once and their intersection isn't empty.
Sort each intervals in each kind. Then, we can use something like n-pointer. To keep finding next possible match.

C is a nice problem. I can't solve it during contest and only 8 correct submissions on it. Given a game with six parameter your health, your attack, opponent's health, opponent's attack, buff, debuff, for each round, you go first and can choose to 1. cure yourself, which will set your health back to original 2. buff your attack, which will increase by buff 3. debuff opponent's attack, which will decrease by debuff and at least 0 4. attack your opponent whose health will decease by your attack. Then, Your opponent will attack you for each round. You should determine the minimum round you can defeat your opponent or says it's impossible.
The best strategy is first debuff several times, buff several times, then, attack until your opponent lose. Also, you should choose to cure whenever you are going to die. Thus, for small, just iterate all possible times for debuff and buff, then simulate the procedure. For large, we can find that buff and attack has some relation and they are independent with debuff. Therefore, we can first find the minimum number of times of sum of buff and attack which can be done in O(sqrt{10^9}). Then, we can first that useful number of times of debuff is O((10^9)^{1/3}). Since if your opponent's attack is x or x - d both will lead to you should cure every t times, then just consider your opponent's attack being debuffed to x.

Get 75 points and rank 24 on final standing. Should stay strong for following rounds!