Guess I'm a faithful guy...

Lately, I'm constant af...

For problem E, I have O(N + M + (M — N) log (M — N) + Q log (M — N)). Is that right?

Auto comment: topic has been updated by DanAlex (previous revision, new revision, compare).

You are right. PocolaOctavian also noticed. Sorry for long delay in response, I'll modify it.

Is on the queue, but I have something little different before in plan.

It's on to do list. :)

I have 4 articles with this format. If you have any specific topic in mind let me know.

I appreciate it. Thank you very much!

Offtopic: I saw you asked about functional programming languages in competitive programming. I am planing to do it when I have more time to practice. :)

I don't know any specific problems, but I know practice I saw some Haskell modules used it. I found the idea of combining 2 data structures itself quite intriguing, therefore the section.

Auto comment: topic has been updated by DanAlex (previous revision, new revision, compare).

Maybe ternary search trie instead of a normal trie. Note I did not read the problem.

Auto comment: topic has been updated by DanAlex (previous revision, new revision, compare).

I don't get why so little changes. Getting out of purple seems very hard.

Did 6 problem rounds become standard ?

I find this very useful. Thank a lot, will start using it.

It depends how advanced the stuff you learn is. I'd say programming has no age as long as you like it.

How to solve problem E ?

Just managed to got master. Ups, candidate master.

For me the first option is the best one as I really think is time to move forward. If you still really want to keep the old graph make it continuous somehow. (The color fields broaden or tighten constantly )

Do you know any examples for 3rd and 4th techniques ?

Good round: good problems, fast system test, fast editorial. Problem F was very nice. Did anyone solved it in a different way to the editorial ?

I can't even ...

Auto comment: topic has been updated by DanAlex (previous revision, new revision, compare).

Would that make me the first writer who participates in his round ?

It depends on what you are trying to implement. Using the cross product is actually the same as comparing the slopes , so if you want to move with a ray you should also keep a sign for upper or lower quadrants.

Thanks a lot mate. For sorting you can always use STL ( for example look here ). I will add the problems. Also we can renew the group any time if we have enough useful ideas for managing it in a better way. ;)

We fix each point as a center, therefore the O(N^2 log N) complexity.

I updated it now , should be clear :)

Auto comment: topic has been updated by DanAlex (previous revision, new revision, compare).

The first observation is valid and I messed up the example. Sorry for that and thank you.

I am also curious about a simpler approach or solving with better complexity.

I do not exactly know how to implement , but I think that thinking of the area as a difference of 2 integrals would do.

More specifically we need to find the difference between the upper and lower envelope of each cluster of circles. To do that observe that there are only O(N×N) points of interest (leftmost point of a circle , rightmost point of a circle and circle intersection points ). In other words we simply divide each circle in 4 functions and there are just some specific points when a function can surpass another.

Therefore the complexity should be O(N×N log N) due to necessity of sorting.

ffao , yeah , you're right about "approach". :))

It's probably from the way I explained the part with the 4 points. Suppose you have angles indexed from [0,360) and we count from ray [BE ( denote BE at 0 degrees ) , that would be points B,E,F,H and separate for 180 degrees we will have points B,A.

"the length of segments, that are not covered by any rectangle on the line" is ok. Substract this from "total".

Uf , lots of typos , thanks a lot mate. :D I thought initially explaining something else but then changed my mind. Yes , minimum radius is not supposed to be there. I will try to make clear explanations tomorrow.

Auto comment: topic has been updated by DanAlex (previous revision, new revision, compare).

Auto comment: topic has been updated by DanAlex (previous revision, new revision, compare).

Will fix that when I have more time. Thanks.

LE : Could not find a working one. If someone can , please PM me.

Auto comment: topic has been updated by DanAlex (previous revision, new revision, compare).

Auto comment: topic has been updated by DanAlex (previous revision, new revision, compare).

How to solve C ?

Wow , do we have a new dreamoon_love_AA : .o. ?

Fustration would normally lead to more problems solved. Just use it in your advantage. If this doesn't help , measure your problem solving skills in a constructive way.

You have a similar solution to mine. I think this might help you: http://codeforces.me/contest/567/submission/12375257

Mine is O(N^2 * K) afterall ( http://codeforces.me/contest/567/submission/12374862 ) , but it can be done in your complexity.

The round was awsome. I enjoyed a lot E and F. Congrats for the round. Also , was F a dp in O(N^3*K) ?

Very very nice problems. Big congrats ! Looking forward for the editorial.

How many problems will be ? How about scoring ?

That was way simpler than lazy propagation segment tree.

How did you solved E ? I think there must have been a lot of different solutions.

Problem E can be also solved using binary indexed trees. My solution runs in O(m+n log^2 n) , but this idea can be reduced to O(m+n log n).

I would be greatful if someone would provide me a detailed explaination of this source. Also , any other thoughts about problem B would be very helpful. Thanks ! :)

#define m ((l+r)/2)
 
int a[N*4];
 
int go(int n,int l,int r,int k,int p,int t)
{
    return t ? p < l || k > r ? 0 : k <= l && r <= p ? a[n] : max( go(n*2,l,m,k,p,1), go(n*2+1,m+1,r,k,p,1) ) : r < k || k < l ? a[n] : l == r ? a[n] = p : a[n] = max( go(n*2,l,m,k,p,0), go(n*2+1,m+1,r,k,p,0) );
}

What is happening to me ? :'(

"The final results will be announced in a day, after catching all cheaters. " ... So the ratings will change only after the final final standings ?

The trip expenses won't be covered.

Got it , thanks. Pretty simple , should have spent more time on it.

How to solve 450 and 900 ? Thanks.

As I specified , we sort the intervals ascending by left. Now let dp[i][j] = the minimum number of marked intervals between the ones among (i,i+1,...,j).

