# | User | Rating |
---|---|---|

1 | tourist | 3757 |

2 | jiangly | 3590 |

3 | ksun48 | 3582 |

4 | Um_nik | 3539 |

5 | maroonrk | 3533 |

6 | slime | 3498 |

7 | djq_cpp | 3486 |

8 | Radewoosh | 3442 |

9 | cnnfls_csy | 3427 |

10 | ko_osaga | 3355 |

# | User | Contrib. |
---|---|---|

1 | -is-this-fft- | 184 |

2 | awoo | 180 |

3 | dario2994 | 171 |

4 | SecondThread | 168 |

4 | maroonrk | 168 |

4 | Um_nik | 168 |

7 | adamant | 166 |

8 | YouKn0wWho | 165 |

9 | errorgorn | 164 |

10 | antontrygubO_o | 162 |

↑

↓

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/07/2022 09:38:35 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Yaaah..... Hope the Problems will be interesting

wish everybody a sound sleep :)

Wake up people, registration is open!

You're not able to wake people up with this comment!

Could someone explain their solution to 1000? I couldn't understand what the AC codes were doing.

|num| <= 20 and O(N) passes...

That constrain was totally deceiving >_<

Sorry for that. We will not use this kind of misleading constraints anymore.

Why? The constraints made the problem fresh. I started from bitmask, realized 3^20 is too much, moved to combinatoric solutions and finally realized it's greedy one. We're too used to think solutions along with constraints.

I'm kind of surprised to see in fact more people like this unconventional setting. So maybe we can try more 'fresh' things in SRMs in the future.

Thanks for your feedback (and 182 people who liked it).

on the contrary, such constraints make the problem more interesting, at least to me, because we do not have much information about expected complexity, thus encouraging fresh, unbaised solutions.

This is one of the things i have liked about TC problems :)

My code:

Could you write some explanations?

In div1-hard,why choose M=80*80*80?

My solution to

Div2 500: O(n^4)The question can be rephrased as:

"Place the origin the orient the coordinate axes in such a way that you get maximum points on the axes"So we know that if we have 3 distinct points, then we have can place the axes in such a way that the x-axis lies on 1st two points and the y-axis lies on the 3rd point. (This is because you can always place the coordinate axes in such a way that vertices of a triangle lie on the axes). So iterate over all triplets in O(n^3) and for a particular triplet, check how many points lie on the axes including these 3. The maximum will be the answer. I did a small silly mistake but my code passed the system tests later on. Hence overall complexity = O(n^3 * n) = O(n^4)

Code: http://ideone.com/vdyaTI

Thanks, I gathered something like that from the solutions, but I keep thinking about the case where you have 3 points on a line, for this case the placement of the origin is still not certain as it could be translated along the y axis as much as you want and still contain all 3 points.

Could you help me understand why it works in this case?

Just like I said, we have a triplet of points (a,b,c) then we can assume that a and b lie on the x axis and c passes through the y-axis.

In the code, I have considered all possible triplets hence, all 3!=6 triplets will occur corresponding to (a,b,c) and therefore no case will be missed out.

Yeah okay, I got it. Thank you for your patience!

Also, what exactly was the solution to

Div 2 1000? No one actually solved it so I think it must have been a tough one. cgy4ever's solution suggests that it was DP+Bitmask.Can anyone explain the solution?

My approach to the Div 2 500 pointer was:

Among all points, find the maximum number of points which lie on two lines perpendicular to each other. If two lines are perpendicular to each other then you could place them in the X-axis and Y-axis.

My solution failed, so I'm not sure if this approach is correct or my implementation is buggy.

Can someone help me with my D2 500? http://www.textsnip.com/13653a

I couldn't think of the integer-only solution. So instead I do this:

I have a test case it's failing on, so I can figure it out eventually. But just wondering if it is the approach or is it the precision? Thanks!!

According to your algorithm, if the test case consists of 4 points that lie on the vertices of a square then your answer will be 3 but the correct answer should be 4. (If you keep the origin in the center of the square)

Test case your code fails on: http://ideone.com/4yLHqN

Gosh.. I see now. Thanks so much!