codeforces-scrape

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

302.md (4256B)


      1 Source: https://codeforces.com/blog/entry/7560
      2 
      3 [302A - Eugeny and Array](/contest/302/problem/A "Codeforces Round 182 (Div. 2)")  
      4 If the length of the given segment is even and count of 1 in input is not lower then half of the length of the segment and count of -1 in the input is not lower then half of the length of the segment so we have answer 1, otherwise 0.
      5 
      6 [302B - Eugeny and Play List](/contest/302/problem/B "Codeforces Round 182 (Div. 2)")  
      7 For each song we will count moment of time, when it will be over (some sums on the prefixes, for example). Further, we will use binary search of two itaratos method to solve the problem.
      8 
      9 [301A - Yaroslav and Sequence](/contest/301/problem/A "Codeforces Round 182 (Div. 1)")  
     10 Using dfs we will find number of numbers that we can set as positive. Note that we can either set all of the numbers as positive or leave one number(any) as negative. If we can obtain all numbers as positive, we just return sum of modules of the numbers, but if we cannot we will count the same sum and will subtract minimal modular value multiple 2 from sum.
     11 
     12 [301B - Yaroslav and Time](/contest/301/problem/B "Codeforces Round 182 (Div. 1)")  
     13 We will use binary search to find the answer. Further we will use Ford-Bellman algorithm. On each step we will have an array of maximum values on timer, when we stand in some point. On in transfer we will check: will our player stay alive after travelling beetwen points. If we can make transfer, we will update value of the final destination point. Becouse of a_i<=d and integer coordinates we haven't optimal cycles, and solution exists.
     14 
     15 [301C - Yaroslav and Algorithm](/contest/301/problem/C "Codeforces Round 182 (Div. 1)")  
     16 We will use ? as iterator. In the begin we will set ? before the number. Then we will move it to the end of the string. Then we will change ? to ?? and we will move it to the begin, while we have 9 before ??. If we have another digit, we just increase it, and finish the algorithm. If we have ?? at the begin, we change it to 1, and end the algorithm.
     17 
     18 Look for accepted solutions for better understanding.
     19 
     20 [301D - Yaroslav and Divisors](/contest/301/problem/D "Codeforces Round 182 (Div. 1)")  
     21 Lets add all pair: (x,y) ((d[x]%d[y]==0) || (d[y]%d[x]==0)) to some lest. We can count such pairs using Eretosphen algorithm. Here will be O(n*log(n)) sych pairs using fact, that we have permutation. We will sort all this paairs using counting-sort. Also we will sort given in input intervals. For each given interval we should count number of pairs that countained in given them . Such problem we can solve using Fenvik tree. On each step we will add segments(that are sorted by right side). On each step we will update Fenfick-tree that count number of added pairs on some suffix. Using such tree if it easy to count the answer. So we have O(n*log^2(n)) solution.
     22 
     23 [301E - Yaroslav and Arrangements](/contest/301/problem/E "Codeforces Round 182 (Div. 1)")  
     24 We will build the needed arrays sequentially adding numbers. Let's look at what states we need. First, it is obvious that you need to keep the number of ways to build an array of already added numbers, secondly you need to know the total amount of added numbers. Now let's look at what happens when we add a new number (that is greater than all of the previous in a certain amount). It is clear that the added numbers should stand between the numbers 1 to less. In this case, if we put two new numbers in a row, between them should stand more (since we already have placed less). It is obvious that you need to cover all the previous numbers (among which must stand newly added). Thus, we have another state: the number of integers between which we should put the new ones. Thus we have the dynamics of the four parameters: dp [all] [ways] [lastnumber] [counttoadd]. Transfer. It is clear that you need to add at least counttoadd numbers, but how will this affect the number of ways to arrange the numbers? It's simple. Suppose we added number x, then the number of ways to be multiplied by the value of Q (x-counttoadd, counttoadd), where Q (x, y) — the number of ways to assign the same x balls in y different boxes. Q (x, y) = C (x + y-1, y-1) where C (x, y) — binomial coefficient.