### gridnevvvit's blog

By gridnevvvit, 9 years ago, translation,

## 350A - TL

Let's v = min(ai), p = max(ai), c = min(bi). So, if max(2 * v, p) < c, then answer is max(2 * v, p), else answer is  - 1.

Author solution: 4632352

## 350B - Resort

Input data represents a graph, by using a array of parents of every vertex. Because every vertex has at most one parent, we can use following solution: we will go up to parent of vertex v (prev[v]) until not found vertex with the outcome degree  ≥ 2. It is better to calculate outcome degrees in advance. After all, we will update the answer.

This algorithm works in O(n).

Author solution: 4632399

## 350C - Bombs

First of all, Let's sort all point by increasing of value |xi| + |yi|, all points we will process by using this order. We will process each point greedily, by using maximum six moves. Now we want to come to the point (x, y). Let's x ≠ 0. Then we need to move exactly |x| in the dir direction (if x < 0 the dir is L, x > 0R). Similarly we will work with y-coordinates of point (x, y). Now we at the point (x, y), let's pick a bomb at point (x, y). After that we should come back to point (0, 0). Why it is correct to sort all point by increasing of Manhattan distance? If you will look at the path that we have received, you can notice that all points of path have lower Manhattan distance, i.e. we will process this points earlier.

This solution works in

Authors solution: 4632478

## 350D - Looking for Owls

It's possible to solve this problem by using only integer calculations. Normalization of the line Ax + By + C is following operation: we multiply our equation on the value , where g = gcd(A, gcd(B, C)), if A < 0 (orA = 0andB < 0) then sgn equals to  - 1, else sgn equals to 1.

