codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

141.md (3691B)


      1 Source: https://codeforces.com/blog/entry/3571
      2 
      3 [141A - Amusing Joke](/contest/141/problem/A "Codeforces Round 101 (Div. 2)")
      4 
      5 It was enough for solving this problem to calculate for each letter: *a**c* - amount of occurrences of letter *c* in first and second strings in input, *b**c* - amount of occurrences of letter *c* in third string in input. If ![](https://espresso.codeforces.com/92d8c13f4cb833bb849f3ebb4c155e65a63e3468.png) the answer is "YES" else "NO".
      6 
      7 [141B - Hopscotch](/contest/141/problem/B "Codeforces Round 101 (Div. 2)")
      8 
      9 Let's bust the "level" 0 ≤ *i* ≤ 106, in which assumedly the stone could hit. Let’s find the minimal number of square on this level. Then we can understand, how many squares there are on this level: one or two. Then we check with one or two ifs (if on this level two squares) if the stone is in corresponding square or not. If the stone is inside then output the answer. If we didn't find any square, where the stone is, output "-1".
     10 
     11 [141C - Queue](/contest/141/problem/C "Codeforces Round 101 (Div. 2)")
     12 
     13 Let's sort the pairs (*name**i*, *a**i*) by ascending of *a**i*. If there is an index i: 0 ≤ *i* < *n* that *a**i* > *i*, then answer is "-1". Otherwise the answer exists. We will iterate through the array of sorted pairs from left to right with supporting of vector of results *res*. Let on the current iteration *a**i* = *n* - *i*, then we must transfer the current man in the position *a**i*. It can be done in C++ with one line: res.insert(res.begin() + a[i], man);
     14 
     15 [141D - Take-off Ramps](/contest/141/problem/D "Codeforces Round 101 (Div. 2)")
     16 
     17 Let's generate the weighted directed graph of all ramps. The graphs' vertexes are the important points on the line *Ox*, there are points: 0, *L*, *x**i* - *p**i*, *x**i* + *d**i*. The graphs' edges are the possible ramp jumps: transfer from point *x**i* - *p**i* to point *x**i* + *d**i* or transfer from vertex in neighboring vertexes (neighboring means that we get the next and previous important points on the line). The weights of these edges are correspondingly *p**i* + *t**i* and *x**v* + 1 - *x**v*, *x**v* - *x**v* - 1. We must note that in the transfers we can't get in the negative part of *Ox*, and we must delete this transfers.
     18 
     19 Then we must find and output the shortest path in this graph from vertex 0 to *L*. This can be done, for example, with Dijkstra's algorithm for the sparse graphs.
     20 
     21 [141E - Clearing Up](/contest/141/problem/E "Codeforces Round 101 (Div. 2)")
     22 
     23 In this problem we must find the minimum spanning tree, in which the half of edges are marked with letter 'S'.
     24 
     25 There are  *n* - 1 edges in this tree, because of it if *n* is even then the answer is "-1".
     26 
     27 Let's delete from the given graph all S-edges. And there are *cnt* components in obtained graph. For making this graph be connected we must add *cnt* - 1 edges or more, that's why if *cnt* - 1 > (*n* - 1) / 2 the answer is "-1". Then we find *cnt* - 1 S-edges, that we must add to the graph, so that it become connected. If *cnt* - 1 < (*n* - 1) / 2 then we will try to add in this set of edges another S-edges, so that the S-edges don't make circle. We must do all of this analogically to Kruskal's algorithm of finding a minimum spanning tree. If we could get a set of S-edges of (*n* - 1) / 2 elements, that there are exactly *cnt* - 1 edges and no S-circles, then the answer exists, Then we must add to this set (*n* - 1) / 2 M-edges, that forms with our set of edges the minimum spanning tree, it must be done analogically with Kruskal's algorithm.