Parity party - Ad Infinitum18

June 10, 2017

Introduction

It is so exciting to see the computer science professor, Math Ph.D. graduate, and high performer all having great time to play the algorithm, 5 out 100 is also very worthy to go for it.

Julia easily stumbled on simple recursive function on real trial with people through the phone. She needs more challenge problem solving experience, therefore she can solve easy algorithm quickly.

Now it is 5:34 pm, Julia still has more than 5 hours to play the contest. Let her enjoy the algorithm.

It is called parity party. The problem statement is here.

Coding in the contest 

Try depth first search, using recursive function, some pruning technique. 6:49 pm, score 5.0 out of 100. Julia has to go out the play tennis for one hour. And she plans to work on the contest until 12:00 am, and then get up early in the morning to play from 5:00 am to 9:00 am.

Try to use memoization, dynamic programming to avoid overlap subproblems.

Try other ideas.

Keep trying!

Follow up after the contest 

It is Sunday, 12:01 pm. Julia likes to post her code submissions and also wrote something to help herself grow technical skills.

First one is to use recursive solution, score 0. The most important task is to write recursive solution, solve the problem first. Here is the code.

Afterwards Julia spend some time to prune the algorithm, terminate recursion tree early adding some extra checking. Code is here, score 5.0 out of 100.

It is so much fun to understand that how mathematics solves the most complicated problem but a programmer has no clue. Julia read editorial notes and then she was amazed that the difference between a talent programmer and a good mathematician with programming talent.

Here is the editorial note link.