Блог пользователя .tx

Автор .tx, история, 8 лет назад, По-русски

681A - A Good Contest

Если хотя бы для одного участника beforei ≥ 2400 и afteri > beforei, то ответ "YES", иначе "NO"

Код

681B - Economy Game

Ограничения в этой задаче таковы, что можно перебрать a от 0 до n / 1234567 и b от 0 до n / 123456, и проверить, что n - a * 1234567 - b * 123456 не отрицательно и делится на c.

Если хотя бы одна такая пара чисел a и b нашлась, то ответ "YES", иначе "NO"

Код

681C - Heap Operations

Будем решать эту задачу жадно. Выполняем оставшиеся запросы в порядке, в котором они нам даны.

Если текущий запрос – insert x, то добавим элемент x в кучу.

Если текущий запрос – removeMin, то если куча не пуста, то просто удалим минимум, а если куча пуста, то вставим запрос insert x, где x – любое число, и затем выполним removeMin

Если текущий запрос – getMin x то выполним следущее:

  1. Пока куча не пуста и минимальный элемент в ней меньше x, выполним запрос удаления минимума из кучи.
  2. Если куча пуста или минимальный элемент в ней не равен x, выполним запрос insert x.
  3. Выполним запрос getMin x.

Для того, чтобы уложиться в ограничение по времени, необходимо использовать структуру данных, которая поддерживает выполнение описанных операций за время O(logN), где N – количество элементов. Например, можно было использовать, std::priority_queue или std::multiset.

Код

681D - Gifts by the List

Формальная постановка задачи:

Дан ориентированный граф без циклов, в каждую вершину входит не более одного ребра (лес "ориентированных деревьев"). Вершина A является предком вершины B, если из A есть путь в B. Также каждая вершина является предком самой себя.

Каждой вершине i сопоставим вершину ai, причем ai – предок i.

Необходимо построить последовательность вершин, такую что для любой вершины i самая первая вершина в последовательности, являющаяся предком i, была равна вершине ai. Либо сказать, что такой последовательности не существует.

Решение:

Рассмотрим последовательность ans, содержащую по одному разу все вершины, встречающихся в последовательности an, и только их. Расположим элементы этой последовательности так, чтобы для любых i и j если ansi – предок ansj, то i ≥ j.

Если эта последовательность является ответом, то выведем её. Иначе, ответа не существует.

Почему это так.

  1. Если какая-то вершина ai из последовательности a не встречается в ans, то мужчина, который должен подарить подарок мужчине с номером ai, не сможет этого сделать. Значит каждая вершина ai должна быть в результирующей последовательности.

  2. Если ai – предок aj и i < j, то мужчина, который должен подарить подарок мужчине с номером aj не сможет этого сделать.

Как получить такую последовательность?

Построим топологическую сортировку вершин графа, то есть такую последовательность вершин, в которой каждый предок идет первее любого своего потомка, затем развернем её и выбросим все лишние вершины.

Как проверить, что последовательность является ответом?

Давайте вычислим, кому будет дарить подарок каждый мужчина. Изначально для каждого мужчины мы не знаем, кому он будет дарить подарок. Переберем вершины результирующей последовательности по порядку.

Для всех вершин (мужчин) из поддерева текущей вершины (т. е. для вершин, для которых текущая вершина является предком), для которых мы не знаем, кому эта вершина (мужчина) будет дарить подарок верно, что эти вершины будут дарить подарок текущей вершине, потому что текущая вершина – самый первый их предок из списка.

Пройдем dfs'ом по всем этим вершинам и запомним в них, кому будет подарен подарок.

После того как мы выполним эту операцию для всех вершин результирующей последовательности, сравним для каждой вершины графа актуальную вершину, которой мы будем дарить подарок, и требуемую. Если есть хотя бы одно несовпадение, то ответа не существует.

Код

681E - Runaway to a Shadow

Для начала разберем случай, когда таракан в момент старта уже находится внутри или на границе какого-то круга. В этом случае, таракан всегда спасется, т. е. вероятность равна 1.

Иначе у таракана есть время, чтобы добежать в любую точку круга с центром в точке x0, y0 радиуса v × t.

Переберем все круги-тени и для каждого поймем как соотносится этот круг с кругом достижимых точек таракана. А именно, найдем максимальный допустимый угол, такой что выбрав направление из этого угла таракан успеет спастись, добежав до текущего круга.

Вообще говоря, максимальный угол, выбрав направление из которого таракан за бесконечное время добежит до круга, – это угол, образованный двумя касательными из точки старта таракана к окружности. Если длины этих касательных не превосходят v × t, то этот угол и будет являться искомым углом для текущего круга.

Иначе найдем точки пересечения границы "тараканьего круга" и границы текущего круга (т. е. пересечем две окружности). Если точек пересечения нет, или она одна (окружности касаются), то текущий круг слишком далеко от таракана. Иначе точки пересечения и точка старта образуют искомый угол для текущего круга.

После того как нашли все углы понимаем, что это отрезки, покрывающие отрезок от 0 до . Сортируем их начала и концы и находим длину объединения этих отрезков. Длина объединения, деленная на , дает нам искомую вероятность выживания.

Код

Разбор задач Codeforces Round 357 (Div. 2)
  • Проголосовать: нравится
  • +36
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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!

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    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)

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    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.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

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://mirror.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://mirror.codeforces.com/contest/681/submission/18475008. Plz help.

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

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?

»
8 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Any proof for problem C?

»
8 лет назад, # |
  Проголосовать: нравится +35 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

EDIT: Found my stupid mistake, nevermind

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Thanks for a good contest.Enjoyed solving good problems.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

D could be done very easily in 20 lines. Link

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

D could be done very easily in 20 lines. Link

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
8 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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,

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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 :)

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
8 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

I will never love geometry >_>

Screenshot
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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));
    }
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    cout << endl;
    

    is slow, because it flushes stdout each time used.

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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