codeforces-scrape

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

245.md (10262B)


      1 Source: https://codeforces.com/blog/entry/5921
      2 
      3 Hello,
      4 
      5 It's my first Blog post and I decided to dedicate it to [CROC-MBTU 2012, Elimination Round](//codeforces.com/contest/245/). I tried to do my best and explain ideas completely. Bear in mind that solutions aren't unique and they're only my ideas. At the end of each explanation, there exists a link to **C++** implementation of problem. I hope this editorial will be useful. Any constructive criticism is appreciated. Please report any bug and/or mistake you encounter here in comments.
      6 
      7 #### [A. System Administrator](//codeforces.com/contest/245/problem/A)
      8 
      9 Let's define following variables:
     10 
     11 *A**Reached* : Number of packets that reached *A*.
     12 
     13 *A**Lost* : Number of packets which didn't reach *A*.
     14 
     15 *B**Reached* : Number of packets that reached *B*.
     16 
     17 *B**Lost* : Number of packets which didn't reach *B*.
     18 
     19 We iterate over input and update each variable accordingly. Now answer for server *A* is `LIVE` if and only if *A**Reached* ≥ *A**Lost* otherwise it's `DEAD`. Also answer for server *B* is `LIVE` if and only if *B**Reached* ≥ *B**Lost* otherwise it's `DEAD`.
     20 
     21 **Implementation**: [C++](//codeforces.com/contest/245/submission/2605304)
     22 
     23 #### [B. Internet Address](//codeforces.com/contest/245/problem/B)
     24 
     25 Problem guarantees that there exists an Internet resource address from which we can obtain our input. At first, let's find **Protocol** of address. It's sufficient to only check first letter of input, if it's *h* then protocol is *http* otherwise, it's *ftp*. Now, let's find position of .*ru*. We can iterate over our string from right to left and greedily choose the first occurrence of .*ru* as [TLD](https://en.wikipedia.org/wiki/Top-level_domain). Now the rest of Internet address can be obtained easily as we have positions of **Protocol** and **TLD**. Just note that we should check whether  < *context* >  is present after .*ru* or not. Also picking .*ru* greedily from left to right fails following testcase, hence it's incorrect.
     26 
     27 Input: `httpruru`
     28 
     29 Incorrect output: `http://.ru/ru`
     30 
     31 Correct output: `http://ru.ru`
     32 
     33 **Implementation**: [C++](//codeforces.com/contest/245/submission/2607393)
     34 
     35 #### [C. Game with Coins](//codeforces.com/contest/245/problem/C)
     36 
     37 First note that if *n* ≤ 2 or ![](https://espresso.codeforces.com/7b4ac172264d37751e053b7d69703bcfd29f9390.png) then answer is  - 1. It's because of the following 2 facts:
     38 
     39 **1**. ![](https://espresso.codeforces.com/bd3e608042b79e1f96ca03451ecf1b129b9407e6.png) and ![](https://espresso.codeforces.com/0e5e0b972a73734f46dcdd6dbd3110ba64581b74.png) so *n* ≥ 3 otherwise *x* won't be a natural number.
     40 
     41 **2**. If ![](https://espresso.codeforces.com/68b4978dad7a8a5241e0b17c5ffe9faa8211d30d.png) then *n* = 2*k* and ![](https://espresso.codeforces.com/079f3d6aac86f113bba5ae2bd4c9caac1055c493.png) which means *x* ≤ *k* - 1 hence 2*x* + 1 ≤ 2*k* - 1 so there doesn't exist a *x* such that it satisfies problem's conditions and can be used to reduce *a*[*n*]
     42 
     43 In other situations, there always exists a sequence which can finish the game. We now propose a greedy algorithm and then prove it's correctness.
     44 
     45 **Algorithm**: Iterate from *n* to 2. Suppose that you're in position *i*. If ![](https://espresso.codeforces.com/1bf3847303aba6a5106883beb349e0e9fba3df4e.png) then take ![](https://espresso.codeforces.com/fa7109c949c827f62be98182adbf5af78fe475da.png) otherwise, take ![](https://espresso.codeforces.com/4c77541482d6834ded359b7ece97d649ff177c01.png) and execute operations with obtained *x* as long as *a*[*i*] > 0 and increase *ans* for each execution. At the end, increase *ans* by *a*[1] and output it. Remember to check if an element you're going to decrease by 1 is positive beforehand.
     46 
     47 **Correctness**: Let's prove correctness of algorithm by induction on *n*. Base case is *n* = 3 in which *ans* = *max*(*a*[1], *a*[2], *a*[3]) and algorithm correctly computes it. Now take *n* ≥ 5 and consider it's of the form 2*k* + 1. To change *a*[*n*] and *a*[*n* - 1] into 0, we need to take *x* = *k* as it's the only possible *x* which affects their values and perform operations exactly *max*(*a*[*n*], *a*[*n* - 1]) number of times. It's both necessary and sufficient in order to change both of them into 0. After that, we can ignore both *a*[*n*] and *a*[*n* - 1] from the list and induction hypothesis ensures that executing algorithm on remaining elements finishes the game in the least number of moves. ![](https://espresso.codeforces.com/4a4e9e431da45a27bc880a8a1ca44d8b1b9bc143.png)
     48 
     49 **Implementation**: [C++](//codeforces.com/contest/245/submission/2605462)
     50 
     51 #### [D. Restoring Table](//codeforces.com/contest/245/problem/D)
     52 
     53 Consider *a*[*i*], *a*[*j*] and *b*[*i*][*j*] = *a*[*i*]&*a*[*j*]. Now consider binary representation of *b*[*i*][*j*]. For each 1-bit of *b*[*i*][*j*] at position *k*, (0-indexed) we conclude that *k*-th bit of *a*[*i*] and *a*[*j*] equals 1 so we set *a*[*i*] = *a*[*i*]|2*k* and *a*[*j*] = *a*[*j*]|2*k*. Now let's describe algorithm. We use *i* to iterate from 1 to *n* and for each *i*, we iterate over all *b*[*i*][*j*] such that *i* ≠ *j* and assign *a*[*i*] = *a*[*i*]|*b*[*i*][*j*]. At the end, we'll have sequence *a* constructed. Now we prove correctness of algorithm.
     54 
     55 **Correctness**: Consider 2 indices *i* and *j* such that *a*[*i*]&*a*[*j*] ≠ *b*[*i*][*j*]. Consider that *k*-th bit of *a*[*i*]&*a*[*j*] differs from *k*-th bit of *b*[*i*][*j*]. If *k*-th bit of their *AND* equals 0, we face contradiction as *k*-th bit of *b*[*i*][*j*] has to be 1 and algorithm ensures that in this situation, *k*-th bit of both numbers will be set as 1. On the other hand, if *k*-th bit of their *AND* equals 1 then we conclude that *k*-th bit of both numbers equals 1 hence when calculating *AND* of them, we get 1 in *k*-th bit which is a contradiction with our preliminary hypothesis. So we proved correctness of algorithm. ![](https://espresso.codeforces.com/4a4e9e431da45a27bc880a8a1ca44d8b1b9bc143.png)
     56 
     57 **Implementation**: [C++](//codeforces.com/contest/245/submission/2607190)
     58 
     59 #### [E. Mishap in Club](//codeforces.com/contest/245/problem/E)
     60 
     61 Consider following interpretation of problem. We're standing in (0, 0) at the center of Cartesian coordinate system. We iterate over the given sequence, for each  + , we move from (*x*, *y*) to (*x* + 1, *y* + 1) and for each  - , we move from (*x*, *y*) to (*x* + 1, *y* - 1). Consider the maximum *y* coordinate we visit during our movement as *MAX* and minimum *y* we visit as *MIN*. It's obvious that we need at least *MAX* - *MIN* people. It can be proved that we can take our moves in such a way that we exactly need *MAX* - *MIN* people. For each  + , if there exists a person out of cafe who had entered cafe once or was in cafe once, we move him in, otherwise, we need a new person. The same argument holds for each  -  we see in sequence.
     62 
     63 **Implementation**: [C++](//codeforces.com/contest/245/submission/2607200)
     64 
     65 #### [F. Log Stream Analysis](//codeforces.com/contest/245/problem/F)
     66 
     67 First note that *"MESSAGE"* is useless and can be ignored. Year is always 2012 so it can be ignored too. Now convert each date and time to seconds past from beginning of 2012. Maintain a list, such as a vector, *V*, for storing seconds. Define pointer *head* to be head of your vector. Define *sec* to be conversion of date and time in seconds for the most recent log. As long as *head* ≤ *Size*[*V*] and *V*[*head*] + *n* ≤ *sec*, increase *head*. After that, push *sec* into *V*. If *Size*[*V*] - *head* ≥ *m* then answer is the current log. If at the end, no time was found, answer will be  - 1.
     68 
     69 **Implementation Note**: You may use *stringstream* in order to ease implementation part. More information can be found [here](http://www.cplusplus.com/reference/iostream/stringstream/) and [here](http://faculty.virginia.edu/comp-phys/phys2660/html/references/www.cppreference.com/cppsstream/all.html).
     70 
     71 **Implementation**: [C++](//codeforces.com/contest/245/submission/2610570)
     72 
     73 #### [G. Suggested Friends](//codeforces.com/contest/245/problem/G)
     74 
     75 Use *map* in order to map people to numbers. Construct the given graph using adjacency list. Now, let's find answer for each vertex *v*. Mark all of *v*'s neighbors. After that iterate over all other vertices, and iterate over their adjacency list and count their mutual neighbors with *v* and update answer for *v*. Complexity is *O*(*m*) for each vertex *v*. Summing up all complexities, we conclude that our algorithm is of *O*(*nm*) and as *n* is of *O*(*m*), we can conclude that overall complexity is *O*(*m*2).
     76 
     77 **Implementation**: [C++](//codeforces.com/contest/245/submission/2610800)
     78 
     79 #### [H. Queries for Number of Palindromes](//codeforces.com/contest/245/problem/H)
     80 
     81 **Note**: Strings and arrays are considered 0-based in the following solution.
     82 
     83 Let *isPal*[*i*][*j*] be 1 if *s*[*i*...*j*] is palindrome, otherwise, set it 0. Let's define *dp*[*i*][*j*] to be number of palindrome substrings of *s*[*i*...*j*]. Let's calculate *isPal*[*i*][*j*] and *dp*[*i*][*j*] in *O*(|*S*|2). First, initialize *isPal*[*i*][*i*] = 1 and *dp*[*i*][*i*] = 1. After that, loop over *len* which states length of substring and for each specific *len*, loop over *start* which states starting position of substring. *isPal*[*start*][*start* + *len* - 1] can be easily calculated by the following formula:
     84 
     85 ```
     86 isPal[start][start+len-1] = isPal[start+1][start+len-2] & (s[start] == s[start+len-1])
     87 ```
     88 
     89 After that, *dp*[*start*][*start* + *len* - 1] can be calculated by the following formula which is derived from [Inc-Exc Principle](https://en.wikipedia.org/wiki/Inclusion-exclusion_principle).
     90 
     91 ```
     92 dp[start][start+len-1] = dp[start][start+len-2] + dp[start+1][start+len-1] - dp[start+1][start+len-2] + isPal[start][start+len-1]
     93 ```
     94 
     95 After preprocessing, we get queries *l**i* and *r**i* and output *dp*[*l**i* - 1][*r**i* - 1]. Overall complexity is *O*(|*S*|2).
     96 
     97 **Implementation**: [C++](//codeforces.com/contest/245/submission/2622404)