Ok.

So exchange argument forwarded is. Start with an optimal solution. And show that we can transform from optimal to our solution without changing "disturbance " at any step we are doing the transformation. While I understand the disturbance not changing anywhere except between i-1, i and mirror of it. Not clear, how it is is proved in the original argument provided by the op that the disturbance of combined disturbance (i, i-1) and mirror is same in the optimal before and after the transformation, which op n as can be easily shown.

If you have any idea around will be thankful for that.

Sorry again, to ask you a question for the solution not provided by you.

Apologies if it is asking too much.

With ref to this comment https://mirror.codeforces.com/blog/entry/135421?#comment-1211619

How can we prove the correctness with exchange argument ? Assuming that we have a optimal solution and we can swap reverse the subarray between (i, n-i). ?

_ So the overall answer will only change due to the change in this part, which we can easily show, will not worsen if we swap it._

How can we show that ? I am not getting any idea around that.

Please find my solution at : http://mirror.codeforces.com/contest/1054/submission/44512450

The algorithm I am following is this,

for each student, find out how many student have more chocolates than him, by adding l[i] and r[i].

This basically gives the standard competition ranking. see[1].

Next step is I am simply verifying if the ranking I am getting is a standard competition ranking.

And chocolate distribution is (n-rank[i])

My solution is failing on test case 6. And I am not able to download the whole test case( it is big).

Any body will be kind enough to point out what I am doing wrong ?

[1]. https://en.wikipedia.org/wiki/Ranking#Standard_competition_ranking_(%221224%22_ranking)

Basically what this is saying is, if parent(a) is visited before parent(b) then a must be visited before b.

Am I right ?

Div-2 C : How to convince or prove that, the procedure listed in the solution in exhaustive. That is sum of three inverse selection is indeed removing all the triangles with non-positive area.

Starting from left, If you can fell a tree left, make it go left else if you can fell it on right make it go right.

Why this works ? If you are falling left then it is easy to see that you are not spoiling the chance of the next tree. The option for next tree is open.

If you are falling the tree to right, may be there is a possibility that the right tree can't fall left. Only thing is worst case scenario you have to select only one of this tree.

To be fair, Peter Norvig's sample size would be less. It would be naive to discard comments from person of stature as Mr. Norvig. Still, I would be careful to generalise such comments.

"remove loops", did you mean self loops ?

Also how can be there at most 26 edges a->c..z, b->c..z , this configuration has more than 26 edges.

I assume I misunderstood something. Can you, please, clarify further, if possible with an example ?

Can you elaborate the DP solution ? I.e. How will you break this into subproblem ?

Also, bump.

This is the approach, I had used for a successful submission in the past. The cats can only get hold of the mouse if cat, mouse, cat form a diagonal of a square. Any where else the mouse will reach the boundary before any of the cat.

Just need to verify if the diagonal condition is satisfied.

Most probbably this "i <= size — ai" should be "i <= size — ai-1" or "<=" should be "<".

After you find a boundary ( top, bottom, left, right), my idea is to convert every cell inside the boundary to "." .

I tried to solve problem D in the following,

Find the connected components from the given maze. And also find the boundary of the connected component.( top,bottom, left,right). And make all the cells in the maze which lies in the boundary to ".".

Also kind of handled case like this with double run of algo.

.... .... ..*.. ...*. ....*

Is there anything wrong with this approach ? This approach was failing for test case 12.

Edit : I think what I said was wrong.

Yes, something like this might happened. Thank you for a nice link.

Yes, seems magical. Did spent quite some time yesterday. Didn't disassemble as could not produce on local. I did played around quite some using the "custom invocation" of the code forces and have noticed the following(not sure how relevant they are).

1. The problem seems to be, the set is counting some "similar" doubles as different. the results produce using scanf is always higher than what it should result from cin(which we think is right)
2. If I change to float the behaviour is same for cin and scanf.
3. If I use iterator and simply iterate over the slopes set before the calling cout<<slopes.size() and getting the right results.
4. Personally feeling may be scanf is setting constant or variable which is affecting the double comparison on the set.

Whatever be the case, please update if anybody find the reason for anomaly.

Ok, so the algo subtracts one from the first sequence which is 1 and splits the second sequence which is 2 to 1+1.

Thanks.

Can anyone explain the example test case and some other test case for Div 2 500 ?

5 2 Returns: 4 One optimal solution: {5} -> {2,3} -> {1,2} -> {1,1} -> {}. We used two splits: once when splitting the sequence of 5 carts into 2+3 and the second time when splitting the sequence of 2 carts into 1+1.

I don't understand how from state {1,2} transition in to {1,1}. It talks about split but doesn't the split of 2 should result {1,2} -> {1,1,1} ?

Not sure what I am misunderstanding in this question ?

I think because of less contestants and and also found less submission in Div 2. Once they put the stats, can confirm one or the other.

My solution also similar I think

Organising in two or three different days of week and two different times will help everybody to participate.

If it helps :

if(d - (inc * a) * p[i] >= 0){

This is the line where the overflow is happening for you, looks like for the test case 17(first one, at least), inc * a * p[i] is out of int range. I think most people have written the check if(d/p[i] - inc * a >= 0 ) {

I think sorting is not stable.

bool f(pii i, pii j)
{
	return (i.first<j.first)||((i.first<j.first)&&(i.second<j.second));
}

May be the left of the "or" condition was not intentional. I think the following was your intention

bool f(pii i, pii j)
{
	return (i.first<j.first)||((i.first==j.first)&&(i.second<j.second));
}

Your compare

return (abs(a.x)==abs(b.x))?(abs(a.y)<abs(b.y)):(abs(a.x)<abs(b.x));

is different to the op. You are checking equality for the abs while op is not.

Looks like recursion depth. May be could not allocate enough stack.

Little tangent, but second cmp ( sort comparison function) is not right.

For both calls, cmp( (5,100), (-5,100)), cmp( (-5,100), (5,100)) it returns true. It breaks transitivity. http://en.wikipedia.org/wiki/Comparison_sort

Same here. It was very difficult understanding the problem B. But looking into the submissions in the room, I was skeptical of making my comment. I think we as a community will benefit if the problems are better written.

Valid point. But I assume one reason may be challenge phase. If there is no registration there might not be fair and optimal way of room assignment as every body will simply log on at the time of the competition.

For Div-2 B my approach,

Find the minimum d ( minimum amount which takes to paint a digit with highest index) and divide the total paint by min d. This number gives total no of digits which can be painted. i.e. the answer will have this many digits.

Now only thing you can do is, if there is still left over paint ( total paint — paint used upto this point ), you can improve, in the sense you can replace already used digit and left over paint with a higher digit by using greedy method.

Repeat the improvement until you have some left over paint and there is a digit with higher index which you can replace.

My Solution

No problem at all. Actually, this is way I was trying to prove that any configuration possible not for even n.

I just got proved that if n is even and if it is not divisible by 4 then there is no configuration with the above reasoning.

If you get the proof using the above logic please let me know.

Please correct me if I am wrong, but I am not getting the proof.

When you say even-odd pairs, does that mean all the evens come from A and all the odds from B. But, we can still get n/2 odd by mixture of ( E,O) And (O,E). Precisely n/4 (E,O) and n/4 (O,E). And same applies for getting n/2 evens. In essence this points that we can still gets the even-odd configuration.

Problem C, Do the n elements for which we can change the sign needs to be consecutive ?

May be system is experiencing some load. Request are getting timed out.