### chrome's blog

By chrome, history, 7 years ago, translation,

Hi there!

Tomorrow at 05:00 MSK, will be held Topcoder SRM 674.

Let's discuss problems after contest.

• +96

 » 7 years ago, # |   +8 Yaaah..... Hope the Problems will be interesting
 » 7 years ago, # |   -12 wish everybody a sound sleep :)
 » 7 years ago, # |   0 Wake up people, registration is open!
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 You're not able to wake people up with this comment!
 » 7 years ago, # |   0 Could someone explain their solution to 1000? I couldn't understand what the AC codes were doing.
 » 7 years ago, # |   -13 |num| <= 20 and O(N) passes...
•  » » 7 years ago, # ^ |   0 That constrain was totally deceiving >_<
•  » » 7 years ago, # ^ |   0 Sorry for that. We will not use this kind of misleading constraints anymore.
•  » » » 7 years ago, # ^ |   +220 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.
•  » » » » 7 years ago, # ^ |   +39 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).
•  » » » 7 years ago, # ^ | ← Rev. 4 →   +31 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 :)
 » 7 years ago, # |   +8 My code: Div2-Easy: http://ideone.com/HAhcJC Div2-Medium: http://ideone.com/UL5r6t Div2-Hard: http://ideone.com/fv4IXx Div1-Easy: http://ideone.com/NQ1us4 Div1-Medium: http://ideone.com/iXDHbE Div1-Hard: http://ideone.com/8DmwsC
•  » » 7 years ago, # ^ |   0 Could you write some explanations?
•  » » 7 years ago, # ^ |   0 In div1-hard,why choose M=80*80*80?
 » 7 years ago, # |   +3 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)
•  » » 7 years ago, # ^ |   0 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?
•  » » » 7 years ago, # ^ |   +5 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.
•  » » » » 7 years ago, # ^ |   0 Yeah okay, I got it. Thank you for your patience!
 » 7 years ago, # | ← Rev. 2 →   0 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?
 » 7 years ago, # |   0 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.
 » 7 years ago, # |   +24
 » 7 years ago, # |   0 Can someone help me with my D2 500? http://www.textsnip.com/13653aI couldn't think of the integer-only solution. So instead I do this:  for (each point p) translate all points so that p is at the origin for (each transformed point q) a = angle of q rotate all points by angle 2pi-a, so that q is on an axis count number of points on x/y axes using 1e-8 precision 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!!
•  » » 7 years ago, # ^ |   0 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
•  » » » 7 years ago, # ^ |   0 Gosh.. I see now. Thanks so much!