gridnevvvit's blog

By gridnevvvit, 11 years ago, translation, In English

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

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

| Write comment?
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

»
11 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

C can also be solved by sorting based on the values of |x| and |y|. :)

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

    thanks

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

    Hello Sir Why doesn't it work if sort it according to x and y axis

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

      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 .

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    I think it's just because of System.out.println("..");. You can use String builder instead.

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

      Thank you! I tried and it worked. So thanks and lot and Sorry for trying it so late.

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

      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

»
11 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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...

  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I couldnt get the statement on problem B too.

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

D is a great problem, I've learned a lot from it. Thx!

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone feel that statement in problem A is not accurate ? In the below statement:

all wrong solutions do not pass the system testing;

my understanding is that there exists a wrong solution that does not pass the system testing,

But as per the solution to the problem, it means that

no wrong solutions pass the system testing;

i.e., all wrong solutions fail the system testing.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i also find it difficult to understand, btw i did even understand the example of input and output