Los_Angelos_Laycurse's blog

By Los_Angelos_Laycurse, history, 8 months ago, ,

problem B Beth Tableaux I have AC by

for(j=0;j<7;j++) for(i=0;i<cnt;i++) seed[i]=rand()%2;

cheating

is there any non cheating idea that can pass all the tests???

•
• +19
•

By Los_Angelos_Laycurse, history, 9 months ago, ,

http://codeforces.com/gym/100285

I got Denial of judgement of this problem and find many others also got this result, hope admin can fix it...

•
• +3
•

By Los_Angelos_Laycurse, history, 10 months ago, ,

•
• +36
•

By Los_Angelos_Laycurse, history, 11 months ago, ,

http://codeforces.com/contest/765/problem/G

is test case 82+ newly added tests??? I have got TLE on test case 82, but I find many AC code only have test 81 tests....

By Los_Angelos_Laycurse, history, 12 months ago, ,

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5156

is there O(N^2) solution???

I have used at least three approach to solve this problem.first two get TLE, last one AC 50 ms(the time is surprising me,because I use O(n^3) precal +constant optimizition..

the second one I use O(n^2)precal +O(n^2*log(n)) FFT obviously it will TLE because there are 1500 test cases..

the third one I use O(n^3) dp[0][i][j][s] record to fill first i empty cells,there are j numbers which is smaller than a1 and s numbers bigger than a(i+1) and ai<a(i+1) dp[1][i][j][s] means ai>a(i+1). in order to get O(1)transfer we can recodrd sum[0][i][j][s]..

to speed up the process of O(N^3) we only need to record states that is visit by the input,so I sort the input increasing by n use scroll array. use f[2002][2002] record f[n][a1-1]=max(f[n][a1-1],n-an)

for(i=1998;i>=0;i--)
for(j=i;j>=0;j--)
f[i][j]=max(f[i][j],f[i+1][j]-1);

for each first two state (i,j) the third state that visit is only [0,min(i-j,f[i][j])], this speed up made my code 50ms..

By Los_Angelos_Laycurse, history, 13 months ago, ,

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1786

uva user try has asked problem author for test cases,he sends tests to me,but there are two tests incorrect:

11 20

8 10 78

9 5 4

3 2 9

11 1 46

6 5 46

5 3 14

9 6 75

11 6 5

6 7 16

9 8 62

9 10 78

4 7 42

7 8 53

4 11 10

6 10 38

11 8 60

8 3 16

4 1 16

4 10 41

11 10 20

4 11 9

11 20

5 7 74

5 4 52

10 6 64

2 7 45

7 1 63

10 7 48

3 8 16

3 10 39

7 8 25

11 5 40

2 5 47

4 6 13

3 4 11

11 6 27

10 11 23

4 8 76

1 6 45

9 11 59

7 6 6

11 1 31

8 11 5

first tests offical answer is 163 but mine is 168.

second test offical answer is 202 but mine is 206.

you can used first edge sets:0,3，6,7,8,10,11,12,13，14,17,18，19 to run first troops. its max_flow value is 108.

and use remain edges to run second troops.its max_flow value is 60 . so 163 is definetly incorrect..

sencond test is similar;

you use first edge sets:1,3,5,6,7,8,10,11,12,15 to run first troops .its max_flow value is 109;

use other edge sets to run second troops it is 97

•
• +13
•

By Los_Angelos_Laycurse, history, 13 months ago, ,

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

in a competetion we offten occur a wins b,b wins c and c wins a,we call this case rock paper scissors given a comptetion graph, mat[i][j]=0 indicate j wins i, mat[i][j]==1 indicate i wins j mat[i][j]==2 indicate i and j are not defined..

you are asked to determine mat[i][j]==2 so that the number of rock paper sissors is maximum

if there is multiple solution output anyone..

http://ideone.com/tN2Gdb

this is my 24 ms AC code, instead of zkw min_cost flow, I use iteration to find unbanlance path, it can run N==1000

complete graph 139ms on codeforces..(if don't output path,it runs 46ms)

•
• +3
•

By Los_Angelos_Laycurse, history, 15 months ago, ,

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

•
• +18
•

By Los_Angelos_Laycurse, history, 15 months ago, ,

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

•
• +11
•

By Los_Angelos_Laycurse, history, 15 months ago, ,

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
•

By Los_Angelos_Laycurse, history, 18 months ago, ,

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

•
• +17
•

By Los_Angelos_Laycurse, history, 18 months ago, ,

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

•
• +10
•

By Los_Angelos_Laycurse, history, 19 months ago, ,

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

•
• +3
•

By Los_Angelos_Laycurse, history, 20 months ago, ,

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=

•
• +5
•

By Los_Angelos_Laycurse, history, 20 months ago, ,

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

•
• +6
•

By Los_Angelos_Laycurse, history, 22 months ago, ,

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

•
• +3
•

By Los_Angelos_Laycurse, history, 2 years ago, ,

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

•
• +1
•

By Los_Angelos_Laycurse, history, 2 years ago, ,

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

•
• +7
•

By Los_Angelos_Laycurse, history, 2 years ago, ,

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

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

•
• +34
•

By Los_Angelos_Laycurse, history, 2 years ago, ,

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

•
• +5
•

By Los_Angelos_Laycurse, history, 2 years ago, ,

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

•
• +10
•

By Los_Angelos_Laycurse, history, 2 years ago, ,

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

•
• +16
•

By Los_Angelos_Laycurse, history, 2 years ago, ,

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

•
• +20
•

By Los_Angelos_Laycurse, history, 3 years ago, ,

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

•
• +6
•

By Los_Angelos_Laycurse, history, 3 years ago, ,

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