codeforces-scrape

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

416.md (5545B)


      1 Source: https://codeforces.com/blog/entry/12277
      2 
      3 #### [416A - Guess a number!](/contest/416/problem/A "Codeforces Round 241 (Div. 2)")
      4 
      5 Let's use the usual Div 2 problem A approach — the naive one. We will track the interval which might contain the number we're guessing. With each of the query we update this interval. If at the end the interval is non-empty then we output any number from it, otherwise the result is "Impossible".
      6 
      7 Submission: [6606892](/contest/416/submission/6606892 "Submission 6606892 by marat.snowbear")
      8 
      9 #### [416B - Art Union](/contest/416/problem/B "Codeforces Round 241 (Div. 2)")
     10 
     11 All we need is to iterate over all painters and for each painter to iterate over all pictures. In the inner loop we also remember when the painter finished working on the picture to make sure that the next painter will not start working on it earlier.
     12 
     13 Submission: [6606994](/contest/416/submission/6606994 "Submission 6606994 by marat.snowbear")
     14 
     15 #### [416C - Booking System](/contest/416/problem/C "Codeforces Round 241 (Div. 2)")
     16 
     17 Let's solve this one greedy. All we need to notice is that the optimal solution will be to place first the groups with biggest sum which they are ready to pay. For each such group it will be optimal to allocate the smallest matching table. The input limits allow to do a full search when looking for a table.
     18 
     19 Submission: [6617198](/contest/416/submission/6617198 "Submission 6617198 by marat.snowbear")
     20 
     21 #### [416D - Population Size](/contest/416/problem/D "Codeforces Round 241 (Div. 2)")
     22 
     23 One thing to notice for this problem is that if we cover some interval with a progression then it will better (at least no worse) to include as many elements to the right of it as possible. So the solution is to greedy — find the leftmost number not covered by a progression, start a new progression with that number (the interval covered by that progression will be of size 1) and then try to extend this interval to the right as far as possible. Repeat this step until all the numbers are covered. One thing you should pay attention to is which numbers can be covered by one arithmetic progression, for example:
     24 
     25 * If there are no fixed numbers in the interval then we can cover it with one progression.
     26 * If there is only one non-fixed number in the interval then we can cover this interval with one progression.
     27 * If there are more than one non-fixed numbers in the interval then we can calculate the parameters of the progression (start value and difference). All non-fixed numbers should match those parameters. Difference should be integer.
     28 * If the progression is ascending and there are some non-fixed numbers in the beginning then those numbers should match **positive** numbers in the progression.
     29 * Same way if the progression is descending then we can include numbers from the right side only while matching progression term is positive.
     30 
     31 Submission: [6607174](/contest/416/submission/6607174 "Submission 6607174 by marat.snowbear")
     32 
     33 #### [416E - President's Path](/contest/416/problem/E "Codeforces Round 241 (Div. 2)")
     34 
     35 Let's look at the graph given to us in the example:
     36 
     37 ![ ](https://assets.codeforces.com/images/416/illustration_416_E_1.png)
     38 
     39 We need to count the count of the edges on all the shortest paths between each pair of vertices. Let's do something easier first — instead of counting all the edges we will count only those which have the destination vertex on its side. For example here are the edges belonging to shortest paths from 4 to 2 which are connected to vertex 2:
     40 
     41 ![ ](https://assets.codeforces.com/images/416/illustration_416_E_2.png)
     42 
     43 Let's denote this number like this: *inEdges**source*, *v* — number of edges which go into vertex *v* on some shortest path from *source* to *v*. In the given example *inEdges*4, 2 = 3. Let's also denote the set *S**source*, *dest* — it is a set of the vertices which belong to at least one shortest path from *source* to *dest*. For example *S*4, 2 = {1, 2, 3, 4}. With these two variables it can be seen that the answer for vertices *source* and *dest* will be:
     44 
     45 ![](https://espresso.codeforces.com/acca1f5ea0320d6e51ce8c834aadd936dc38b0b9.png)
     46 
     47 In other words the answer for vertices *s* and *d* will be equal to the sum of *inEdges**s*, *v* for all vertices *v*, which belong to any shortest path from *s* to *d*. So the only thing left is to calculate these *S* and *inEdges*. Both of them can be easily calculated if you have minimum distances between all pairs of vertices. And these distances can be calculated using the Floyd-Warshall. So the full solution is:
     48 
     49 1. Calculate minimum distances between all pairs of vertices using Floyd-Warshall algorithm.
     50 2. Count *inEdges*. Simply iterate over all source vertices and all edges. For each edge check whether any of its ends belong to any shortest path from source.
     51 3. Calculate the answer. Let's have three loops to iterate over the vertices — — *source*, *destination* и *mid*. First two vertices are those for which we're calculating the answer. Third vertex is the vertex which should belong to any shortest path (basically we're checking whether *v* belongs to *S**source*, *dest*). If *mid* belongs to any shortest path from *source* to *dest* then we add *inEdges**source*, *mid* to the answer.
     52 
     53 Each step has a complexity *O*(*n*3).
     54 
     55 Submission: [6607257](/contest/416/submission/6607257 "Submission 6607257 by marat.snowbear")
     56 
     57 P.S.: Please feel free to let me know about any typos, errors, etc using the private messages.