Can’t guess why many have failed just one TC.
Solutions of Tester,setter and Editorialist are not visible. Please update them ASAP.
Maybe it was the only strong testcase covering all types of corner cases.
where are solutions?
Yea, it was a very lucky case.
Most tests were generated randomly, using some heuristics (K was set to near maximum, C was between 10 and 400 etc) to prevent overly weak test cases.
It’s the other way round, write an AC code and create a poem for yourself out of that XD
It’s your sort(). Try using a set or get the next_minimum for the (i+1)st loop while doing the i-th iteration.
Yes. Me too got the same test case wrong.
https://p.ip.fi/TxpH
Could you please tell where i went wrong. It will be a great help.
I did a kind of semi-unbounded Knapsack Algorithm.
Making a vector of size ans W and calculating the best possible answer for every value.
Can someone please explain how to decide which lines to erase if we have different values of V ; I did the calculation of triangles in n^2log(n) so didnt got TLE but since I was always deleting lines with maximum no of intersections I got WA for the subtasks (except 1 and 2).The calculation of triangles also took into account the presence of parallel lines. So please explain how to do greedy selection of lines req to be erased.
CodeChef: Practical coding for everyone this is my submission 
wonderful … c++ to english converter
there’s no such greedy selection, have you read about the knapsack problem?
You must have written some script, share it!
yep Knapsack did came in my mind here the eraser length should be the total weight of knapsack right? But I was unable to apply it correctly 
subsfreq editiorial??
Hey @rishup_nitdgp , I am writing this because I hardly get 10% of what is written in this editorial
mostly when switching one paragraph to another I got lost. I actually tried solving this problem for almost 3 days during the contest So I was very excited for the editorials but sadly I can’t get most out of this editorial.In the comment section everyone is talking about why their solution failed for only 1 or 2 test cases nobody is talking about the quality of this editorial maybe they have got everything what u have written or they simply have not read it.I specially feel that this editorial could have been a little bit better.
Please bro don’t take this comment negatively(but take it seriously), I know writing editorials is not easy so thanks for trying your best.
6 Likes
Here is a simple gist of the solution (copied from my draft editorial):
-
First, notice that lines can be grouped on the basis of their colors, since lines of different colors don’t contribute anything to the answer.
-
Now, lets first solve the problem when there is only 1 color (C=1).
-
Since erasing any line of this color has the same cost (or in other words, reduces the length of the eraser by the same constant value), we are simply interested in finding the most optimal selection of lines to remove, to reduce the total number of triangles.
-
Let’s solve for when there are no parallel lines. If there are x lines, no two parallel, the number of triangles is simply x \choose 3 (refer doc). So, removing any line randomly till the eraser becomes too short, is an optimal choice.
-
Now, let’s let’s solve for when there are parallel lines. Notice that we can no longer use the above formula, since 2 parallel lines don’t meet (since the above equation selects all unordered triplets of lines, it will also count a triplet involving parallel lines, which is invalid).
Now, we can group parallel lines into groups. Let A = \{a_1, a_2, \dots, a_p\} be the size of each set of parallel lines. Simple math gives you the total number of triangles as:
\sum_{1\le i\le j\le k\le p} a_i*a_j*a_k
-
Now, if we could erase exactly 1 line, which line would we select? Some experimentation / trial and error would show you that subtracting 1 from the smallest value in A reduces the number of triangles the most. Some more experimentation shows that this holds for any number of removals that we may do.
This gives the lemma: The most optimal method to reduce the overall number of triangles is - removing a line repeatedly from the smallest, non-empty set of parallel lines. The mathematical proof for this (huge thanks to @admin) is given in the editorial. -
Now, using the above logic, we can easily make an array to hold the maximum number of triangles we can reduce if we remove exactly x lines from this color, for all valid x.
-
Things quickly cascade after this. We now have C colors (rather than 1) and we have to find the number of lines to remove from each color, to maximize the number of triangles reduced (while satisfying the eraser length constraints).
This is a classical, well know adaptation of knapsack DP. Figuring out how to modify it to meet the requirements of the problem is a trivial excersise (in case you fail to do it, have a look at my solution).
It’s not well written, but I hope it gave a gist of the solution.
8 Likes
Also, @rishup_nitdgp please add the greedy tag, since the optimal selection of lines to remove uses a greedy choice.
1 Like
Can you please explain how to calculate it in linear time as given in the editorial ?
I’m unable to figure out how sum of products got converted to (cnt1 * cnt2 * cnt3 + 2 * cnt3 - 3 * cnt2 * cnt1 ) / 6
3 Likes