lecxe's blog

Can someone please help in understanding this solution
By lecxe, 11 months ago, In English

Question: https://mirror.codeforces.com/problemset/problem/1906/M

Editorial: https://competition.binus.ac.id/icpc2023/M5xmtK1iPAdXT1t765fbLg5m66d52XuT.pdf

The second part in the editorial where $$$M \le 2 \cdot (S - M)$$$

I read it, but still feel I don't quite get it.
Can someone please help me to understand the math of the second part

  • Vote: I like it
  • -2
  • Vote: I do not like it

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

check this submission : https://mirror.codeforces.com/contest/1906/submission/235469801

→ Reply
»
11 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

M = maximum special points on any side; S = sum of special points;

S-M = special points on remaining sides;

if M > 2*(S-M) => if maximum number of special points is greater than twice the number of special points on other sides then for every point on the other sides there is are 2 points on the side with M special points so the answer in this case is S-M; (must make triangles in the order stated in solution)

else if M <= 2*(S-M) lets consider M is 1 then each side has 1 special point and max 1 triangle can be formed using one side and it's adjacent sides. Now, if M >= 2 in this case then you take a side with M special points (P) and every 2 points here forms the base for the points on the P+1 side, now as P has been used up you have to find the side with next greatest special points and continue repeating the process until M < 2 or S < 3. The answer for this case is floor(S/3) and not S(S-2)/3 i.e. $$$\binom{S}{3}$$$ because you can make triangles in a certain order(as defined in the editorial) and cannot select any three points randomly to make these non — degenerate.

My Submission

→ Reply