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

http://codeforces.com/problemset/problem/542/B.

my n^2*log(n) solution with prunning got Accepted and worst case is n==10000,run 951ms(not n==200000),hope admin can add a lot of big test cases,I think test cases for a problem at least 100+ is suitable(with a lot of construct test cases),but this problem there is only 37 cases....

http://codeforces.com/gym/100496

I have nearly submit 50 times and always WA on test 14, and I have checked my code for many times

and can't find any bug,I don't think this is a hard problem,so probably test 14 is wrong,or some thing wrong goes to problem description, any help???

http://codeforces.com/gym/100496

I have used a O(unknown) approach and got AC 1700ms:

first,choose a valid root node and perform bfs(),foreach node in the queue list judge and color the node in order from 1 to n...

the implement of bfs() is O(n*log(n)) but the main problem is how to choose valid root and prove its correctness that I have no idea,so I enum each node as root node,if there is valid solution break.

and 1700ms AC, maybe there are a lot of valid root nodes...

can anyone give prove or better idea???

Link:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=441&page=show_problem&problem=4010

It involves to solve bivariate polynomial equation with degree k:(find all solution in a interval[left,right].) i.e.

sigma(A[i][j]*u1^i*u2^j)==0  

  sigma(B[i][j]*u1*i*u2^j)==0  

  (i<=k[0],j<=k[1])  k[0],k[1]<=5,(u1,u2 are veriables)

I haved tried to eliminate the veriable u1: we can write the equation as

f(u1,u2)==sigma(Fi(u2)*u1^i)==0  

              g(u1,u2)==sigma(Gi(u2)*u1^i)==0

              Fi(u2),Gi(u2) are polynomials of u2

first we can eliminate u1^k[0] , f'(u1,u2)==g(u1,u2)*Fk[0]-f(u1,u2)*Gk[0]

g'(u1,u2)== f'(u1,u2)*u1*Gk[0]-g(u1,u2)*Fk[0]-1 .

if we use this approach we can finally get a one veriable polynomial equation F(u2)==0,but the degree is two high, about hundred magnitude we can prove upperbound is about 10th fibonacci number multiply 5 ,this is also a big problem to solve F(u2)==0. I have tried find derive of F(u2) and solve F'(u2)==0 to find extreme point of F(u2) and binary search with each segment.but WA 6s,because of precision error(miss some solution) maybe we can find one of the solution and divide the polynomial?? but how to find one solution without too much precision error?? this is also a big problem....

is there anybody have better idea?

link: http://community.topcoder.com/stat?c=problem_statement&pm=12294 I have found a clever iteration approach for this problem and 4ms passed(this approach is also proper for find integer optimal solution):

first build graph and get all connected component of the graph these component are monotonic between each other,so choose and solve one component and other variable value is lower_bound.

for one connected component first init the variables:satisfy sum of these variable is maxSum,and value of each is between lower_bound and upper_bound. choose any two variables a and b as main variables ,others regard as constant,then find the local optimal value of these variables,let a to be a+dx,b to be b-dx,find the value of dx that is optimal: if a and b is directly connected, it is a downward quadratic function (a+dx)*(b-dx)+C*dx+D, lower[a]<=a+dx<=upper[a] lower[b]<=b-dx<=upper[b]. otherwise it is a linear function. for every two main varibales we can choose the maximum increment of the local optimal values,and relax the chosen varibles: ans[choose_a]+=dx; ans[choose_b]-=dx; until we can't get more optiaml values compare each component of optimal value and choose the max.

this approach is much faster than editorial's O(3^n*n) and it is also proper for find integer optimal solution. complexity is O(n^2*times) times is the (times of interation,seems to be log(1.0/accurancy),not proved yet)

link : http://codeforces.com/gym/100548 My n^6 tree dp with constant optimal get Accepted. I think this problem's float point accuracy is harder than algorithm....it will take more effort to get "within an absolute error of 10−6" than thinking algorithm.....

using long double with some heuristic compute, my code's last example acurracy error is 8e-7.... dangerous Accepted...

include<stdio.h>

int main()

{

double x=-1.99999999999999980000;

while(x>-2.0&&x-1==-3.0)
   puts("orz");

return 0;

}

can anybody give some explaination ,thank you..

http://codeforces.com/gym/100543 can't believe my eyes.....

we can denote optimal solution of (p1,t1,p2,t2) f(t1,t2).notice if two pets start at same time ,then it will be conflict in t==0,so one of the pet must move at least 1 seconds to right,then we can find next conflict position. there are two kinds of choose: move first pet 1 seconds to right,then next conflit position will be solution of p2*x2-p1*y2==1 (first pet will be feed y2 times,and second will be feed x2 times)then next state will be f(t1-y2,t2-x2). increment of time is p2*x2. second choice is :move second pet 1 seconds to right,then equation will be p1*x1-p2*y1==1 next state will be f(t1-x1,t2-y1),increment of time is p1*x1.

so we can get recursion formula: f(t1,t2)=min(f(t1-x1,t2-y1)+p1*x1),f(t1-y2,t2-x2)+p2*x2)) notice :f(0,0)=1;

then we can get further observision for state (t1,t2) we must choose k1 pair of (x1,y1) transition,and k2 pair of (x2,y2) transition,then we can get

k1*x1+k2*y2>=t1

k1*y1+k2*x2>=t2

min(p1*k1*x1+p2*k2*x2)

(x1>=0,y1>=0,x2>=0,y2>=0)

notice: k1*x1 and k2*x2 must be integer, other not necessary.

this will be solved by linear programming. cutting plane algorithm will be work in O(1)

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

