DIV1-375E and Integer Programming

Revision en2, by shakil.ahamed, 2018-03-04 23:35:01

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. :)

Tags simplex, ip


  Rev. Lang. By When Δ Comment
en2 English shakil.ahamed 2018-03-04 23:35:01 2 Tiny change: 't is good.\n2. I use' -> 't is good. \n2. I use'
en1 English shakil.ahamed 2018-03-04 23:33:41 1318 Initial revision (published)