### Блог пользователя Los_Angelos_Laycurse

Автор Los_Angelos_Laycurse, история, 11 месяцев назад, ,

There are N points cooridinate is x[1],x[2]....x[N]; try to partition these points into two sets {p1,p2,....pk1} (q1,q2,...qk2};p1<p2<..<pk1,q1<q2<..<qk2 the weight of partion w=abs(xp1)+abs(xp2-xp1)+abs(xp3-xp2)...+abs(xpk1-xp(k1-1)+abs(xq1)+abs(xq2-xq1)+...+abs(xqk2-xq(k2-1)).

find the kth smallest partion.. N<=10000, K<=500000, x[i]<=100000000..

you can submit this problem here:

http://www.lydsy.com/JudgeOnline/problem.php?id=3945

two partions are different if and only if the sets of them are different..

•
• +12
•

 » 11 месяцев назад, # |   0 Auto comment: topic has been updated by Los_Angelos_Laycurse (previous revision, new revision, compare).
 » 11 месяцев назад, # |   +1 Time Limit: 20 Sec Really?
•  » » 11 месяцев назад, # ^ |   0 Yes, time limit is too tight,I have solved this problem in K*lg(n)^2+n*log(n)^2+k*lg(n)and set the first k==min(k,200),and get Accepted..
•  » » » 11 месяцев назад, # ^ |   0 Even if K = 500000, Your algorithm should run in less than 1 sec!
•  » » » » 11 месяцев назад, # ^ | ← Rev. 2 →   0 precisily speaking it is K*log(w)*log(n) w is about 1e12, it is too big, and I have run random test case 1.6s per case on codeforces. maybe there are many tests...btw I want to know whats the intended solution of this problem.
•  » » » 11 месяцев назад, # ^ | ← Rev. 4 →   0 How did you do it? I have seen many problems that seem unsolvable, but this one is completely unapproachable. Your complexity is really good and should easily fit in 2-3 second. Maybe that strange judges's grader is just too slow. Could you, please, briefly describe the solution? Something like N^3 would be easy and I hardly found an NlogN algorithm to get the smallest weight. But, as I see from your complexity, you're somehow binary searching the answer which I have no clue how to include in my dynamic programming (the only way I know to get the smallest weight, let alone the Kth)
•  » » » » 11 месяцев назад, # ^ | ← Rev. 2 →   +11 first ,try to find the minimum distance of every state i, optimal way to partion first i points into two sets using dynamic programing:dist[0][i]=min(dist[0][j]+abs(x[j+2]-x[j+1])+abs(x[j+3]-x[j+2])+..+abs(x[i]-x[i-1])+abs(x[i+1]-x[j]); we can write abs(x[j+2]-x[j+1])+abs(x[j+3]-x[j+2])+..+abs(x[i]-x[i-1])as sum[i]-sum[j+1],by precompute sum[i]=abs(x[1])+abs(x[2]-x[1])+..+abs(x[i]-x[i-1]);so dist[0][i]=min(dist[0][j]+sum[i]-sum[j+1]+abs(x[i+1]-x[j]);we can use segment_tree to optimal this dynamic programing process inN*log(N).and similarly we should compute the reverse state dist[1][i] means partition points i,i+1,...n into two sets...now we'll focus on Kth smallest partitions:Do you know the O((m+k)*log(n)) algorithm on K th shortest paths??if you don't find it on the internet, it is a Classical problem(solutions)..but there is a problem.. m is about O(n^2) how to optimize?we can thoose the first K smallest edges: by smallest we mean the weight:w[i][j]= dist[0][i]+dist[1][j]+sum[j+1]-sum[i]+abs(x[j]-x[i]) : ie minimum distance go to i and using edges (i,j) to get to point j,and from j to destination point..we want to find the Kth smallest edges, I using binary search weight and find how many edges is smaller than this weight and record them, it can be done in K*log(w)*log(n)..at last you can use these K edges to run kth smallest shortest path in k*log(n)you can try to smaller these K number because for many tests the edges you are truly used is far smaller than K
•  » » » » » 11 месяцев назад, # ^ |   0 Could you please provide a link or a formal name to look for (for the algorithm). I don't know it and it seems is has a really good complexity. I'd be happy if you could give me a problem to solve too (like the classical problem asking for the exact same thing as the algorithm you mentioned). I can't believe I missed this one, I thought I know most of them. After that, I see how you can build a graph and optimizing it should be something I can handle myself (maybe I could even come up with a slightly different solution that could help you too).
•  » » » » » » 11 месяцев назад, # ^ |   0 here is the articlehttp://pan.baidu.com/share/link?uk=1176019800&shareid=3271123889&fid=848270619&errno=0&errmsg=Auth%20Login%20Sucess&&bduss=&ssnerror=0but it is in Chinese,try to translate it..
•  » » » » » » » 11 месяцев назад, # ^ |   +8 the original Kth shortest path problem is here:http://codeforces.com/gym/101365problem I..
•  » » » » » » » » 11 месяцев назад, # ^ |   0 Thank you! Once I understand the algorithm and solve this problem, I'll come back to the one you've mentioned in this blog and would try to solve it. If I find any better solution, I'll let you know
•  » » » » » » » » » 11 месяцев назад, # ^ | ← Rev. 2 →   0 I think build graph is an important part of this problem. I use 1d segment tree with if tree[id].min_value>w prunning approach. but now it seems it is better to use 2d segment tree...btw, probably the k=min(k,200) is a wrong approach, but test data didn't challenge me..
•  » » » » » » 11 месяцев назад, # ^ |   +11 Pretty sure this is Eppstein's algorithm.
•  » » » » » » » 11 месяцев назад, # ^ |   +5 That's exactly what I just started to read a couple of minutes ago. Thanks! At least now I'm sure I am reading in the right place
•  » » » » » 11 месяцев назад, # ^ | ← Rev. 4 →   0 So I have another idea of building the graph. The complexity would be approximately the same, but the Klog^2(N) term disappears. I build a graph with O(NlogN) nodes and O(NlogN) edges: N nodes for the positions in the array and NlogN for the nodes in a persistent segment tree. The paths in the graph ending at a position should have a length equal to the unoptimal dp if you chose a certain partition so far. The paths will go from a position to some node in the persistent segment tree and back to some other position and so on. Basically we add edges instead of actually finding the smallest distance. Edges from positions to nodes in the segment tree when we update and vice versa when we query. It must be persistent to assure that we don't get from a position i to some other smaller position j. This way, once you have the graph built, you can simply run the classical algorithm and the only part that depends on K would be the KlogK. I know it's not really well explained, mainly because I should've better define unoptimal dp. It is just some cost that you can achieve till some position by using the same recurrence, the only change being that now you don't have to use minimum of something, but rather the reunion of those possible values.Ohh and, of course, to reduce logVmax to logN (from the segment tree part because we update and query depending on values of X), we just need to use a normalization.