### gridnevvvit's blog

By gridnevvvit, 7 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 Tutorial of Codeforces Round #203 (Div. 2) Tutorial of 1st weekly contest 203, Comments (17)
 » 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)
 » 7 years ago, # | ← Rev. 2 →   C can also be solved by sorting based on the values of |x| and |y|. :)
•  » » 3 months ago, # ^ | ← Rev. 2 →   thanks
•  » » Hello Sir Why doesn't it work if sort it according to x and y axis
 » 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
•  » » I think it's just because of System.out.println("..");. You can use String builder instead.
•  » » » Thank you! I tried and it worked. So thanks and lot and Sorry for trying it so late.
•  » » » 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
•  » » » » Not to cout, but to endl. Use '\n' instead.
•  » » » » » ok , thanks :)
•  » » » » » Hello Sir, Why doesn't it work if we sort according to x and then y axis
 » 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
 » 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...
•  » » I couldnt get the statement on problem B too.
 » D is a great problem, I've learned a lot from it. Thx!
 » What's the matter? Why is my 350C code o (n) or tle? var n,i,t,h:longint; res,ord:array[0..1000000]of longword; a,b,c,d:array[0..1000000]of word; p,q:array[0..100000]of longint; cnt:array[0..65535]of longint; begin readln(n); for i:=1 to n do begin readln(p[i],q[i]); if p[i]=0 then h:=h+4 else if q[i]=0 then h:=h+4 else h:=h+6; end; for i:=1 to n do begin t:=p[i]+q[i]; a[i]:=t>>16; b[i]:=t and (1<<16-1); inc(cnt[b[i]]); end; for i:=0 to 65534 do inc(cnt[i+1],cnt[i]); for i:=1 to n do begin ord[cnt[b[i]]]:=i; dec(cnt[b[i]]); end; fillchar(cnt,sizeof(cnt),0); for i:=1 to n do inc(cnt[a[i]]); for i:=0 to 65534 do inc(cnt[i+1],cnt[i]); for i:=n downto 1 do begin res[cnt[a[ord[i]]]]:=ord[i]; dec(cnt[a[ord[i]]]); end; writeln(h); for n:=1 to n do begin i:=res[n]; if p[i]>0 then writeln('1 ',abs(p[i]),' R'); if p[i]<0 then writeln('1 ',abs(p[i]),' L'); if q[i]>0 then writeln('1 ',abs(q[i]),' U'); if q[i]<0 then writeln('1 ',abs(q[i]),' D'); writeln(2); p[i]:=-p[i];q[i]:=-q[i]; if p[i]>0 then writeln('1 ',abs(p[i]),' R'); if p[i]<0 then writeln('1 ',abs(p[i]),' L'); if q[i]>0 then writeln('1 ',abs(q[i]),' U'); if q[i]<0 then writeln('1 ',abs(q[i]),' D'); writeln(3); end; end. 
 » 46 hours ago, # | ← Rev. 2 →   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)?