I have use a O(n^2/31) dynamic programming approach and use bitset optimization and get AC 0.06s..

1873447 09:40:10 Scenery Accepted 0.06 s C++

here is my code:

algorithm correctness have not been proved yet,

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

1 | tourist | 3602 |

2 | Petr | 3265 |

3 | ainta | 3174 |

4 | LHiC | 3163 |

5 | Um_nik | 3159 |

6 | izrak | 3109 |

7 | W4yneb0t | 3087 |

8 | RomaWhite | 3053 |

9 | moejy0viiiiiv | 3051 |

10 | I_love_Tanya_Romanova | 3031 |

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

1 | rng_58 | 176 |

2 | Errichto | 175 |

3 | Petr | 164 |

4 | csacademy | 160 |

5 | tourist | 158 |

6 | Zlobober | 151 |

7 | Swistakk | 150 |

7 | GlebsHP | 150 |

9 | zscoder | 144 |

10 | matthew99 | 138 |

I have use a O(n^2/31) dynamic programming approach and use bitset optimization and get AC 0.06s..

1873447 09:40:10 Scenery Accepted 0.06 s C++

here is my code:

algorithm correctness have not been proved yet,

http://codeforces.com/gym/101366

problem F who can give me test case 3, I got strange TLE on this test...

I'm sure excution times of test case 3 is far less than 1e6, but got TLE as far as I have tested...

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..

http://codeforces.com/gym/100110

problem J I have tried at least two approach for this problem both of them get stuck on test case 67, what's the kind of this test?

I began to doubt the correctness of this test...

world finals 2014 problem L Wire Crossing

test data is probably wrong, my code had been AC in uva live and uva. but WA on test case 6 on codeforces, admin please check test 6 is incorrect...

http://poj.org/problem?id=2520

today, I have solved problem poj 2520: now I'll share my approach:

use dynamic programming dp[cost][pos1-pos2] maximum position it can reach with cost cost and difference of position is p

pos1-pos2. cost is the true cost plus estimation function which is equal to 3*(len[0]-pos1-(len[1]-pos2)),

for each cost we constraint lower_bound and upper_bound of pos1-pos2 is between (3*(len[0]-len[1])-cost)/6 and

