codeforces-scrape

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

486.md (6761B)


      1 Source: https://codeforces.com/blog/entry/14678
      2 
      3 [486A - Calculating Function](/contest/486/problem/A "Codeforces Round 277 (Div. 2)")
      4 
      5 If *n* is even, then the answer is *n* / 2, otherwise the answer is (*n* - 1) / 2 - *n* =  - (*n* + 1) / 2.
      6 
      7 [486B - OR in Matrix](/contest/486/problem/B "Codeforces Round 277 (Div. 2)")
      8 
      9 Hint of this problem is presented in its statement. "![](https://espresso.codeforces.com/661f67f4b56b351d145dce2e9a87cd7c5f6a4d64.png) where ![](https://espresso.codeforces.com/7bcdd7440cc300269a3395fa037d5af6351c3221.png) is equal to 1 if some *a**i* = 1, otherwise it is equal to 0."
     10 
     11 To solve this problem, do 3 following steps:
     12 
     13 1. Assign all *a**ij* (1 ≤ *i* ≤ *m*, 1 ≤ *j* ≤ *n*) equals to 1.
     14 2. If some *b**ij* = 0, then do assignments: *a**ik* = *a**tj* = 0 (1 ≤ *k* ≤ *n*, 1 ≤ *t* ≤ *m*) (that means, assign all elements in row *i* and column *j* of matrix *a* to 0).
     15 3. Then we have matrix *a* which need to find. Just check whether from matrix *a*, can we produce matrix *b*. If not, the answer is obviously "NO".
     16 
     17 Complexity: We can implement this algorithm in *O*(*m* * *n*), but it's not neccesary since 1 ≤ *m*, *n* ≤ 100.
     18 
     19 [486C - Palindrome Transformation](/contest/486/problem/C "Codeforces Round 277 (Div. 2)")
     20 
     21 Assuming that cursor's position is in the first half of string(*i*.*e* 1 ≤ *p* ≤ *n* / 2) (if it's not, just reverse the string, and change *p* to *n* - *p* + 1, then the answer will not change).
     22 
     23 It is not hard to see that, in optimal solution, we only need to move our cusor in the first half of the string only, and the number of "turn" is at most once.
     24 
     25 Therefore, we have below algorithm:
     26 
     27 * Find the largest index *r* before *p* in the first half of the string (*p* ≤ *r* ≤ *n* / 2) such that *s**r* different to *s**n* - *r* + 1. (*s**i* denote *i**th* character of our input string *s*)
     28 * Find the smallest index *l* after *p* (1 ≤ *l* ≤ *p*) such that *s**l* different to *s**n* - *l* + 1.
     29 * In optimal solution, we move our cusor from *p* to *l* and then from *l* to *r*, or move from *p* to *r* and then from *r* to *l*. While moving, we also change character of string simultaneously (if needed) (by press up/down arrow keys).
     30 
     31 Be careful with some corner case(for example, does'nt exist such *l* or *r* discribed above).
     32 
     33 Complexity: *O*(*n*).
     34 
     35 [486D - Valid Sets](/contest/486/problem/D "Codeforces Round 277 (Div. 2)")
     36 
     37 * Firstly, we solve the case *d* =  + ∞. In this case, we can forget all *a**i* since they doesn't play a role anymore. Consider the tree is rooted at node 1. Let *F**i* be the number of valid sets contain node *i* and several other nodes in subtree of *i* ("several" here means 0 or more). We can easily calculate *F**i* through *F**j* where *j* is directed child node of *i*: ![](https://espresso.codeforces.com/90ad3bd47e8c794d6fa7ac47cf3b973f561313b7.png). Complexity: *O*(*n*).
     38 * General case: *d* ≥ 0. For each node *i*, we count the number of valid sets contain node *i* and some other node *j* such that *a**i* ≤ *a**j* ≤ *a**i* + *d* (that means, node *i* have the smallest value *a* in the set). How? Start DFS from node *i*, visit only nodes *j* such that *a**i* ≤ *a**j* ≤ *a**i* + *d*. Then all nodes have visited form another tree. Just apply case *d* =  + ∞ for this new tree. We have to count *n* times, each time take *O*(*n*), so the overall complexity is *O*(*n*2). (Be craeful with duplicate counting)
     39 
     40 [Here](//codeforces.com/contest/486/submission/8669623) is my code.
     41 
     42 [486E - LIS of Sequence](/contest/486/problem/E "Codeforces Round 277 (Div. 2)")
     43 
     44 LIS = Longest increasing subsequence.
     45 
     46 #### Solution 1 (Most of participant's solutions):
     47 
     48 * Let *F*1*i* be the length of LIS ending exactly at *a**i* of sequence {*a*1, *a*2, ..., *a**i*} and *D*1*i* is the number of such that LIS.
     49 
     50 * Let *F*2*i* be the length of LIS beginning exactly at *a**i* of sequence {*a**i*, *a**i* + 1, ..., *a**n*} and *D*2*i* is the number of such that LIS.
     51 
     52 * // Calculates *F*1*i* and *F*2*i* is familiar task, so I will not dig into this. For those who have'nt known it yet, this [link](http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence) may be useful)
     53 * // We can calculate *D*1*i* and *D*2*i* by using advanced data structure, like BIT or Segment tree.
     54 * *l* = length of LIS of {*a*1, *a*2, ..., *a**n*} = *max*{*F*1*i*} = *max*{*F*2*j*}.
     55 * *m* = number of LIS of {*a*1, *a*2, ..., *a**n*} = ![](https://espresso.codeforces.com/5494cd80687769b5d94b3b63790823db9b957e92.png)
     56 * Let *C**i* be the number of LIS of {*a*1, *a*2, ..., *a**n*} that *a**i* belongs to. Index *i* must in group:
     57 
     58   1) if *C**i* = 0
     59 
     60   2) if 0 ≤ *C**i* < *m*
     61 
     62   3) if *C**i* = *m*
     63 * How to calculate *C**i*? If (*F*1*i* + *F*2*i* - 1 < *l*) then *C**i* = 0, else *C**i* = *D*1*i* * *D*2*i*. Done!
     64 
     65 We have an additional issue. The number of LIS of {*a*1, *a*2, ..., *a**n*} maybe very large! *D*1*i*, *D*2*i* and *m* maybe exceed 64-bits integer. Hence, we need to store *D*1*i*, *D*2*i* and *m* after modulo some integer number, call it *p*.
     66 
     67 Usually, we will choose *p* is a prime, like 109 + 7 or 109 + 9. It's not hard to generate a test such that if you choose *p* = 109 + 7 or *p* = 109 + 9, your solution will lead to Wrong answer. But I have romeved such that tests, because the data tests is weak, even *p* is not a prime can pass all tests.
     68 
     69 #### Solution 2:
     70 
     71 // Some notation is re-defined.
     72 
     73 * Let *F*1*i* be the length of LIS ending exactly at *a**i* of sequence {*a*1, *a*2, ..., *a**i*}.
     74 * Let *F*2*i* be the length of LIS beginning exactly at *a**i* of sequence {*a**i*, *a**i* + 1, ..., *a**n*}.
     75 * *l* = length of LIS of {*a*1, *a*2, ..., *a**n*} = *max*{*F*1*i*} = *max*{*F*2*j*}.
     76 * Let *F**i* be the length of LIS of sequence {*a*1, *a*2, ..., *a**i* - 1, *a**i* + 1, ..., *a**n*} (i.e the length of LIS of initial sequence *a* after removing element *a**i*).
     77 * Index *i* must in group:
     78 
     79   1) if *F*1*i* + *F*2*i* - 1 < *l*, otherwise:
     80 
     81   2) if *F**i* = *l*
     82 
     83   3) if *F**i* = *l* - 1
     84 * How to caculate *F**i*? We have: *F**i* = *max*{*F*1*u* + *F*2*v*} among 1 ≤ *u* < *i* < *v* ≤ *n* such that *a**u* < *a**v*. From this formula, we can use Segment tree to calculate *F**i*. Due to limitation of my English, it is really hard to write exactly how. I will post my code soon.
     85 
     86 Complexity of both above solution: *O*(*nlogn*).