Now the solution. We will have two maps (map<> in С++, TreeMap(HashMap) in Java) to a set of points (it's possible that some points will have multiply occurrence into the set). In first map we will store right boundaries of the segments, in second — left boundaries (in increasing order).

In advance for every segment we will build a normalized line, and for this normalized line we will put in our maps left and right segments of the segment.

After all, for every fixed line let's sort our sets.

Let's fix two different circles. After that, let's check that distance beetween them is greater then sum their radiuses, also you should check that circles has same radius. We can assume that we builded a line between centers of circles (x1, y1) and (x2, y2). Perpendicular to this line will have next coefficients (center of the segment [(x1, y1), (x2, y2)] also will belong to the next line) A = 2(x1 - x2), B = 2(y1 - y2), C =  - ((x1 - x2) * (x1 + x2) + (y1 - y2) * (y1 + y2)). After that you need to calculate values cntL, cntR by using binary search on set of points that lie on this line. cntL — amount of left boundaries that lie on the right side of point ((x1 + x2) / 2, (y1 + y2) / 2), cntR -- amount of right boundaries that lie on the left side of the point ((x1 + x2) / 2, (y1 + y2) / 2). After that you should add to answer value cntV - cntR - cntL,l where cntV — amount of segments, that lie on the nolmalized line.

Total complexity: .

solution: 4632546

## 350E - Wrong Floyd

Let's do the following: construct the graph with the maximum possible number of edges and then remove the excess. First of all, you can notice that if k = n answer is  - 1. Else let's fix some marked vertex, for example a1. Let's put in our graph all edges except edges beetween a1 and x, where x — an another marked vertex.

So, why this algorithm is correct? If Valera's algorithm is wrong, then there are a ''bad'' pair of vertexes (i, j). Bad'' pair is a pair for that Valera's algorithm works wrong. So, there are not marked vertex v on the shortest path from i to j, and v ≠ i, and v ≠ j. Without loss of generality, we can assume, that distance beetween i and j equals to 2, but Valera's algorithm gives greater answer. There are some cases, that depends on the type of vertexes i, j. But we can look only at the case where (i, j) are marked vertexes. First, add to the graph all edges beetween not fixed (i, j) vertexes. Second, add to the graph edges beetween some fixed vertex (i or j) and some not marked vertex. Third, add to the graph edges beetween i and some marked vertex v, where v ≠ j. It's simple to understand, that if we add some another edge, the Valera's algorithm will work correctly. Total amount of edges is .

BONUS Simple bonus. For same contrains (n, m, k) can you build a graph, where Valera's code works correctly?

Код: 4632600

• +28

 » 9 years ago, # |   0 For E Bonus: for k>=1, build a star with any marked vertex(i.e. all nodes are connected directly to marked vertex k.),then continue to build extra edges until the number of edges = m.Proof: it is clear that the maximum value of pair-wise distance of nodes <= 2 in a star. Also, distance = 1 if and only if there is a path directly connecting those two nodes.(even though the two nodes are both unmarked, their distance is defined as 1 if they are directly connected.) If there are no path between two nodes, the marked node will also provide a "island" for them to finish a path with distance 2. therefore the graph is correct.k=0 is possible if and only if (m==(n*(n-1))) or (m<=n/2)
 » 9 years ago, # | ← Rev. 2 →   0 C can also be solved by sorting based on the values of |x| and |y|. :)
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 thanks
•  » » 2 years ago, # ^ |   0 Hello Sir Why doesn't it work if sort it according to x and y axis
•  » » » 16 months ago, # ^ |   0 You might have got the solution by now .But if you didn't then here is how .Let's consider Bomb positions ( after sorting) = { (-3,-3) ,(-3,-2),(-2,-3) } So you do the operations to diffuse bomb at position (-3 , -3 ) first . And for this you will have to go either through (-2 , -3) or (-3,-2) which isn't allowed .PS : You can also change the direction of your path that is you can move to other points to avoid (-2 , -3) or (-3 , -2 ) but again that will require more direction changes which increase the total number of operations .
 » 9 years ago, # |   0 My solution for C problem in java is similar to author's solution but I am getting Time out for the solution. Don't know where am I doing the heavy operation. My solution id is 4639684
•  » » 9 years ago, # ^ |   0 I think it's just because of System.out.println("..");. You can use String builder instead.
•  » » » 9 years ago, # ^ |   0 Thank you! I tried and it worked. So thanks and lot and Sorry for trying it so late.
•  » » » 9 years ago, # ^ |   0 does that apply to cout in c++ because I also solved it in the same way and I am getting TLE , here is my submission
•  » » » » 9 years ago, # ^ |   0 Not to cout, but to endl. Use '\n' instead.
•  » » » » » 9 years ago, # ^ |   0 ok , thanks :)
•  » » » » » 2 years ago, # ^ |   0 Hello Sir, Why doesn't it work if we sort according to x and then y axis
 » 9 years ago, # |   0 Problem B can be solved without any dfs techniques as pointed in the question tags, by spending some memory. http://codeforces.com/contest/350/submission/4647033
 » 9 years ago, # |   -8 i found the statements very hard to understand for example on problem E it sais that the graph shoud not contain any loops, what i get from this is that the graph is a tree , also i couldnt get the statement on problem B . i know my english sux but still...
•  » » 9 years ago, # ^ |   +1 I couldnt get the statement on problem B too.
 » 9 years ago, # |   0 D is a great problem, I've learned a lot from it. Thx!
 » 3 years ago, # | ← Rev. 2 →   0 deleted
 » 2 years ago, # | ← Rev. 2 →   0 Can someone help me understand the first sample test to 350A - TL? If the answer is 5, do not all the correct submissions(4, 5, 2) pass the sys.test WITHOUT extra time(a)?
•  » » 2 years ago, # ^ |   0 My doubt is same. If the answer of first sample test is 5 then their wouldn't be any correct answer to pass with extra time. And also taking 5 would mean first incorrect answer(ie 6) would pass with extra time. In case you now know the answer kindly tell.
•  » » » 2 years ago, # ^ |   0 op_panda here extra time means there should be one integer for all correct solution that satisfies the condition 2*(interger for correct solution) <= V(expected time limit).Hope you understand this point.
•  » » » » 23 months ago, # ^ |   0 thanks mate :)
 » 21 month(s) ago, # |   0 Why we need to sort in C? I cannot understand it. Can someone explain?
•  » » 21 month(s) ago, # ^ |   0 Never mind I got it.
 » 10 months ago, # |   0 Anyone please explain the logic behind the 350A . If max(2 * v, p) < c, then answer is max(2 * v, p), else answer is  - 1.