The tutorials for problems B & E were written by 1am, D by The-Legend, F by Qumair, J & K by Motarack and M by abo_od303. Thank you guys for also reviewing the rest of the tutorial!

#### A. Careful Thief

It’s enough to try all segments of size *K* that either starts with the start of a range or ends with the end of a range, suppose that the optimal solution is somewhere that starts in some range and ends in some other range (possibly ranges of zeroes), then shifting the segment to one direction will increase the answer, and shifting it in the other direction will decrease it until you reach the boundary of the range, or if both ranges have the same amount of money then shifting will not affect the answer. This can be done using a sorted array of the ranges and for each range that starts with *l*_{i} we can binary search for *l*_{i} + *k* - 1 and to get the result of all the ranges in between we can do a prefix summation for (*r*_{i} - *l*_{i} + 1) × *v*_{i}. Same process can be done for trying the ends of all ranges.

**Complexity per test-case:** .

**Solution**

#### B. Friends and Cookies

This problem simply requires implementation with basic modulus and division calculations. Please observe the following image:

^{st}friend, till the

*n*

^{th}. We can simply loop this, since

*n*is maximum 1000. Or add 1 to all friends if

*x*≥

*n*. After that, it's just careful calculations. Decrease

*n*from

*x*, and divide what is left by

*n*- 1. This is because in the iterations after the first one, Abood will give cookies to the first

*n*- 1 friends, then to the last

*n*- 1 friends. So by dividing, I can figure out how much each friend will eat without having to loop

*x*times. The only thing left to deal with is , the remainder cookies. Depending on whether is even or not, I can figure out the direction of the last iteration, and where I start giving (either start

*n*- 1 and move to the left, or start at 2 and move to the right). Using that, I loop accordingly only the remainder until I have no more cookies left. It is possible to loop because we know the remainder will be less than

*n*- 1. I’m too lazy to discuss exact calculations, if anything is unclear please feel free to write in the comments. Oh and don't forget to clear the array between iterations, and be careful of division by zero when

*n*= 1.

**Complexity per test-case:**

*O*(

*N*).

**Solution**

#### C. Flip the Bits

The maximal number *m* which is less than *n* is *n* - 1, so the number of flipped bits will be exactly the number of different bits between *n* and *n* - 1 which is equal to the number of 1 bits in *n* XOR (*n* - 1).

**Complexity per test-case:** .

**Solution**

#### D. Magic Sticks

Let us use these terminologies:

- Each line belong to 1 × 1 cell we will call it
edge- Each line parallel to one of the biggest rectangle's sides
n×mand equal to its length we will call itline.

Our solution depends on these two observations about the selected *edges*:

- They should be parallel to each others.
- They should be parallel to the shorter line in the biggest rectangle
n×m.

Assume *n* ≤ *m* (you can otherwise swap the numbers to satisfy that) And the shorter side *n* is vertical.

We have *m* + 1 vertical *lines* with length *n* from each one of them if we take an *edge* then we have to not take the one below or above But how do we select the *edges*?

We should select them alternatively, why? Let us not take two consecutive *edges* then there are two cells that are not covered by at least one *edge* till now so in the next *line* we must take two consecutive *edges* to get these two cells covered by at least one *edge* which will violate the problem's constraints (edges should not touch).

Now let us continue with taking the alternative *edges*. One of the *lines* we will take *edges* among *n*, the next one and so on..

You have to notice that we have to start with taking from the first line not since we need to take as much as we can in comparing with to minimize the number of *edges* in the required group.

Here's an example for a 5 × 6 grid:

**Complexity per test-case:**

*O*(1).

**Solution**

#### E. N-Dimensional Grid

There are many different solutions for this problem that can pass, let's discuss the one where you calculate all pairs and subtract the incorrect ones. For every cell, we need to know how many cells have a manhattan distance of 1 with it. It is clear that these pairs will have the same values for *n* - 1 dimensions, with only one dimension having a different value by an absolute difference of 1.

So for every cell, keep fixed *n* - 1 dimensions, and decrease the value for one dimension by 1 will give us one non repeated pair. For each cell, there are *n* ways to do this. Since number of cells is the product of the sizes of all dimensions in the input, we multiply this product by *n* to get the number of pairs.

Notice that not all these pairs are valid, because we are considering pairs that get matched with a cell with a 0 as one of its values. All we must do now is decrease these invalid pairs. Fix one dimension with a value as 0. The number of valid cells that will be wrongly matched with this invalid one is the product of all dimensions sizes *a* _{ i} except for the one that's currently fixed. Therefore for each fixed *i*, decrease the product of all dimension sizes except for *a* _{ i} from our number of pairs. This is our final answer.

**Complexity per test-case:** *O*(*N*).

**Solution**

#### F. Minimum Sum of Array

