Hi,
Can people who quickly solved todays Codeforces Round 468 (Div. 1, based on Technocup 2018 Final Round) please share their thought process? It would be great to know how you reduced those problems to standard stuff so quickly. (Particularly for Div-1 B and Div-1 C, but other questions are welcome too).
Thanks
For problem C, it was something like:
1) How do I know for sure that no point belongs to all segments?
2) Seems like the only way I could know is if I see that a segment started after the end of another segment.
3) How do I know for sure that a segment has ended and another has started after that?
4) Seems like the only way I could know is if F(i) > F(i + 1) and F(i + 1) < F(i + 2), where F(k) is the number of segments point k belongs to. took a few moments to make sure this is the only way, turned out to be trivial to see and prove
5) This means that I should take as many points as possible so that for no three consecutive taken points i, j and k, the inequalities F(i) > F(j) and F(j) < F(k) hold.
6) How does such sequence of points look like? Well, it should be non-decreasing at first and after it reaches some peak point, it starts being non-increasing till the end.
7) Let's fix that peak point and find LIS and LDS.
I couldn't do the contest but when i looked at C(And got logic pretty fast) , this was my thought process mostly:
1. Need to trick player into thinking that the (xi, cnti) sequence given looks like one where there is a point contained in every set.
2.Thats only possible if such that , hence the sequence (xi, cnti) , if sorted according to xi is first nondecreasing and then nonincreasing (The cnti sequence).
3.Just use dp to find this sequence.
My thought process on A:
For problem C, it was something like:
1) Need to trick player into thinking that the (xi, cnti) sequence given looks like one where there is a point contained in every set. 2) Please don't downvote me 3) Seems like the only way I could know is if F(i) > F(i + 1) and F(i + 1) < F(i + 2), where F(k) is the number of segments point k belongs to. took a few moments to make sure this is the only way, turned out to be trivial to see and prove
I think the truth is it's just english skill + luck. English because half the thinking time is spent understanding the problem, and luck because of the other half. (Also luck because it took me 30 minutes to solve A)
Russian skill also helps. Especially when problems are translated word-for-word, and the phrasing becomes awkward. (Also, inflorescences? Whaaaaaaat)
Thought process on Div 1-B, since no one's written it yet.