Problem: 375E - Red and Black Tree
At first, the editorial seems like using black and red in the opposite meaning than the problem. If someone can edit the editorial than it would be good for newcomer because this problem is really an interesting one and many people will learn the concept of integer programming from this at first. (I googled to get some problem on LP and found this. Then read the editorial and a book on IP formulation, and It was really confusing until I really believed, the editorial is not always perfect.)
My solution: 35949315
The time limit is 1s and it passed in 935ms. Is it OK for an LP like this? I didn't wrote the template. And I do not also know its time complexity. There is a entire book on this. Which is not good (for now). Can you give an intuitive idea about the complexity?
I am concerned with 2 cases
1. This maybe with the simplex implementation. Maybe someone can help to verify this if it is good.
2. I used n+2 constraints. I don't know what is the standard technique to replace equality with inequalities without dividing it into 2. Is it the correct approach?
And finally,
Suggest me some problem on linear programming. I have solved 375E, 605C on CF and another one on HackerRank.
Thanks for your time. :)
The simplex algorithm, which you also used in your solution, doesn't have a polynomial complexity. You can construct linear programs for which the simplex algorithm uses uses exponential time.
However in practice the algorithm is really efficient. As far as I know, the simplex algorithm is still used in pretty much every commercial LP solver, despite other algorithm exists that guarantee polynomial runtime.
2) Yes, converting an equality into two inequalities is a good way. Alternatively you could express one variable, and eliminate this variable from all other equaltions by substituting it (same method as solving a system of linear equations). But this complicates all formulas, and is not worth it when you do it by hand.
Is it worth understanding the nature of the problems that will lead to exponential run-time? Or, Should I just hope for good and use simplex anyway?
Thank you for your answer.
No, only if you are curious.
If you want to solve problems, you can just assume that this case will never happen.