codeforces-scrape

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

631.md (6781B)


      1 Source: https://codeforces.com/blog/entry/43551
      2 
      3 [631A - Interview](/contest/631/problem/A "Codeforces Round 344 (Div. 2)")
      4 
      5 You should know only one fact to solve this task: ![](https://espresso.codeforces.com/c34940621af58759ab118bc8b99e57e43b4dd36c.png). This fact can be proved by the [truth table](https://en.wikipedia.org/wiki/Truth_table). Let's use this fact: ![](https://espresso.codeforces.com/7e53766bec66c314d02297ffee851e7bd27ec64d.png). Also ![](https://espresso.codeforces.com/90b860f25f0eb1f9e6de084d95d04135afe92a21.png). According two previous formulas we can get that *f*(*a*, 1, *n*) ≥ *f*(*a*, *i*, *j*). Finally we can get the answer. It's equal to *f*(*a*, 1, *N*) + *f*(*b*, 1, *N*).
      6 
      7 Time: ![](https://espresso.codeforces.com/92de30bfabf583a2c3a88f74b1d279cf6e3b0abf.png)
      8 
      9 Memory: ![](https://espresso.codeforces.com/92de30bfabf583a2c3a88f74b1d279cf6e3b0abf.png)
     10 
     11 [C++](//www.codeforces.com/contest/631/submission/16501234) [Python3](//www.codeforces.com/contest/631/submission/16501281)
     12 
     13 [631B - Print Check](/contest/631/problem/B "Codeforces Round 344 (Div. 2)")
     14 
     15 Let's define *timeR**i* as a number of last query, wich repaint row with number *i*, *timeC**j* – as number of last query, wich repaint column with number *j*. The value in cell (*i*, *j*) is equal *a**max*(*timeR**i*, *timeC**j*).
     16 
     17 Time: ![](https://espresso.codeforces.com/f316db23879960331b379f2afde64878fdd16964.png)
     18 
     19 Memory: ![](https://espresso.codeforces.com/a7f4ad8b5132a2829b6b18c049f2f17636435a0b.png)
     20 
     21 [C++](//www.codeforces.com/contest/631/submission/16501244) [Python3](//www.codeforces.com/contest/631/submission/16501289)
     22 
     23 [631C - Report](/contest/631/problem/C "Codeforces Round 344 (Div. 2)")
     24 
     25 If we have some pair of queries that *r**i* ≥ *r**j*, *i* > *j*, then we can skip query with number *j*. Let's skip such queries. After that we get an array of sorted queries (*r**i* ≤ *r**j*, *i* > *j*). Let's sort subarray *a*1..*max*(*r**i*) and copy it to *b*. For proccessing query with number *i* we should record to *a**r**i* - 1..*r**i* first or last(it depends on *t**i* - 1) *r**i* - 1 - *r**i* + 1 elementes of *b*. After that this elements should be extract from *b*. You should remember that you need to sort subarray *a*1..*r**n*, after last query.
     26 
     27 Time: ![](https://espresso.codeforces.com/c8cd97be9399344d0317745bcd02cd569492a8d7.png)
     28 
     29 Memeory: ![](https://espresso.codeforces.com/d6bf4dffa897d5aeafe1abd778c79469b2a9e318.png)
     30 
     31 [C++](//www.codeforces.com/contest/631/submission/16501250) [Python3](//www.codeforces.com/contest/631/submission/16501304)
     32 
     33 [631D - Messenger](/contest/631/problem/D "Codeforces Round 344 (Div. 2)")
     34 
     35 Let's define *S*[*i*] as *i* - *th* block of *S*, *T*[*i*] — as *i* - *th* block of *T*.Also *S*[*l*..*r*] = *S*[*l*]*S*[*l* + 1]...*S*[*r*] and *T*[*l*..*r*] = *T*[*l*]*T*[*l* + 1]...*T*[*r*].
     36 
     37 *T* is substring of *S*, if *S*[*l* + 1..*r* - 1] = *T*[2..*m* - 1] and *S*[*l*].*l* = *T*[1].*l* and *S*[*l*].*c* ≥ *T*[1].*c* and *S*[*r*].*l* = *T*[*m*].*l* and *S*[*r*].*c* ≥ *T*[*m*].*c*. Let's find all matches of *T*[*l* + 1..*r* - 1] in *S* and chose from this matches, witch is equal *T*.You can do this by Knuth–Morris–Pratt algorithm.
     38 
     39 This task has a some tricky test cases:
     40 
     41 1. ![](https://espresso.codeforces.com/1606f89b7374dff1927c8603ae3d2abf6a8396fc.png) and ![](https://espresso.codeforces.com/f256b8bb0d2c0bcb6dacd44ae6c2665f76b406f8.png). Letters in the adjacent blocks are may be same.This problem can be solved by the union of adjacent blocks with same letter.
     42 2. ![](https://espresso.codeforces.com/4607da7553c25e13bc375d26804153859f979bcc.png) and ![](https://espresso.codeforces.com/3fe1b1befd7f9025cb6fc600392537e73cbfbf58.png). Count of *T* blocks are less than 3. Such cases can be proccess singly.
     43 3. ![](https://espresso.codeforces.com/1e3258a042463a3689497da82b4d9966456cb004.png) and ![](https://espresso.codeforces.com/6c3b6010cfda0802686117b0dce4b88550cf7aff.png). Answer for this test should be stored at long long.
     44 
     45 Time: ![](https://espresso.codeforces.com/d6bf4dffa897d5aeafe1abd778c79469b2a9e318.png)
     46 
     47 Memory: ![](https://espresso.codeforces.com/d6bf4dffa897d5aeafe1abd778c79469b2a9e318.png)
     48 
     49 [C++](//www.codeforces.com/contest/631/submission/16501261)[Python3](//www.codeforces.com/contest/631/submission/16501311)
     50 
     51 [631E - Product Sum](/contest/631/problem/E "Codeforces Round 344 (Div. 2)")
     52 
     53 ![](https://espresso.codeforces.com/740d5974c151726d49a533f2a6ce31411d71daaa.png)
     54 
     55 The operation, which has been described in the statement, is cyclic shift of some subarray. Let's try to solve this problem separately for left cyclic shift and for right cyclic shift. Let's define ![](https://espresso.codeforces.com/18e619f29056e45425e2c3c1a4a5c06bc6f030aa.png) as answer before(or without) cyclic shift, Δ*ans* = *ans* - *ans*' — difference between answer after cyclic shift and before. This difference can be found by next formulas:
     56 
     57 For left cyclic shift:
     58 
     59 Δ*l*, *r* = (*a**l*·*r* + *a**l* + 1·*l* + ... + *a**r*·(*r* - 1)) - (*a**l*·*l* + *a**l* + 1·(*l* + 1) + ... + *a**r*·*r*) = *a**l*·(*r* - *l*) - (*a**l* + 1 + *a**l* + 2 + ... + *a**r*)
     60 
     61 For right cyclic shift:
     62 
     63 Δ'*l*, *r* = (*a**l*·(*l* + 1) + *a**l* + 1·(*l* + 2) + ... + *a**r*·*l*) + (*a**l*·*l* + *a**l* + 1·(*l* + 1) + ... + *a**r*·*r*) = (*a**l* + *a**l* + 1 + ... + *a**r* - 1) + *a**r*·(*l* - *r*)
     64 
     65 You can find this values with complexity ![](https://espresso.codeforces.com/34429d3fd71191b755681162f135c11209a37d16.png), using prefix sums, ![](https://espresso.codeforces.com/b00b89b0310a720e2837b87b0551a3b164f59f0e.png).
     66 
     67 ![](https://espresso.codeforces.com/fea7aeb47cde5897a9049f1b89f84b6ad37a08fc.png)
     68 
     69 Let's try to rewrite previous formulas:
     70 
     71 For left cyclic shift: Δ*l*, *r* = (*a**l*·*r* - *sum**r*) + (*sum**l* - *a**l*·*l*)
     72 
     73 For right cyclic shift: Δ'*l*, *r* = (*a**r*·*l* - *sum**l* - 1) + (*sum**r* - 1 - *a**r*·*r*)
     74 
     75 You can see, that if you fix *l* for left shift and *r* for right shift, you can solve this problem with complexity ![](https://espresso.codeforces.com/8649dd3ee97ab9f219ec48ea50f9459c9173db75.png) using [Convex Hull Trick](http://wcipeg.com/wiki/Convex_hull_trick).
     76 
     77 Time: ![](https://espresso.codeforces.com/8649dd3ee97ab9f219ec48ea50f9459c9173db75.png)
     78 
     79 Memory: ![](https://espresso.codeforces.com/92de30bfabf583a2c3a88f74b1d279cf6e3b0abf.png)
     80 
     81 [C++](//www.codeforces.com/contest/631/submission/16501267)