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

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

1 | tourist | 3372 |

2 | mnbvmar | 3345 |

3 | OO0OOO00O0OOO0O0…O | 3264 |

4 | Radewoosh | 3230 |

5 | scott_wu | 3189 |

6 | Benq | 3187 |

7 | LHiC | 3171 |

8 | Um_nik | 3155 |

9 | V--o_o--V | 3152 |

10 | Petr | 3139 |

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

1 | Radewoosh | 191 |

2 | Errichto | 172 |

3 | rng_58 | 158 |

4 | neal | 156 |

5 | Um_nik | 154 |

5 | tourist | 154 |

7 | Petr | 152 |

7 | Ashishgup | 152 |

9 | 300iq | 150 |

9 | PikMike | 150 |

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

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

There are 6 problems whose rating >=4500 left::

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

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

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

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

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

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

all of them seems not easy to solve, welcome to discuss these problems..

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

admin please rejudge all solutions...

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

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

so second answer is 206

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

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)

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

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/19/2018 15:32:08 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|