sudo_Vendetta's blog

By sudo_Vendetta, 16 months ago, In English,

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 li we can binary search for li + k - 1 and to get the result of all the ranges in between we can do a prefix summation for (ri - li + 1) × vi. 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:

The first iteration, Abood will start to give his friends cookies starting from the 1st friend, till the nth. 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 × m and equal to its length we will call it line.

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 ai except for the one that's currently fixed. Therefore for each fixed i, decrease the product of all dimension sizes except for ai 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 106 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 Fch 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 Fch.
Suppose that we have determined what characters we will change, then all of them should be changed to the same character ch1, and any other equal characters ch should all be changed into ch1 or none, except for one character ch2 that we can change part of it, check the proof below.
Now if we will fix ch1 and ch2, 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 × A3) (O(A2) for iterating over (ch1, ch2), 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 ai + a2 × 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 ai, bi and vi be the ith 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 vi = 1 and ai = bi = 0 then we can take the segment segment [a, b] as their cost will be less than v.
  • If vi = 0 and ai = bi = 1 then we can't take any number as the cost of every number is greater than v.
  • If vi = ai = bi = 0 we don't have enough information so we go to the next bit.
  • If vi = ai = bi = 1 we don't have enough information here either, so we set ai, bi and vi 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 vi = ai = 0 and bi = 1 then we can't include any number with it's ith bit 1, let c = number with all bits after ith 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 vi = 1, ai = 0 and bi = 1, if all the bits to the right of the ith bit in v are 1s then we can take the segment [a, b] as our answer, else let c = number with all bits after ith 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 ith 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 ai = 1 and bi = 0 are impossible because all the bits to the left of the ith 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, .

A soldier is dead if he's to the right of (can be checked using cross product) and he's inside the laser beam (| after normalizing , if it's not clear read more about the dot product as this is a classical usage of it).
Complexity per test-case: O(N2).
Solution

L. Lazy Teacher

The problem can be solved using Dynamic Programming, the DP state is dp[i][j][p1][p2][p3][p4][p5] which i and j means at the ith row and jth column and the colors of the last 5 cells are pi where p1 is the earliest one and p5 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 pi values can reach 105 each, but some different coloring patterns have the same result, for example if you have the colors 5, 9, 5, 2, 1 for p1, p2, p3, p4, p5 the answer for dp[i][j][p1][p2][p3][p4][p5] 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: p1 < 1, p2 < 2, p3 < 3, p4 < 4, p5 < 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(N2 × 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: cost1(u) - cost1(lca) + cost2(v) - cost2(lca) where cost1(x) is the cost of the directed path from the root to x and cost2(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
 
 
 
 
  • Vote: I like it
  • +66
  • Vote: I do not like it

»
16 months ago, # |
  Vote: I like it +18 Vote: I do not like it

I am sorry but I do not understand why the complexity of the last problem (M) is N2 per test case. It seems to me it's only Nlog(N). May you please explain?

Thank you.

  • »
    »
    16 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

»
16 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

  • »
    »
    16 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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`

    • »
      »
      »
      16 months ago, # ^ |
      Rev. 6   Vote: I like it +5 Vote: I do not like it

      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!

      • »
        »
        »
        »
        15 months ago, # ^ |
        Rev. 3   Vote: I like it +8 Vote: I do not like it

        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 :

        • if , i.e .
        • (integer division) if

        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) since b - 1 + x ≥ b since x ≥ 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.

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
4 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

,