codeforces-scrape

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

599.md (5844B)


      1 Source: https://codeforces.com/blog/entry/21685
      2 
      3 Problem A.
      4 
      5 Everything that you needed to do — solve some similar cases.
      6 
      7 You need to check the following cases:
      8 
      9 * Home ![](https://espresso.codeforces.com/70a0795f45d32287dba0eb83fc4a3f470c6e5537.png) the first shop ![](https://espresso.codeforces.com/70a0795f45d32287dba0eb83fc4a3f470c6e5537.png) the second shop ![](https://espresso.codeforces.com/70a0795f45d32287dba0eb83fc4a3f470c6e5537.png) home
     10 * Home ![](https://espresso.codeforces.com/70a0795f45d32287dba0eb83fc4a3f470c6e5537.png) the first shop ![](https://espresso.codeforces.com/70a0795f45d32287dba0eb83fc4a3f470c6e5537.png) the second shop ![](https://espresso.codeforces.com/70a0795f45d32287dba0eb83fc4a3f470c6e5537.png) the first shop ![](https://espresso.codeforces.com/70a0795f45d32287dba0eb83fc4a3f470c6e5537.png) home
     11 * Home ![](https://espresso.codeforces.com/70a0795f45d32287dba0eb83fc4a3f470c6e5537.png) the second shop ![](https://espresso.codeforces.com/70a0795f45d32287dba0eb83fc4a3f470c6e5537.png) home ![](https://espresso.codeforces.com/70a0795f45d32287dba0eb83fc4a3f470c6e5537.png) the first shop ![](https://espresso.codeforces.com/70a0795f45d32287dba0eb83fc4a3f470c6e5537.png) home
     12 * Home ![](https://espresso.codeforces.com/70a0795f45d32287dba0eb83fc4a3f470c6e5537.png) the second shop ![](https://espresso.codeforces.com/70a0795f45d32287dba0eb83fc4a3f470c6e5537.png) the first shop ![](https://espresso.codeforces.com/70a0795f45d32287dba0eb83fc4a3f470c6e5537.png) the second shop ![](https://espresso.codeforces.com/70a0795f45d32287dba0eb83fc4a3f470c6e5537.png) home
     13 
     14 Time: *O*(1)
     15 
     16 Problem B.
     17 
     18 First of all, you should read the statement carefully. Then, for every element 1 ... *N* create a list of integers from what we can get this number.
     19 
     20 After that you have to check some cases, before that create a special mark for answer *Ambiguity*:
     21 
     22 Let current element of the given array is *b**i*
     23 
     24 * If two or more elements exist from which it's possible to get *b**i*, then use your special mark that answer is *Ambiguity*
     25 * If no elements exist from which it's possible to get *b**i*, then print *Impossible*
     26 * If only one element exists from which it's possible to get *b**i* just change *b**i* to the value of this element
     27 
     28 Finally, if you marked your special mark then print *Ambiguity*, else print *Possible* and correct answer.
     29 
     30 Time: *O*(*N*)
     31 
     32 Problem C.
     33 
     34 Let's take a minute to see how the best answer should look like.
     35 
     36 Let *H**i* be a sorted sequence of *h**i*. Let ***E*** — set of indices of the last elements of each block. Then ![](https://espresso.codeforces.com/fdc680037a1862069351e3c1b78ad73566b699d5.png) *e* ![](https://espresso.codeforces.com/ebd0354d208474a4f5b8b1639fb842e4e46a2b00.png) ***E***, first *e* sorted elements of sequence *h**i* are equal to the first *e* elements of the sequence *H**j*.
     37 
     38 So, it is not difficult to notice that the size of ***E*** is the answer for the problem.
     39 
     40 Firstly, we need to calculate two arrays: *prefmax* and *suffmin*, where *prefmax**i* — maximum between *a*1, *a*2, ..., *a**i*, and *suffmin**i* — minimum between *a**i*, *a**i* + 1, ..., *a**n*.
     41 
     42 If you want to get the answer, just calculate the number of indices *i* that *prefmax**i*  ≤  *suffmin**i* + 1.
     43 
     44 Time: *O*(*N*)
     45 
     46 Problem D.
     47 
     48 First of all, let's solve this problem for *n* ≤ *m*, and then just swap *n* and *m* and print the answer. Important! Not to print squares twice!
     49 
     50 We can use this formula for fixed *n* & *m* (*n* ≤ *m*) for calculating the value of *x*. ![](https://espresso.codeforces.com/ecd5a33ad84bfb17fb168424e54dd0cef26f151f.png)
     51 
     52 Then ![](https://espresso.codeforces.com/46756fb00622752812ecefd8ae394605094d6f0c.png)
     53 
     54 Using the sum squares and the sum of the first *k* numbers we can easily solve this problem.
     55 
     56 Getting 6*x* = 6*n*2 * *m* - 3(*n*2 + *n*3 - *nm* - *n*2) + 2*n*3 - 3*n*3 + *n* = 3 * *m* * *n*2 + 3 * *m* * *n* - *n*3 + *n*
     57 
     58 As we solved this task for *n* ≤ *m* the 3*n*2 * *m* =  ≈ *n*3, it means that *n* is not greater than ![](https://espresso.codeforces.com/1301345aa07d38c23eecde4fca1c89000c2b8a7c.png).
     59 
     60 Time: ![](https://espresso.codeforces.com/12886d463e3433367254b40d155728d8f48b50c9.png)
     61 
     62 Problem E.
     63 
     64 The solution for this problem is dynamic programming.
     65 
     66 Let *f**root*, *mask* is the number of ways to build a tree with root in vertex *root* using vertices from the mask *mask* and all restrictions were met. For convenience we shall number the vertices from zero.
     67 
     68 The answer is *f*0, 2*n* - 1.
     69 
     70 Trivial states are the states where a mask has only one single bit. In such cases *f**root*, *mask* = 1.
     71 
     72 Let's solve this task recursively with memorization. To make the transition, we need to choose some kind of mask *newMask*, which is **necessarily is the submask** of mask *mask*. Then we should try to find new root *newRoot* in mask *newMask*. Also, in order not to count the same tree repeatedly impose conditions on the mask *newMask*. Namely, we shall take only such masks *newMask*, in which the senior bit (not in charge of the *root*) coincides with a senior bit (not in charge of the *root*) of the mask *mask*. After that, you need to check the fulfillment of all conditions to the edges and to the lca. If everything is OK, update ![](https://espresso.codeforces.com/37362612b90e324322451eee03a0b6982f0a7b18.png). Where ![](https://espresso.codeforces.com/4ce1dcdcb7e402d6b40e3250035be66695c3decf.png) means ***xor***.
     73 
     74 What about checking lca, it's possible to do it in time *O*(*N*2) — previously memorized lca for each pair or in the worst case in time *O*(*Q*) just iterating through all pairs of vertices, for which some vertex *v* is lca.
     75 
     76 Time: *O*(3*N*·*N*3) or *O*(3*N*·*N*·*Q*)