.tx's blog

Codeforces Round #357 (Div. 2) Editorial
By .tx, history, 8 years ago, translation, In English

681A - Хороший контест

If for any participant beforei ≥ 2400 and afteri > beforei, then the answer is "YES", otherwise "NO"

Code

681B - Экономическая игра

We can simply try every a from 0 to n / 1234567 and b from 0 до n / 123456, and if n - a * 1234567 - b * 123456 is non-negative and divided by 1234, then the answer is "YES".

If there is no such a and b, then the answer is "NO".

Code

681C - Операции с кучей

Let's solve this problem with greedy approach. Let's apply operations from log in given order.

If current operation is insert x, then add element x to heap.

If current operation is removeMin, then if heap is not empty, then simply remove minimal element, otherwise if heap is empty, add operation insert x, where x can be any number, and then apply removeMin

If current operation is getMin x then do follows:

  1. While heap is not empty and its minimal element is less than x, apply operation removeMin.
  2. Now if heap is empty or its minimal element is not equal to x, apply operation insert x.
  3. Apply operation getMin x.

In order to fit time limit, you need to use data structure, which allows you to apply given operations in O(logN) time, where N is a number of elements in it. For example, std::priority_queue or std::multiset.

Code

681D - Подарки по списку

Formal statement of the problem:

You have a directed acyclic graph, every vertex has at most one ingoing edge. Vertex A is an ancestor of vertex B if there is a path from A to B in graph. Also every vertex is an ancestor of itself.

Every vertex i has a pair – vertex ai, ai – ancestor of i.

You need to build such sequence of vertex, that for every vertex i the leftmost vertex in the sequence which is ancestor of i must be equal to ai.

Or you need to tell, that such sequence does not exists.

Solution:

Assume sequence ans, which contains every vertex from sequence an by once and only them. Let's order elements of this sequence in such way, that for every i and j if ansi – ancestor of ansj, then i ≥ j.

If this sequecne is the answer, then print it. Otherwise, there is no answer.

Why?

  1. If some vertex ai from sequence a in not present in ans, then a man, who needs to give a gift to a man number ai, will not be able to do it. So every vertex ai must have place in the resulting sequence.

  2. If ai – ancestor of aj and i < j, then a man, who needs to give a gift to a man number aj will not be able to do it.

How can we build this sequence?

Let's sort vertices topologically, than reverse it and remove redundant vertices.

Now we need to check if that this sequence can be the answer.

Let's calculate to whom every man will give his gift. At start for any man we don't know that. Let's iterate through vertices of the resulting sequence.

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.

Iterate through that vertices (men) in dfs order and remember for them, to whom they will give their gift.

After we apply this operation to all vertices from resulting sequence, compare for each man to whom he will give his gift and to whom he needs to give his gift. If there is at least one mismatch, then the answer doesn't exist.

Code

681E - Побег в тень

At first assume the case when cockroach at the moment 0 is already inside or on the border of some circle. In that case the cockroach will always survive, i. e. the probability is 1.

Otherwise the cockroach will have time to run to every point inside the circle with center of x0, y0 and radius v × t.

Let's iterate through all the shadow circles and figure out how each circle relates to "cockroach circle". We want to find the maximum angle, such that choosing the direction from this angle the cockroach will have enough time to reach current circle and survive.

In general, maximal "surviving" angle, such that choosing the direction from it the cockroach will reach the circle in infinite time – is an angle between two tangents from a start point to the circle. If length of this tangents is not greater than v × t, then this angle is the needed one.

Otherwise we need to find intersections of cockroach circle and current circle. If there is no intersection points or there is only one, then current circle is too far away from cockroach. Otherwise intersection points and start point form the needed angle for this circle.

After we've found all the angles, we can figure out that those angles are segments that cover a segment from 0 to 2π. Sort their ends and find a length of their union. This length divided by 2π will give us the answer.

Code

  • Vote: I like it
  • +36
  • Vote: I do not like it

Comments Comments (45)
| Write comment?
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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!

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Mine is a faster solution, which uses some math, but it's not O(1).

    Let p = 1234567, q = 123456, r = 1234 .

    Note that .

    Let i be inverse of r wrt p

    pa + rc = n - qb

    Now, for all non-negative values of b, such that qb <  = n, is the minimum non negative possible value of c. Find a corresponding to this value, and if it is  >  = 0, then there exists a non negative triple.

    Gives answer in O(n/123456)

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    No. This is the Frobenius Postage Stamp problem, which doesn't have any closed solutions for more than 2 summands. See https://en.wikipedia.org/wiki/Coin_problem You can of course solve it with Euclid's algorithm, but some coefficients might be negative. Getting a solution for positive integers is a much harder problem.

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    Something interesting: because of the Frobenius problem, any number higher than 27406117 will always result in "YES".

    During the contest, I used this fact to recursively brute-force check the remaining 27 million integers.

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like 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.com/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.com/contest/681/submission/18475008. Plz help.

→ Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

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?

→ Reply
»
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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.com/contest/681/submission/18463859 AC: http://codeforces.com/contest/681/submission/18481068

→ Reply
»
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Any proof for problem C?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Seems everyone knows it is a gready problem...

    → Reply
»
8 years ago, # |
  Vote: I like it +35 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Yeah I was just solving it out of competition now, and that's actually pretty much what I did, I had just missed one edge case. I was pushing the index into the answer vector if it hadn't been pushed before, not only if it was giving it to himself.

    Which would fail when a node has several children, and all it's descendants of a branch are giving gifts to it, but some descendants in other branches aren't.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Then you probably got WA on pretest 6. I had the same problem and noticed that we can push just when a node gives a gift to himself. However I don't consider this as an edge case. You would have to sort nodes by depth and make them unique to make your approach somehow working.

      → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

[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.com/contest/681/submission/18482766

EDIT: Found my stupid mistake, nevermind

→ Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

Code: 18471518

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Infact,O(n/1234567 ★ n/123456) is pretty quick, even it is brute force.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That's very true. I tried using normal set first on my machine, but it seemed very slow, so I had to use unordered_set instead.

      → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.com/contest/681/submission/18484919

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    System.out.print is slow in Java. Try using a StringBuilder or PrintWriter. I believe it will pass as syso is enough to cause TLE in this problem.

    → Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Thanks for a good contest.Enjoyed solving good problems.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

D could be done very easily in 20 lines. Link

→ Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.com/contest/681/submission/18495490

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    There are so many ways to do D. Mine is,

    In the problem you are given a forest of directed trees, build the LCA using Nodes which are root( Root have in-degree 0 ).

    dp[i][j] stores information for LCA.
    dp2[i][j] stores the number of requested ancestor from i to i's (2^j-1) parent.

    Any node u is a requested ancestor if it occurs in request of some i.

    Now just do LCA type skipping between the requested ancestor of every i by taking difference of their levels(They can be in different sub trees too, that is why we need to check at last that the skipping leads to same requested ancestor) and also the sum the path , this will tell us whether their are no nodes in between which are requested ancestor. Just check it for all that it is possible to have A[i] as the ancestor.

    If yes sort the requested ancestors on the basis of decreasing levels ( Take an example you will understand why).

    18476129

    → Reply
»
8 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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,

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    The operation of remove min that you have is O(n) That is to say, every time you remove a min, you perform an scan through the whole list ( min(n) ) in orther to find the minimum and then remove it.

    The thing is that your algotirthm is O(n^2) which is a high complexity for the size of n (10^5).

    I recommend you to read about priority_queue datastructure and it's implementation through a binary heap and not an array (as you do). The binary heap perform removeMin operation in O(logn) time. So if you use it, your algorithm would be O(nlogn) which is acceptable.

    https://en.wikipedia.org/wiki/Heap_(data_structure)

    EDIT: I also append the time complexity of the operations in python

    https://wiki.python.org/moin/TimeComplexity

    Hope it helps :)

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it

I will never love geometry >_>

Screenshot
→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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));
    }
→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I also didn't get it. If someone could explain why divide in two cases, it would be of great help.

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Ah, I get it now.

    The two cases are: when the range will be determined by the lines tangent to the cirumference which pass through the cockroach's starting point and when the range will be determined by the lines which pass through the cockroach's starting point and the points of intersection between the two circumferences. You can determine which case is this by comparing the length of the segment from the point of tangency to the cockroach's starting point (tLen) and r0.

    In the first case, the angle can be determined through triangle similarity. In the second case, you may derive the equation from the triangle formed by the center of both circumferences and a point of intersection.

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    cout << endl;

    is slow, because it flushes stdout each time used.

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Why are you inserting -x in the priority queue, instead of x? Even the author has done the same thing, what is the logic behind this. UPD :- i got the reason, it is because by default the priority_queue is a max_heap, we can use this trick to convert it into min_heap.

    → Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

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

→ Reply