Let’s define a frequency array for the original array and a visited array for the values, now for every number *x* from 1 to 10^{6} with frequency more than zero (it exists in the array) then loop over the multiples of *x*, if a multiple of *x* say *y* is not visited before then we should change *y* into *x* as *x* is the smallest divisor for *y* in the array.

**Complexity per test-case:** .

**Solution**

#### G. Power of String

Notice that the position of the characters doesn't matter because, for example, if you have character *ch* repeated *F*_{ch} times then no matter what their positions are in the string they will add the same value which is equal to , So we are only interested in *F*_{ch}.

Suppose that we have determined what characters we will change, then all of them should be changed to the same character *ch*_{1}, and any other equal characters *ch* should all be changed into *ch*_{1} or none, except for one character *ch*_{2} that we can change part of it, check the proof below.

Now if we will fix *ch*_{1} and *ch*_{2}, we can calculate knapsack-like DP on all other characters (we know that we will change either all or none of all equal characters).

**Complexity per test-case:** *O*(*K* × *A*^{3}) (*O*(*A*^{2}) for iterating over (*ch*_{1}, *ch*_{2}), and *O*(*K* × *A*) for knapsack) where *A* is equal to the number of different characters in the string which is 26.

**Proof**

**Solution**

#### H. Making Friends

Find the maximum value for *a*_{i} + *a*_{2 × n - i - 1} for all *i* < 2 × *n* - *i* - 1.

**Complexity per test-case:** *O*(*N*).

**Solution**

#### I. Split the Number

The minimum difference is either 0 or 1, splitting *x* equally over the *n* parts giving each part , now we have as left-over which is less than *n*, we can split them over the last parts. note that if equals 0 then there is no strictly positive solution so print - 1.

**Complexity per test-case:** *O*(*N*).

**Solution**

#### J. T-Shirts Dilemma

Let *a* _{ i}, *b* _{ i} and *v*_{i} be the *i*th bit of *a*, *b* and *v* correspondingly, and let's iterate from the most significant bit to the least significant bit, and each time check the following:

