https://codeforces.net/contest/234/problem/G
This problem is the type of problem where I know everything needed but I still can't solve it. I always learn a lot from such problems
I am not interested in a solution, I know it, but how to approach the problem and reach a solution. How to think about it? What should have hinted me to consider using what was needed to solve it ?
The name of the problem says it all
234G - Practice
How to practice ? Are all ways of practice equally good ? Will any kind of practice pay off ? When I try to think about a problem which I didn't know how to solve to locate my gaps, aren't this practice ?
I just hate when someone answer "Practice" Wow, thanks genius \ This is the most stupid answer to a question, I have ever read.
My Thought process
Okay so, basically we need two groups such that matching between them is maximum possible.
It makes sense to make the size of the groups as equal as possible so that max number of edges may exist between them.
Okay, so if we do that, every player of one group will already have played with all the players of the other group and now should play against the players of his own group. Hence the problem is divided in $$$\left \lceil{\dfrac{n}{2}}\right \rceil$$$ and $$$\left \lfloor{\dfrac{n}{2}}\right \rfloor$$$ individual problems. Divide and Conquer Now I just need to merge, Since the matches are held in parallel, I guess the number of matches will be max of left and right, + 1.
Oh come on, I also need to print now. Okay, I guess Matches are held at each level of recursion. Hence I can store them level wise in a vector.
The maximum depth should be $$$\left\lceil{\log_{2}(n)}\right\rceil$$$. But lets just create a vector of size 1000.
Me after expanding all of your spoiler tags
PlagiarismInspirationCan you implement this solution ?
Implementation