# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3821 |
3 | Benq | 3736 |
4 | Radewoosh | 3631 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3388 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Name |
---|
Yaaah..... Hope the Problems will be interesting
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?
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