is there a math approach to Problem B? like GCD o like that? Because i tried with diophantine equation, but i can't solve it!

I am using a map for the third problem but i can't understand why my solution is showing time limit exceeded, here is my solution http://codeforces.net/contest/681/submission/18472898. plz help, I then tried to further optimize by removing a a for loop inside but then it is giving memory limit exceeded, here is my modified code http://codeforces.net/contest/681/submission/18475008. Plz help.

My submission for problem C timed out because I used cin/cout -_-.

In E, I got a TLE on one of the pretests for reading the input as doubles instead of integers. Is it really necessary to have such strict time limits just for reading the input?

Disappointed with my performance on C. Timed out when using std::to_string, but passes if I keep a pair of string and int. Not a fan of problems that require fast in/out optimizations, but I understand why they're necessary.

WA: http://codeforces.net/contest/681/submission/18463859 AC: http://codeforces.net/contest/681/submission/18481068

Any proof for problem C?

For D, I think this is simpler solution (with idea by P___):

Note that a man v may want to give gift either to himself or to the same guy as a direct parent of v wants. Otherwise v and his parent have a conflict. Then we simply DFS and check this for each node, and after leaving the node, we add the node to the answer only if it wants to give present to itself. We can do it because if the man is in someone's preference, he has to give his present to himself, otherwise they have a conflict.

Submission: 18481462

[SOLVED}Can anyone help me look at my problem E code? I keep getting WA in question 29, and I even carefully studied the editorial's code, and feel like my code is doing exactly the same?

Where am I going wrong?

Thanks for the help:

http://codeforces.net/contest/681/submission/18482766

EDIT: Found my stupid mistake, nevermind

Problem D: We don't even need to make topsort, just go up for every vertex i until we found a_i or a marked vertex (if it marked not as a_i, then  - 1), and mark on this path all vertices as a_i (it means, that vertex has a passing path to the a_i), because all path shouldn't be intersected. And answer will be list of distinct a_i sorted by height in the tree.

Code: 18471518

Anyone used unordered_set for B? I just brute forced every possible combination of (a,b) and matched with values from c. Actually didn't time out. I feel so lucky.

My code is the same as the code presented in problem C, but done in Java 8. I used a priority queue, but it still times out on test 10. I don't know what else I could implement for this problem. Any help would be appreciated. Here is the code: http://codeforces.net/contest/681/submission/18484919

Thanks for a good contest.Enjoyed solving good problems.

D could be done very easily in 20 lines. Link

D could be done very easily in 20 lines. Link

This is how, I solved problem D.

If a person gifts to himself, no problem. If person gifts to its ancestor 'x', then its parent must also gift to 'x', this way we can go to top following the parent pointer,till person doesn't gift himself. We can do this for all leaf nodes, If its successful, answer exist else -1.

Now, how to print answer, just print all unique a[i]'s in the order they appear in Topological sort, as topological sort (not necessarily unique) is kind-of ordering which should appear first & which one later.

http://codeforces.net/contest/681/submission/18495490

It would really be helpful, if the setter/tester code given in Editorial had meaningful variable names. E.g. Problem D have array names inA, a, r which are hard to follow and understand.

Also, few one line comments would also be helpful.

I would be very thankful, if the moderator/setter/tester can please put effort in this direction,

can anybody help me improve my code of problem C its in python 2. i am getting time limit exceeded in test 26. 18502038

for div2D http://codeforces.net/blog/entry/45404?#comment-299935

what does this mean?? " For every vertex (man) from current vertex subtree (i.e. for vertices whose ancestor is current vertex) such that we still don't know whom will this vertex (man) give a gift to, stays that these vertices would give a gift to current vertex, because it is their first ancestor in the list. " please elaborate someone?

I will never love geometry >_>

Problem E: I have seen some accepted codes as well as the code given in the tutorial. But one thing I am not understanding why I have to calculate the angle using both asin and acos. Whats the difference? For example (tutorial code)-

double tLen = sqrt(d * d - 1.0 * r * r);
    if (tLen < r0 + eps) {
        ang = asin(r / d);
    } else {
        ang = acos((d * d + r0 * r0 - 1.0 * r * r) / (2 * d * r0));
    }

My code is giving tle on using normal for loop. But, replacing the same with "for(auto& p : ans)" gets the code accpeted.

My code:

#include <iostream>
#include <queue>
#include <string>
 using namespace std;
// struct comparator {
//  bool operator()(int i, int j) {
//  return i > j;
//  }
// };

int main()
{

    // ios_base::sync_with_stdio(false);
    // cin.tie(0);
	int t;
	string ops[] = {"sd","insert","removeMin","getMin"};
	vector <pair<int,int> > v;
	scanf("%d",&t);
	priority_queue<int> minHeap;

	for(int i = 0;i<t;i++)
	{
		string op;
		int x;
		cin >> op;
		//if(op != "removeMin")
		//	cin>>x;

		if(op == "insert")
		{
			cin>>x;
			minHeap.push(-x);
			v.push_back(pair<int,int>(1,x));
		}
		else if(op=="getMin")
		{
			cin>>x;
			while(!minHeap.empty() && -minHeap.top() < x)
			{
				minHeap.pop();
				v.push_back(pair<int,int>(2,0));
			}

			if(minHeap.empty() || -minHeap.top() > x)
			{
				minHeap.push(-x);
				v.push_back(pair<int,int>(1,x));
			}

			v.push_back(pair<int,int>(3,x));
		}
		else 
		{
			if(minHeap.empty())
			{
				v.push_back(pair<int,int>(1,1));
			}
			else
				minHeap.pop();

			v.push_back(pair<int,int>(2,x));
		}
	}

	cout<< v.size()<<endl;

	for(int i = 0;i<v.size();i++)       //this loops gives tle
	{	
		if(v[i].first == 2)
			cout<<ops[v[i].first]<<endl;
		else
			cout<<ops[v[i].first]<<" "<<v[i].second<<endl;
	}

	// for (auto& p : v) {                   //this loops gets accepted
 //        cout << ops[p.first];
 //        if (p.first != 2) {
 //            cout << " " << p.second;
 //        }
 //        cout << "\n";
 //    }

	return 0;
}

Please Help.

Задача 681D. Почему не заходит получение последовательности(ответа) как нужных вершин с компаратором (tin[b] <= tin[a] && tout[b] >= tout[a])?

Is there any precision mistake for E?

For 3rd test case which is

0 0 1 2

2

2 0 1

-2 0 1

The point of intersection of a circle with radius 2 and centre at the origin with the other two are {(1.75000000,-0.96824584),(1.75000000 0.96824584)} and {(-1.75000000,-0.96824584),(-1.75000000 0.96824584)} respectively and the angle subtended by both the arc in total i.e. total surviving angle as mentioned in the editorial is 2.0214420411 (1.0107210206 by each arc and both are non-overlapping) and so surviving_angle/2*PI is 0.3217225 whereas the given answer is 0.333333

Can someone please verify this ?? (both the point of intersection are correct) my submission