Hi codeforces,are you sure special judge(or test data or problem description) of this problem is correct? I don't think my code is incorrect(though may get TLE),but get wrong answer on test 16. please check it.

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

problem C Comb Avoiding Trees my solution for this problem is shorter than 40 lines(I often write long code and make problem more complex than itself when solving problems)

the key observasion of this problem is we must find every rooted binary tree correspond a bracket sequence(thinking in prufer coding)(i.e. something like (((()()()))). and avoid k means the depth of the bracket sequence is less than k. then very short dynamic programming can solve it,complexity O(n^2)

Link:http://codeforces.com/gym/100453 C

what I can think out is to use unsigned long long bit mask compression and brute force for every rectangle.. complexity is total area of query rectangle divide 64,this approach possibly can pass,but it is not so beautiful.

can anyone give me some hint on better ideas(not brute force)?

Link:http://codeforces.com/gym/100020 F This is an interesting problem,and main idea seems simple but hard to find it out. First we can find for each cell when we perform an rotate operation there are four cells related to it: (i,j),(i,n-1-j) (n-1-i,j),(n-1-i,n-1-j)

so we can use only (n-1)/2*(n-1)/2 matrix to record the state of each cells. There are 6 states of each cell:

00 11 11 00 10 01

00 11 00 11 10 01

and further more, when we perform each rotate operation, the result is swap two of these six states. so for each cell,the result of any times of operation is the permution of the six states,for brute force idea we just need to record per[6] for every cells,of course,brute force will timeout,and obviously we need a data structure such as two dimension segment tree with lazy labels for each big matrix(we need to use the permuation of these 6 states as lazy labels). and for every time we visit the big father matrix,we need to pass the lazy labels to the son matrix.we need to convert son.per[6],and fa.per[6] as son.per[i]=fa.per[son.per[i]].

This idea we two dimension segment tree worst complexity is m*n*log(n),this is not the problem,but the problem is memory is too much,so we need to compress the 4000*4000 matrix into 500*500==250000 (8*8) bigger matices and for when we visit matrix which is smaller or equals to 8*8 just run a brute force(use a char mat[4001][4001] to record which constant factor is much smaller than segment tree).

This idea makes me 5300+ms AC, but I don't know if there are any more sufficient data structure to implement this idea

I think it is a insanely hard and interesting problem(at least to me),if I'm not miss something: I

have came up with a idea of complexity O(m*sqrt(n)*log(n)*log(answer))

this is my anlanysis:

we want to find the maximum almost everage number between [a,b] in the

interval (L,R), if the answer >=0 ,then we can conclude the length of the

length of [a,b] is either 2 or 3,so we just need to build a segment tree

record maximum (ai+a(i+1)+a(i+2))/2 and (ai+ai+1). if the result of query of [L,R] is non-negative ,then this is the answer, but if it is negative,then

it is more and more complex: we need to binary search the answer x. we need

to check if there is almost average number >=x. we just need to check if there is

[a,b] v[a]-x+v[a+1]-x+...+v[b]-x>=-x , right part is positive. if we split

the interval into two part and have already checked left part and right part

both are <-x,then we need to check the maximum sum of v[i]-x of the suffix

of left part of interval and maximum sum of v[i]-x of prefix of right part

of interval,and check the sum of suffix and prefix.but how to find them

efficiently. we can obersive we need to check prefix and suffix if and only

if the both of the sum of them are positive,that is to say the the slope

suffix sum of left part (i.e. (v[i+1]+..+v[j])/(j-i))>x i.e. (sum[j]-sum[i])/(j-i) and the slope prefix sum of right part >x, so we just need to find a data

structure to record all the suffix convex hull(decreasing index and

decreasing slope) of and interval and all the prefix convex hull(increasing

index and decreasing slope) of interval(of course we also need to know the

convexhull of whole interval),if we know the covexhull, we just need to use

binary search to find the position of slope that is closest to x(after this position,slope of sum <x i.e.sum of v[i]-x is negative just abandon them). the data

structure to preserve the prefix and suffix of convexhull, squarelist is what I can

think of.because this problem denied any off-line approach.we need to build

static squarlist. and for each squarelist we need to record the almost

average number(brute force to find) of this interval and all the prefix and

suffix convexhull of this interval. the whole process of build squarelist is N*sqrt(N). then for each query, if split the query inteval in to O(sqrt(N))interval for each interval that is not cover the whole of one sqarelist,just brute

force to find the value,and maximum sum of v[i]-x,if it is cover the

sqarelist then find the position of prefix covexhull whose slope closest to

x and the position of suffix convexhull of previous squarelist,sum it up to

and compare it to -x.

this is the approach but I think the complexity is too high,I don't know

much about Functional segment tree, but feel it can also implement this

idea,but it is more and more complex..

if you know much better idea or find some error of this approach, please discuss it.

http://codeforces.com/gym/100162/problem/D

I'm so happy

link: http://codeforces.com/gym/100016 I used a O(n^2*k) construct with some optimization and run 4100+ms how can it be solved in O(n^2),can anyone give some ideas?

link: http://codeforces.com/problemset/problem/457/E

"If the intern's solution may be optimal, print the efficiency of the solution if it can be determined rounded to the nearest integer, otherwise print "UNKNOWN"."

I think the efficienty of the solution is always undetermined,because if intern's solution is correct,and total flow is k,for every correct solution we can always add a new eddge from node 1 to node n with w==inf and b==1,the total flow is k+1 and intern's solution is also correct for optimal cost,but the effiency is surely changed.

am I miss something?