Hello everybody !
School is finished. I am in the village. I don't have fast internet and I won't do next competition :(
But, I can write new topic with my 'potato' English with no word HELP ( so you can relax and read next part :D ) !
During this break I plan to learn a lot of things. First I start with learning C++ . Pascal is great language and help me a lot, but without C++ you can't do something very fast and good on the competitions (when I had to write some algorithm with graphs (even dfs) or I had to write SET , always i said — NO WAY , GO TO NEXT TASK ). Now I will change it and no more crying for bad results :)
I also plan to learn many graphs and string algorithms ( now a know 4-5 graphs algo. , KMP and hashing ( everything harder I do with hashing), also I know trie but it wasn't necessary to coding it on any contest ). Normally I plan to do every competition on the summer :D
What will you do during vacation ?
Second part of this blog is about preparing tasks for contest.
My friend and I prepared one contest, for me it was very interesting and good experience. I hope you like our problems... Sorry for hard div 2 round, next time I'll give my best to make better contest. I recived a lot of messages about our contest, many messages were grat, but also I recived some insluts. Please, don't write me it again :) Everything I do because I love programming and this community, maybe I deserved insults , but you don't talk about my friends, proffesor and country on that way !
The last few days I invented many new problems ( I believe I have enough problems for 2 contest ). But I will try with my friend , to come up some very hard problems( D, E div 1), for other problems I think I have enough ideas to devise a daily div 2 contest :D Please give me advice, how I can invent hard problems ( I know it isn't easy and you must know a lot about programming and contests) , but tell me how did you come up your 'famous tasks' ?
Also, If you have some impressions of our contests or some intresting problems on codeforces , I like to hear it .
At the end, I will write one my task ( certainly something like this already exist, but I didn't see it before) :
PROBLEM 1
You have plane with n points (-10^6<=Xi,Yi <=10^6, n<=10^5). You should draw a line which will contain the most points from this set. Print the number of points on this line. (I didn't solve this task, but I expect you can find some solution lower than O(n^2)).
PROBLEM 2
You have plane with n points ( -100<=Xi,Yi<=100, n<=50). Find minimum number of lines needed to cover all the points . ( For previous problem I had some solution, but for this I can't find something normal ).
Thanks for reading, sorry for Englsih and solve tasks ;)
P.S. I can add more intresting tasks.
+1..As you asked about summer plan.I have learnt some basic algo's like dfs,bfs,toposorting,bipartite,ssc,Disjoint set union and a few more I am very happy with my progress(I don't care about ratings)Apart from this I have started a blog too..along with this I have started reading some Interview question-answer book.I have planed to do MSc in Computer science so I have started learning discrete maths too.I like maths a lot but sadly I have very poor math background.I never bothered to study when I was a kid and when I realised I was around 17yo.I didn't even know very basic maths(didn't knew what euclidean distance is.)I am almost 20 and half now and two years remaining in my undergraduates.I have also started solving IMO previous year papers so that I can grasp maths quickly.
Secondly,I am so sorry that people insulted you.You tried really hard to make contest and it was awesome.Congrats and be blessed.
I corrected some grammer mistakes :)
Thanks for replaying antivenom ! I hope you will learn everything what you want !
It's nice to see people write their thoughts throught blogs, imo this should be encouraged — Good luck! Regarding your problem, I think an O(n) algorithm (or even O(nlogn)) doesn't exist. The best I could think of is O(n^2), using some hashing.
I don't think the task you gave is solveable faster than (n^2 *log(n) )
Yes it can be reduced to n^2 using hash
I really don't think about O(n) solution, everything lower than O(n^2) is very good ! I change constrains for coordinates, maybe that can change something.
I put another problem, maybe you can solve it.
I think problem setting is more interesting, because you have to make sure some solutions will not pass (WA, TLE, ..)
Looking forward to your next round :)
One of the most interesting problems for me is PrinceOfPersia's task 536C - Tavas and Pashmaks. I want to know how did he invent this amazing problem?
I like his problem 536A - Tavas and Karafs, good binary search with interesting 'greedy' algorithm. I had difficulty on virtual competition with it. Also problem C on last competition (308 div 2) was great !
Preparing contest is pretty hard thing, if you are amateur for it !
After some search, I found that your problem can be solved in O(n) if the coordinates of the points are less than or equal 10^6 or maybe 5*10^6 (exactly maximum array size over 360). The solution uses Hough transformation which gives an approximated result in practical implementations.
For every possible line there is another line from the origin perpendicular to that line. We may use the polar coordinate system to represent the line by R distance and Theta the positive angle from the x-axis. Create a 2-D array with two parameters the angle and distance from origin point, the array will hold the number of points that lies on that line. Now for each point there is at most 360 lines it can lie on (not considering rational angles), so loop from 0 to 360 and calculate the distance and increment the line. You can keep track of the maximum instead of other methods to get the local maximum and global maximum in the matrix.
Of course the result may be wrong since we have to round the distance to the nearest integer (or you may use map or hash-maps). Also, we only loop over integer angles only (maps may not help here).
Interesting solution, I don't know a lot of about polar coordinate system and I couldn't think on that way ! Also solution can be wrong, but it's nice to know something new ! Thanks !
Lol, you got master with pascal. You can get more with C++ :)