For some dp[i][j] , firstly you check if there is one interval that covers all the others in the range (i,j). If there isn't such interval will try to minimize dp[i][j] as follow:

dp[i][j] = min(dp[i][k]+dp[k][j]) , for each k from i to j-1

The solution will be in dp[1][n].

Refelecting x-coordonate and y-coordonate in parallel ?

Oh , I see. I've made the same thing by sorting intervals by left and making DP. I should have relised it was a simpler solution.

How to prove the corectitude of the 250 solution ?

Thanks.

How to solve E ?

I guess dreamoon won't be first place when he gets into div2.

Yup , also got the test file generated and couldn't hack in final 5 minutes.

I hope I change mine too.

It was quite rare for me. ( twice at the middle ) Also you can save the statements locally...

Very nice problems. Can't wait for the system test to end so I can submit solutions at C.

I liked F , but I think my solution won't pass. Also very nice E , I don't know how to solve it yet. Congrats Mike for the round !

Very nice solution ! :D Also note that all the processes described by you can be done just using binary indexed trees. ( http://codeforces.me/contest/486/submission/8697188 )

I like D , I tried to solve it ( but got TL ) with DP , ternary search and segment trees.

I liked the contest and the difficulty was ok for div2. Also , very nice problem C. Congrats !

Why is that ? ( "each component will have exactly one cycle" )

EDIT : It's ok. Saw andreyv's comment. ( and read again the statement )

How to make the flow network ?

I made a graph with costs ( edge from type1 <-> type2 with cost min(number1,number2)+1 ) and tried to add and replace edges increasingly by cost.

I have no idea what is the good abordation. Maybe some DP. I am not even sure I got the statement right.

Thanks. Lesson learned...

And congrats for the round ! I liked alot C.

I think this kind of situations should be avoided by the authors. It is really annoying to have a good solution and fail because of that.

D[i][j] is the minimum height of arriving from a cell from the exterior of the matrix to cell (i, j). Supose you are in cell (i, j) and you want to update a neighbouring cell , the cost of the neighoring cell ( let's note it (i₂, j₂) ) will be the maximum between the height of cell (i₂, j₂) ( that is a[ i₂ ][ j₂ ] ) and the height of the cell on the road to (i, j) ( that is D[i][j] ).

I add virtual lines and colums that represent the exterior of the matrix so you can arrive in a border cell (i, j) with the cost a[i][j].

Now , about lines 62-66:

while ( D[Q.front().x][Q.front().y] != Q.front().c )
{
    Q.pop();
    if ( Q.empty() ) break;
}

The cell in the front of the queue was introduced in the queue with the cost Q.front().c , but the cost of arriving in (Q.front().x,Q.front().y) might have modified , so you have another cell (Q.front().x,Q.front().y) with cost D[Q.front().x][Q.front().y] in the queue. Therefore , the element Q.front() is useless so we can pop it out of the queue.

Hope it is clear now and you enjoyed the problems. :)

Could you tell me what part you don't understand ?

I did it with DP in O(N^2), so I think it whould have been harder with a formula. ( maybe worth more points )

First of all , problems were awsome. B was harder than expected and D and E were interesting. C was maths , but I liked it.

On the other side , I think the pretests at C were weak. I put m instead of n in one place ( in a for ) and because of that it didn't passed. I think that pretests are made for this kind of situations.

I got a kind of stupid solution at B and got hacked. I passed the hack 3 seconds before end of constest. :)) I hope it passed.

Edit: It passed. :)) Thanks to the hacker.

I noticed it after 20 minutes. What about bolding these important things ? :))

Nice round. Congrats to the authors! How to solve E ?

I liked the round a lot. C was super nice , I solved it on paper with sets and an segment tree. ( but I'm not sure it's ok ) I got WA on B for something that I thought it works in O(N log N) , but got TLE. Overall , very nice round even though I think I'm going to be div2 after it. :)) Congrats for the authors !

This solution for E is very interesting. Can anyone explain me in which kind of situations is this random walk applicable ?

[ Deleted ]

Nice thing that you keep making contests constantly. You are one of my favourite authors ! Looking forward for the round!

Yup. I think a lot of sources at A will not pass...

This was way harder than usual ( at least for me ). Although , very nice problems. Big plus for the authors and waiting for your next contest !

http://mindcoding.ro/ct/mc2014r4/pb/palarb ( there is a story at beginning , skip it ) http://www.infoarena.ro/problema/hashuri ( at ending there are some links , but unfortuantely all are in Romanian — hope Google Translate makes a good job )

Very nice solution. Thanks a lot !

Actually this is how I've generated the tests , but some of them were added later. But it didn't came to my mind that this will make any difference or someone will get confused. Though , the statement was clear sorry for the inconvenience.

This worked for me too for a long period now. ( even with K smaller ) It is very usefull in a Olympiad fromat as you always make many points in short time. :)

I am pleased you took attitude against this annoying spam.

In fact at E you do not need to find the spot where you place the center. You can go with 2 pointers , one which comes from left and one from right and at every step add (a[right] — a[left]) * 2 to the solution. This is right because at each you go from the center once to right and return and then once to left and return.

At D I passed the pretests with a very bad hashing algorithm. Also I passed in O(N^2 log N) , not O(N^2). Although , for me was a great ocasion to test the speed of set and unordered_set as I was participating unoficially.

E was very nice, but quite known ideed.

EDIT: At D , there was a solution in O(N^2) without hashes , so + for the authors.

For the example the answer should be 66.

I observed that if you have a line fixed you can compute the answer, but I didn't noticed that. Now it seems kind of obvious. Thanks. :)

How to solve B ? It was awsome. :)) But I did not get the idea.

Can you explain a bit your idea , please ?