ACCBIP - Editorial

editorial
, , , , , , , ,
47

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 :frowning: :frowning_face: :upside_down_face:

48

subsfreq editiorial??

49

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
50

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
51

Also, @rishup_nitdgp please add the greedy tag, since the optimal selection of lines to remove uses a greedy choice.

1 Like
52

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
54

can anyone tell what tf was wrong with 9th test case

55

Please google the definition of coinciding before claiming the problem statement was faulty. For the lazy ones, here it is - Coincident Definition (Illustrated Mathematics Dictionary).

56

Honestly, I donno. I’ll debug it tomorrow!

57

can u help me solution in top down manner

58

Bro can you please tell the test case that was set in test case 9 and also what was the special thing in that test case that most of us missed.

59

Heyya! How do you calculate the number of valid triangles for each colour using that crazy formula ? I mean how did you come up with that?
Thanks!

60

Same here…Just one TC wrong…Can you please identify the problem…Wong on TC#9
https://www.codechef.com/viewsolution/36796068

61

Nice problem… !!!
My mind became :exploding_head: :exploding_head: after solving it on paper …
Get only 15 point lol… :stuck_out_tongue:

62

Yes, I also feel the same way, I am not able to grasp anything from this, and also there’s no other editorial available , @admin would it be possible to arrange something?

1 Like
63

This is THE Best Solution I have ever seen, Wonderful !!

64

@infinitepro I personally feel that your editorial is way better than the official editorial (except the fact that it doesn’t has mathematical proof)

2 Likes
65

@infinitepro Can you please tell what is vvi val(c+1) doing in your solution , It would be a great help for me

66

@infinitepro thanks for this, it’s much clear now.

1 Like
67

Seems like I need to write an unofficial editorial. I’ll do it tonight!
Please wait till then :slight_smile:

2 Likes