codeforces-scrape

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

519.md (5139B)


      1 Source: https://codeforces.com/blog/entry/16687
      2 
      3 ## [519A - A and B and Chess](/contest/519/problem/A "Codeforces Round 294 (Div. 2)")
      4 
      5 **Author:** [BekzhanKassenov](/profile/BekzhanKassenov "Candidate Master BekzhanKassenov")
      6 
      7 This problem asked to determine whose chess position is better.
      8 
      9 **Solution:** Iterate over the board and count scores of both player. Then just output the answer.
     10 
     11 **Complexity:** *O*(*n*2), where n is the length of the side of the board (8 here)
     12 
     13 **Code:** [10083191](/contest/519/submission/10083191 "Submission 10083191 by BekzhanKassenov")
     14 
     15 ## [519B - A and B and Compilation Errors](/contest/519/problem/B "Codeforces Round 294 (Div. 2)")
     16 
     17 **Author:** [ADJA](/profile/ADJA "Candidate Master ADJA")
     18 
     19 In this problem you were given three arrays. Second array is the same as the first array without one element, third array is the same as second array without first element. You were asked to find deleted elements.
     20 
     21 **Solution:** I'll describe easiest solution for this problem: Let's denote *a* as sum of all elements of first array, *b* as sum of all elements of second array and *c* as sum of all elements of third array. Then answer is *a* - *b* and *b* - *c*
     22 
     23 There are also some other solutions for this problem which use map, xor, etc.
     24 
     25 **Complexity:** *O*(*N*)
     26 
     27 **Code:** [10083248](/contest/519/submission/10083248 "Submission 10083248 by BekzhanKassenov")
     28 
     29 ## [519C - A and B and Team Training](/contest/519/problem/C "Codeforces Round 294 (Div. 2)")
     30 
     31 **Author:** [ADJA](/profile/ADJA "Candidate Master ADJA")
     32 
     33 In this problem we should split *n* experienced participants and *m* newbies into teams.
     34 
     35 **Solution:** Let's denote number teams with 2 experienced partisipants and 1 new participant as *type*1 and teams with 1 experienced participant and 2 new participants as *type*2. Let's fix number of teams of *type*1 and denote it as *i*. Their amount is not grater than *m*. Then number of teams of *type*2 is *min*(*m* - 2 * *i*, *n* - *i*). Check all possible *i*' and update answer.
     36 
     37 **Complexity:** *O*(*N*)
     38 
     39 **Code:** [10083265](/contest/519/submission/10083265 "Submission 10083265 by BekzhanKassenov")
     40 
     41 ## [519D - A and B and Interesting Substrings](/contest/519/problem/D "Codeforces Round 294 (Div. 2)")
     42 
     43 **Author:** [ADJA](/profile/ADJA "Candidate Master ADJA")
     44 
     45 In this problem you were asked to find number of substrings of given string, such that each substring starts and finishes with one and the same letter and sum of weight of letters of that substring without first and last letter is zero.
     46 
     47 **Solution:** Let's denote *sum*[*i*] as sum of weights of first *i* letters. Create 26 *map* < *longlong*, *int* > 's, 1 for each letter. Suppose we are on position number *i* and current character's map is *m*. Then add *m*[*sum*[*i* - 1]] to the answer and add *sum*[*i*] to the *m*.
     48 
     49 **Complexity:** *O*(*NlogN*), where *N* — the length of input string.
     50 
     51 **Code:** [10083293](/contest/519/submission/10083293 "Submission 10083293 by BekzhanKassenov")
     52 
     53 ## [519E - A and B and Lecture Rooms](/contest/519/problem/E "Codeforces Round 294 (Div. 2)")
     54 
     55 **Author**: [BekzhanKassenov](/profile/BekzhanKassenov "Candidate Master BekzhanKassenov")
     56 
     57 In this problem we have to answer to the following queries on tree: for given pairs of vertices your program should output number of eqidistand vertices from them.
     58 
     59 **Let's denote**:
     60 
     61 *dist*(*a*, *b*) as distance between vertices *a* and *b*.
     62 
     63 *LCA*(*a*, *b*) as [lowest common ancestor](https://en.wikipedia.org/wiki/Lowest_common_ancestor) of vertices *a* and *b*.
     64 
     65 *depth*[*a*] as distance between root of the tree and vertex *a*.
     66 
     67 *size*[*a*] as size of subtree of vertex *a*.
     68 
     69 On each picture green nodes are equidistant nodes, blue nodes — nodes from query.
     70 
     71 **Preprocessing**: Read edges of tree and build data structure for LCA (it is more convenient to use binary raise, becase we will use it further for other purposes).
     72 
     73 Complexity: *O*(*NlogN*)
     74 
     75 **Queries**:
     76 
     77 We have to consider several cases for each query:
     78 
     79 1) *a* = *b*. In that case answer is *n*.
     80 
     81 2) *dist*(*a*, *b*) is odd. Then answer is 0.
     82 
     83 3) *dist*(*a*, *l*) = *dist*(*b*, *l*), where *l* = *LCA*(*a*, *b*).
     84 
     85 ![ ](/predownloaded/d2/82/d282e5e8b8959d18efcf5733a3d0eca5c22ab504.jpg)
     86 
     87 Find children of *l*, which are ancestors of *a* and *b* (let's denote them as *aa* and *bb*). Answer will be *n* - *size*[*aa*] - *size*[*bb*].
     88 
     89 4) All other cases.
     90 
     91 ![ ](/predownloaded/9a/0f/9a0f57a10090a82a3bea8f923dafe9aa3f2f3d9b.jpg) ![ ](/predownloaded/f4/a3/f4a3bd7ac67445554e649dfd0e1c49010ba9c153.jpg)
     92 
     93 Assume that *depth*[*a*] > *depth*[*b*]. Then using binary raise find *dist*(*a*, *b*) / 2-th ancestor of *a* (let's denote it as *p*1), *dist*(*a*, *b*) / 2 - 1-th ancestor of vertex *a* (denote it as *p*2). Answer will be *size*[*p*1] - *size*[*p*2].
     94 
     95 Complexity: *O*(*logN*) for each query, *O*(*MlogN*) for all queries.
     96 
     97 **Resulting complexity:**: *O*(*MlogN* + *NlogN*)
     98 
     99 **Code:** [10083310](/contest/519/submission/10083310 "Submission 10083310 by BekzhanKassenov")