dWhy this task can be solved with brute force ???
There is in task that n <= 1024 and k <= 1024 so the worst case is (i think) n = 1024 and k = 512 so with brute force that is (k^2*(n-k)^2) = (512^4) = 68.719.476.736 and that is toooooooo big for 1 sec ...
so why are test cases in this task very bad ... ???
My solution has O(n*n*log(n*n)) complexity(I use FFT). But with such strict time and memory limits it works correctly only when n<=512. I was very surprised when I saw 100 points solution (My program recieved 80 points as I expected). So I ask to share the idea on 100 points solution.
our team was thinking of solution with fft but it was too complicated, and I think that is fastest solution, so probably brute force got 100 points, or some randomized solution. ( my brute force with clocking got 70 points )
I used brute force and got 3/10 TLEs. I don't understand how did you solve it using bf ?
I just say that probably randomized brute force solution got 100 points, if fft is too slow.
So if brute force can got 100 points, it is obvious that tests were very week. Too bad, cos I very like this problem.
bf with small optimization ...
1st optimization: when solution is 0 just write 0 and exit program
2nd optimization: when you compare and absolute different is bigger then 15 then break ...
It's still O( k^4 ) in worst case ...
test cases are very bad ...
broke such solutions is not very hard...
@frost_nova: do you used anything other than mincut in problem z-cellphones?
I got tle on last 3 test cases, maybe because I used relatively slow max flow algorithm.
@gates: no nothing more than mincut, just fast maxflow algo.
@frost_nova: how to solve this with maxflow? Any hint?
represent problem as a graph and actually mincut is solution, but because of mincut maxflow theorem it can be calculated just like maxflow( you probably know this ).
How to construct the graph? I mean, how to represent the problem as a graph?
then I have to say whole solution...but ok.
let C1[x] be cost of installing cellphone of first company to house x, and same for C2[x] and second company, and let K be cost of blocker.
set edge with capacity C1[x] from source to every house x, set edge with capacity C2[x] from every house x to sink.
set edge with capacity K between every pair of adjacent houses.
you see now that you have to split source and sink with minimum cost.
after mincut you'll have graph with 2 components, if house x is in same component as source it will take second company for installing cellphone, and if it is in same component as sink it will take first company.
We have the same solution.