(3*(len[0]-len[1]+cost)/6.. and upper_bound of cost is not exceed 30000.

so the total state of dp is not bigger than 1.5*10^8..

it can AC with some constant optimization..

http://poj.org/status?problem_id=2520&user_id=&result=&language=

http://acm.timus.ru/problem.aspx?space=1&num=1369

today I have solved problem ural 1369. which spent me nearly two months and 600+ submits. now I'll share you approach of this problem:

first find voronoi diagram of this problem, and using sweepline algorithm to scan x cooridinates voronoi convex polygon

using set to record the point inside the polygon(sort by y cooridinates), for query, find the nearest y cooridinates scan the set from this nearest y points, if dist>min_dist+eps break..

I use this approach and WA on test 17, it is because there is precision error on voronoi points.

then I change sweepline the y cooridinates,and sort the set by x, it got WA on test 21(a different test)

so I combine this two approach together, and compare the two results,choose the minimum distance,finally get AC..

http://codeforces.com/contest/713/problem/E

if we change the problem description: all guests move one step in any direction , how to solve this problem::

binary_search+iteratrion..

first we can get lp inequations: a[i]+y[i]+1==a[i+1]-x[i+1] for 0<=i<=n-2 a[n-1]+yn-1+1==a[0]-x[0]+m

2*x[i]+y[i]<=T||x[i]+2*y[i]<=T.. for 0<=i<=n-1

we can iteratively to find minimum value of lower_bound of each x variable.. low[i], use dynamic programming low[i+1]=min(a[i+1]-a[i]-1-(T-2*low[i]),a[i+1]-a[i]-1-(T-low[i])/2); low[i+1]=max(low[i+1],0); after we run a circle , we got new low[0], if this value >T return false, if this value doesn't increase return true. else continue to run a circle and update low[0].

we must consider two cases : x[0]+2*y[0]<=T and 2*x[0]+y[0]<=T seprately..

my first code which wa on test case 5 is this idea, which I have misunderstand the problem description...

http://codeforces.com/gym/101047/problem/F

I have implement an O(N^2) greedy algorithm and get Accepted, but I dont clear if it is correct:

first to fighting with all y-x>=0 from smallest x to biggest x, and throw out all y-x>=0 point

then sort remain point by increasing of (x-y). then check ,add every point to stk_list[] one by one. for each point i, choose the position of this point we will insert,the value

min(H-x1+y1-x2+y2-....-xj) for each j>=1&&j<=i after we insert point i must be biggest

if the maximum min(H-x1+y1-x2+y2-....-xj)<=0 then throw out this point and k--.

if we use binary_search approach and something like treap data structure, then total complexity is O(N*log(c)*log(n))

I have got accpeted, but I havenot prove its correctness and I don't know if test data is strong...

http://codeforces.com/gym/100958 problem I substring pair::

what a hard problem, I have spent nearly a week on this problem....

this is an interesting problem if you use n*log(n)*log(p) algorithm but I use 50 lines O(n^2) brute force and got accepted

16834091 2016-03-20 11:12:29 Los_Angelos_Laycurse 645G — Armistice Area Apportionment MS C++ Accepted 889 ms 4900 KB

I don't know if it is easy to cha...

http://codeforces.com/gym/100800 problem F

again I use brute force and solve this problem 6500+ms

so I assume for every acm problem there must be a brute force approach that can AC...

http://codeforces.com/gym/100927 problem B

Is there O(n^2) solution? I use O(n^3/16)+O(n*m) with very very small constant and got accepted...561ms

15453721 2016-01-20 16:18:12 Los_Angelos_Laycurse D — Dining Room MS C++ Accepted 2464 ms 24600 KB

http://codeforces.com/gym/100863

spend three days on this egg hurt(chinglish) problem.

complexity : (N*Q^2*log(N)) notice :this is log(N) not log(N)^2

with very very very very very very very very heavily optimizition..

http://codeforces.com/gym/100863

again what an easy and 0 ACed problem, probably data case is wrong,hope admin can check it or send it to me, I'll check it...

both my brute_force and sweepline algorithm are same for random case and both are WA on test 4...

link: http://codeforces.com/gym/100803

seems test cases are too weak::

I just try to find floating solution of (a1*x1+a2*x2+...+an*xn)*(b1*x1+b2*x2+...+bn*xn)*(c1*x1+c2*x2+...+cn*xn)... x1+x2+...+xn==k 0<=xi<=1 and it is equal to integer solution for all test cases.. so we have O(polynomial) solution to find minmum floating value of f(x1,x2,....,xn)=(a1*x1+a2*x2+...+an*xn)*(b1*x1+b2*x2+...+bn*xn)*(c1*x1+c2*x2+...+cn*xn) x1+x2+...+xn==k 0<=xi<=1 all of x[] is integers

Hope admin can add test cases....

can anyone give explaination, I don't know how to find the hardest problems on cf now.....

http://codeforces.com/contest/185/problem/E

problem description doesn't mention what to output when there is no solution:

for example:

2 0

1 0

2 0

what's the output to this samples?? 0.5 or 1 or no solution.. problem description doesn't mention it at all...

http://codeforces.com/gym/100134

though there are 345 test cases, I think there are a lot of holes in test cases,maybe it is a little boring to write n^2 brute force but sweepline algorithm is also not interesting....

http://codeforces.com/gym/100016

I have no idea how to compute integral of f(z)=0.5*(r*r-z*z)*acos(c*z/(r*r-z*z)) (c is a constant and r is the radius of sphere) I can't find its original funtion so I have tried something like simpson, but it is tooooo huge (worst case 2000 times compute) and got tle on test 4... any one have idea how to compute the original funtion thanks....

http://codeforces.com/gym/100491

i have code two totally different approaches and both of them wa on test case 13.... this is a very easy problem but nobody get accepted, I think data case is wrong....

http://codeforces.com/gym/100020

what a fucking problem! if you use scanf to read all n*n matrix n<=2000, you will defintly TLE.... we must read only n+1 number,and get the state....

and there are sepcial test cases for n==1 &&n==2 I want to break my computer when solving this problem....

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/29/2017 14:27:16 (c4).

Desktop version, switch to mobile version.
User lists

Name |
---|