codeforces-scrape

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

285.md (2223B)


      1 Source: https://codeforces.com/blog/entry/7093
      2 
      3 [285A - Slightly Decreasing Permutations](/contest/285/problem/A "Codeforces Round 175 (Div. 2)")
      4 
      5 As the answer you can print such permutation: *n*, *n* - 1, ..., *n* - *k* + 1, 1, 2, ..., *n* - *k*. For example, if *n* = 5, *k* = 2, then the answer is: 5, 4, 1, 2, 3. If *k* = 0, you should print 1, 2, ..., *n*. Such solution can be written in two loops.
      6 
      7 [285B - Find Marble](/contest/285/problem/B "Codeforces Round 175 (Div. 2)")
      8 
      9 It is known that a permutation can be considered as set of cycles. The integer *i* moves to *p*[*i*] for all *i* (1 ≤ *i* ≤ *n*). You can start moving from integer *s* along the cycle. If you find integer *t*, then print the length of the path. If you return to *s*, then print  - 1.
     10 
     11 [285C - Building Permutation](/contest/285/problem/C "Codeforces Round 175 (Div. 2)")
     12 
     13 The solution of the problem is rather simple. Sort all integers *a* and then make from integer *a*[1] integer 1, from integer *a*[2] integer 2 and so on. So, integer *a*[*i*] adds to the answer the value |*a*[*i*] - *i*|. The answer should be count in 64-bit type. You can simply guess why such solution is correct.
     14 
     15 [285D - Permutation Sum](/contest/285/problem/D "Codeforces Round 175 (Div. 2)")
     16 
     17 For a start, describe bruteforce solution. Firstly, we will always assume, that *a* is identity permutation, that is *a*[*i*] = *i*. In this case, the answer should be multiplied by *n*!. Or in other way your bruteforce will not be counted. Secondly, using our bruteforce we can see, that for even *n* the answer is 0.
     18 
     19 What do you also need to get accepted? First case is to calculate answers for all *n* on your computer and write them in constant array. In other words you can make precalc. Second case is to make you solution faster. The soltuion using meet-in-the-middle idea works fast for *n* ≤ 15. If you remember that for even *n* answer is 0 then you can get accepted using such solution. But other simple bruteforces and dynamic programmings on maps work slower than 3 seconds.
     20 
     21 [285E - Positions in Permutations](/contest/285/problem/E "Codeforces Round 175 (Div. 2)")