some days ago I have found a stronger version of an old problem: TCO 13 round 3A 1000pts:

https://community.topcoder.com/stat?c=problem_statement&pm=12547 stronger version: https://www.lydsy.com/JudgeOnline/problem.php?id=3284 with range m-n<=1000

but I have found this stronger version is not strong enough..I have found (m-n)*lg(m-n) sol of this problem.. the problem is to compute number of sol X1+X2+..+Xm<=s
satisfy 1：1<=i<=N,Xi<=t 2:X1+X2+...+Xm<=s the answer is sigma C(S-X1-X2-..XN,M-N) for each 1<=i<=n xi<=t the answer can be write as (f[0]*z^0+f[1]*z^1+...+f[m-n]*z^(m-n))/(m-n)! z==S-X1-X2-...-XN-(m-n). and f[] is the stirling number of first kind.

we have two steps first to compute the stirling number of first kind and second is to compute sigma((S-x1-x2-..-xn)^i) xi from 1 to t,for each i =1 to m-n

the expansion of (S-x1-x2-...-xn)^i is sigma(i!/(i1!*i2!*..in!*in+1!) (-x1)^i1(-x2)^i2*..*(-xn)^in*(S)^in+1) xi is from 1 to t, i1+i2+..+in+1==i i is from 0 to m-n. if g[i]=1^i+2^i+...+t^i.

if h(x)==simga(g[i]*x^i/i!) ,g(x)==sigma(S^i*x^i/i!). then g(x)*h(x)^n is generation funtion of (S-x1-x2-..-xn)^i we can compute g(x)*h(x)^n by g(x)*exp(n*ln(h(x)), this is (m-n)*lg(m-n)

and how to get g[i],i from 0 to m-n we know an (m-n)^n sol can get g[i]: (t+1)^(i+1)-t^(i+1)==simga(C(i+1,i+1-j)*t^j) j is from 0 to i. t^(i+1)-(t-1)^i==sigma(C(i+1,i+1-j)*(t-1)^j) j is from 0 to i ... 2^(i+1)-1^(i+1)==simga(C(i+1,i+1-j)*1^j) j is from 0 to i

and these equations we can get t^(i+1)-1== sigma(C(i+1,i+1-j)*g[j] j is from 0 to i so g[i]==(t^(i+1)-1-sigma(C(i+1,i+1-j))*g[j])/(i+1) j is from 0 to i-1.

if you continue to expansion this equation you can get:

g[i]==simga(i!/((-(i1+1))!*(-(i2+1)!)*(-(i3+1)!)*..*(-(ik+1)!))*(t^(i(k+1)+1)-1)/((i(k+1)+1)! k is from 0 to +oo i==i1+i2+..+i(k+1) if we set f(x)==x^i/(-(i+1)!) g(x)==(t^(i+1)-1)/(i+1)! then g[i]'s generation funtion is g(x)/(1-f(x)) . then we can find g[i] by compute inverse of(1-f(x) and multiply it by g(x).. so g[i] can be compute (m-n)*lg(m-n)

last how to compute stirling number of find kind by (m-n)*lg(m-n)?

just use recursion if we have found coef o f(n/2,x)=(x+1)*(x+2)*..*(x+n/2) then we can got f(n,x)==f(n/2,x)*f(n/2,x+n/2) we can expansion f(n/2,x+n/2) using FFT in O(n*lg(n)) and find multiply using FFT in O(n*lg(n)) so complexity is T(n)=T(n/2)+O(n*lg(n)) it is O(n*lg(n))

so total complexity of this problem is O((m-n)*lg(m-n).

here is implement of this problem

https://www.ideone.com/DifbHi

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://mirror.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://mirror.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..

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)

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

http://mirror.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..

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

http://mirror.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://mirror.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://mirror.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...

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

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

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

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

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

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

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://mirror.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..