codeforces-scrape

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

617.md (3435B)


      1 Source: https://codeforces.com/blog/entry/22971
      2 
      3 [617A - Elephant](/contest/617/problem/A "Codeforces Round 340 (Div. 2)")
      4 
      5 It's optimal to do the biggest possible step everytime. So elephant should do several steps by distance 5 and one or zero step by smaller distance. Answer equals to ![](https://espresso.codeforces.com/7db446b074534bfc1be809dc5c8f6b31c9219f5e.png)
      6 
      7 Solution [15550796](/contest/617/submission/15550796 "Submission 15550796 by komendart")
      8 
      9 [617B - Chocolate](/contest/617/problem/B "Codeforces Round 340 (Div. 2)")
     10 
     11 We are given array which contains only ones and zeroes. We must divide it on parts with only one 1.
     12 
     13 Tricky case: when array contains only zeroes answer equals to 0.
     14 
     15 In general. Between two adjacent ones we must have only one separation. So, answer equals to product of values *pos**i* - *pos**i* - 1 where *pos**i* is position of i-th one.
     16 
     17 Bonus: what's the maximal possible answer for *n* < 100?
     18 
     19 Solution [15550806](/contest/617/submission/15550806 "Submission 15550806 by komendart")
     20 
     21 [617C - Watering Flowers](/contest/617/problem/C "Codeforces Round 340 (Div. 2)")
     22 
     23 First radius equals to zero or distance from first fountain to some flower. Let's iterate over this numbers. Second radius equals to maximal distance from second fountain to flower which doesn't belong to circle with first radius. Now we should choose variant with minimal *r*12 + *r*22.
     24 
     25 Bonus: It's *O*(*n*2) solution. Can you solve problem in *O*(*nlogn*)?
     26 
     27 Solution *O*(*n*2) [15550812](/contest/617/submission/15550812 "Submission 15550812 by komendart")
     28 
     29 Solution *O*(*nlogn*) [15550822](/contest/617/submission/15550822 "Submission 15550822 by komendart")
     30 
     31 [617D - Polyline](/contest/617/problem/D "Codeforces Round 340 (Div. 2)")
     32 
     33 Answer equals to one if all coordinates x or y of points are same.
     34 
     35 When answer equals to two? Let's iterate over all pairs of points. Let first point in pair is beginning of polyline, second point is end. Only one or two such polylines with answer two exist. If third point is on the polyline it belongs to rectangle with corners in first two points. We can just check it.
     36 
     37 Else answer equals to three. We can build vertical lines which contains the most left and the most right point and horizontal line through third point. If we erase some excess rays we will get polyline.
     38 
     39 Solution [15550843](/contest/617/submission/15550843 "Submission 15550843 by komendart")
     40 
     41 [617E - XOR and Favorite Number](/contest/617/problem/E "Codeforces Round 340 (Div. 2)")
     42 
     43 We have array *a*.
     44 
     45 Let's calculate array *pref* (*pref*[0] = 0, ![](https://espresso.codeforces.com/d2d26f54b218b77fb18c0d01231511907b494163.png)).
     46 
     47 Xor of subarray *a*[*l*...*r*] equals to ![](https://espresso.codeforces.com/5d9344069c27412caa1180d3543155331180e297.png).
     48 
     49 So query (l, r) is counting number of pairs *i*, *j* (*l* - 1 ≤ *i* < *j* ≤ *r*) ![](https://espresso.codeforces.com/256577bedfd2b78f87fed741eb241dc03b3734ef.png).
     50 
     51 Let we know answer for query (l, r) and know for all *v* *cnt*[*v*] — count of *v* in *a*[*l* - 1...*r*]. We can update in O(1) answer and *cnt* if we move left or right border of query on 1. So we can solve problem offline in ![](https://espresso.codeforces.com/c0dc39f34ba8c3c2f560af9c33a9fd70d7ca53e5.png) with sqrt-decomposion (Mo's algorithm).
     52 
     53 Solution [15550846](/contest/617/submission/15550846 "Submission 15550846 by komendart")