Los_Angelos_Laycurse's blog

By Los_Angelos_Laycurse, history, 2 days ago, In English,

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://ideone.com/g5otEq

Read more »

 
 
 
 
  • Vote: I like it  
  • +13
  • Vote: I do not like it  

By Los_Angelos_Laycurse, history, 11 days ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +11
  • Vote: I do not like it  

By Los_Angelos_Laycurse, history, 11 days ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +12
  • Vote: I do not like it  

By Los_Angelos_Laycurse, history, 3 months ago, In English,

I can't open ural oj for one day.. there are 5 problems whose rating >10000 left for me(solved 9 of them), hope I can finish them soon especially ural 1589 and ural 1394...

Read more »

 
 
 
 
  • Vote: I like it  
  • +17
  • Vote: I do not like it  

By Los_Angelos_Laycurse, history, 3 months ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +10
  • Vote: I do not like it  

By Los_Angelos_Laycurse, history, 4 months ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +3
  • Vote: I do not like it  

By Los_Angelos_Laycurse, history, 5 months ago, In English,

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=

Read more »

 
 
 
 
  • Vote: I like it  
  • +5
  • Vote: I do not like it  

By Los_Angelos_Laycurse, history, 5 months ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +6
  • Vote: I do not like it  

By Los_Angelos_Laycurse, history, 8 months ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +3
  • Vote: I do not like it  

By Los_Angelos_Laycurse, history, 10 months ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +1
  • Vote: I do not like it  

By Los_Angelos_Laycurse, history, 13 months ago, In English,

I have test to give some upvote and down vote for zero vote comment, but soon a lot of them get back to zero? What's wrong??

Read more »

 
 
 
 
  • Vote: I like it  
  • +7
  • Vote: I do not like it  

By Los_Angelos_Laycurse, history, 13 months ago, In English,

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

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +34
  • Vote: I do not like it  

By Los_Angelos_Laycurse, history, 13 months ago, In English,

sa +president_tree + brute_force Accepted this problem, seems it is O(n*poly(log(n)),but it needs some proof...,there is litte possibilaty it is O(n^2*poly(log(n))).

Read more »

 
 
 
 
  • Vote: I like it  
  • +5
  • Vote: I do not like it  

By Los_Angelos_Laycurse, history, 14 months ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +10
  • Vote: I do not like it  

By Los_Angelos_Laycurse, history, 14 months ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +16
  • Vote: I do not like it  

By Los_Angelos_Laycurse, history, 14 months ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +20
  • Vote: I do not like it  

By Los_Angelos_Laycurse, history, 16 months ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +6
  • Vote: I do not like it  

By Los_Angelos_Laycurse, history, 17 months ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +5
  • Vote: I do not like it  

By Los_Angelos_Laycurse, history, 17 months ago, In English,

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

Read more »

 
 
 
 

By Los_Angelos_Laycurse, history, 17 months ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +34
  • Vote: I do not like it  

By Los_Angelos_Laycurse, history, 17 months ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +5
  • Vote: I do not like it  

By Los_Angelos_Laycurse, history, 21 month(s) ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it  
  • -22
  • Vote: I do not like it  

By Los_Angelos_Laycurse, history, 22 months ago, In English,

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

Read more »

 
 
 
 

By Los_Angelos_Laycurse, history, 23 months ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it  
  • -1
  • Vote: I do not like it  

By Los_Angelos_Laycurse, history, 23 months ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it  
  • -8
  • Vote: I do not like it