- If
*v*_{i}= 1 and*a*_{i}=*b*_{i}= 0 then we can take the segment segment [*a*,*b*] as their cost will be less than*v*. - If
*v*_{i}= 0 and*a*_{i}=*b*_{i}= 1 then we can't take any number as the cost of every number is greater than*v*. - If
*v*_{i}=*a*_{i}=*b*_{i}= 0 we don't have enough information so we go to the next bit. - If
*v*_{i}=*a*_{i}=*b*_{i}= 1 we don't have enough information here either, so we set*a*_{ i},*b*_{ i}and*v*_{i}to 0 and go to the next bit (note that flipping the bits won't affect the answer because the*OR*of any set of numbers before and after the flipping will remain the same expect for the flipped bit, but that bit is the same for*v*and all numbers in [*a*,*b*], so it doesn't matter). - If
*v*_{i}=*a*_{i}= 0 and*b*_{i}= 1 then we can't include any number with it's*i*th bit 1, let*c*= number with all bits after*i*th bit 1, and rest of bits 0, then the answer for (*a*,*b*,*v*) equals answer for (*a*,*c*,*v*), so we replace*b*with*c*and go to the next bit. - If
*v*_{i}= 1,*a*_{i}= 0 and*b*_{i}= 1, if all the bits to the right of the*i*th bit in*v*are 1s then we can take the segment [*a*,*b*] as our answer, else let*c*= number with all bits after*i*th bit 1, and rest of bits 0, then we can either take the segment [*a*,*c*] as an answer or take the answer of the problem (*c*+ 1,*b*,*v*) with setting the*i*th bit for all the numbers to 0 (note that we don't benefit by taking the answer of the problem (*c*,*b*,*v*) because*c*OR (*c*+ 1) is already larger than*v*), we take the max of those two as our answer.

Cases where *a*_{i} = 1 and *b*_{i} = 0 are impossible because all the bits to the left of the *i*th bit are always 0 and *b* ≥ *a*. See the code below for better understanding of how the algorithm works.

**Complexity per test-case:** .

**Solution**

#### K. League of Demacia

Let's say that θ is the angle in which Lux will rotate clockwise, and an optimal θ is an angle which will kill the maximum number of soldiers, notice that there could be an infinite amount of optimal θs, but at least one of them will have a soldier intersecting with either the left border of the laser or the left half of the laser's base (the line intersecting with the point (0,0) and having length *z*), note that this is true because if we take any optimal θ we can keep increasing θ until such soldier appears.

Now let's for each soldier figure out if he can be the chosen one, this can be done by calculating the corresponding θ and counting the number of dead soldiers for such a θ.

let *d* be the distance of the soldier to the point (0, 0), if the soldier will intersect with the base, otherwise he will intersect with the left border (imaging a circle at (0, 0) with radius ).

Let be vector that resembles the left side of the base and be a vector from (0, 0) to our soldier, if then (in terms of direction), else we can get by rotating by θ _{2} counter clockwise, .

**Complexity per test-case:**

*O*(

*N*

^{2}).

**Solution**

#### L. Lazy Teacher

The problem can be solved using Dynamic Programming, the *DP* state is *dp*[*i*][*j*][*p*1][*p*2][*p*3][*p*4][*p*5] which *i* and *j* means at the *i* ^{ th} row and *j*^{th} column and the colors of the last 5 cells are *p*_{i} where *p* _{1} is the earliest one and *p*_{5} is the latest one, that is because only the last 5 cells colored will affect the result if we move column by column making sure no two adjacent cells have the same color.

Now *p*_{i} values can reach 10^{5} each, but some different coloring patterns have the same result, for example if you have the colors 5, 9, 5, 2, 1 for *p*_{1}, *p*_{2}, *p*_{3}, *p*_{4}, *p*_{5} the answer for *dp*[*i*][*j*][*p*1][*p*2][*p*3][*p*4][*p*5] will be the same for the colors 0, 1, 0, 2, 3 which means mapping the colors to smaller numbers in a smart way will make: *p*_{1} < 1, *p*_{2} < 2, *p*_{3} < 3, *p*_{4} < 4, *p*_{5} < 5 while giving the same result, this way we only need to try colors from 0 to 4, and the rest from 5 to *k* will give the same answer as they will have the same mapping so in the DP we only need to iterate over *min*(*k*, *n* + 1) colors.

**Complexity per test-case:** *O*(*N*^{2} × *M* × *N*!), the extra *N* is from the loop inside the DP.

**Solution**

#### M.Greedy Pirate

It's obvious that we need to traverse the maximum number of edges. Let's denote *u* as the starting node and *v* as the finishing node, the only edges that we can not traverse are the edges on the path directed from *v* to *u*, so we need to calculate the sum of coins on this path and then subtract it from the total number of coins on all edges. Calculating the sum of coins on a path can be done easily by finding the lowest common ancestor(LCA) of node *u* and node *v*, the answer will be: *cost*_{1}(*u*) - *cost*_{1}(*lca*) + *cost*_{2}(*v*) - *cost*_{2}(*lca*) where *cost*_{1}(*x*) is the cost of the directed path from the root to *x* and *cost*_{2}(*x*) is the cost of the directed path from *x* to the root which can be pre-calculated with a DFS.

**Complexity per test-case:** .

**Solution**

I am sorry but I do not understand why the complexity of the last problem (M) is

N^{2}per test case. It seems to me it's onlyNlog(N). May you please explain?Thank you.

It is actually , welcome to the copy paste world! Just edited it, Thanks!

Can i know what is the second case in problem B :( I wrote a math equation to solve this problem ,but it seems that something wrong. Can I get any help?

Here my code https://ideone.com/V5Sxh6 Thanks a lot.

Your solution is correct, but the problem is in using double numbers, and that might give you inconsistent results, try to write your own ceil function which doesn't deal with float numbers.

I've just updated your solution code`

Could you please explain more why it is a problem ? btw, in the updated code i try to understand how (x-i+1 + 2*n-3) / (2*n — 2) is equivalent to ceil((x-i+1)/(2.0*(n-1))) ,but for sorry i could not.

i will be happier with more explanation

Again, thanks!

The problem is caused by the limited storage for floating point numbers (double numbers).

For example is equal to 0.3333333333333..., after a digit the number will be cut and some round will occur then.

So for example if you want to divide 4.0 by 2.0 you might end up with 2.0000000001 (just an example) and then after you take a ceiling to this number you will get 3.

I advise you to read more about precision errors in floating point numbers for complete understanding about the problem.

Now the ceil function to this fraction is equal to :

please note that we are talking about ceil when dividing two positive numbers.

Now there is another way to write the ceil function How is that true ? Let us assume there is a remainder

x≥ 1 when dividing a by b then if we add b-1 to x this will increase the integer division result by 1 (the first part above) sinceb- 1 +x≥bsincex≥ 1, the other case when there is no remainder when divide a by b then adding b-1 to the numerator has no affect in the result (the second part above)So I just added the denominator - 1 to the numerator at your solution.

wonderful! Thanks for the useful reply.

No, you can't :3 it's very confidential

I wonder if there are any hacks with dynamic segment trees in the solution of problem A. I have tried a hybrid solution, which embraces the approach in the editorial by shifting range boundaries without trying all possibilities. However, the code exceeds the memory limit in Test 3 in this case, because vanilla dynamic segment tree stores all leafs in the supplied non-overlapping segments.

Is it possible to remove deprecated nodes of segment trees on-the-fly in an effective way? By assuming a strict increasing order in queries, deprecation of nodes are assured.

I really like the solution code for E. I calculated inverse for all 1e5 values, which took 1528ms. The solution code doesn't even use inverse.

,