When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

SummerSky's blog

By SummerSky, 7 years ago, In English

A. 123-sequence

Suppose that the number of integers 1, 2 and 3 are denoted as x[1], x[2] and x[3]. To obtain the minimum number of replacements, we should find out the minimum value among x[1]+x[2], x[1]+x[3] and x[2]+x[3], and output it as the answer. One could also find out the maximum value of x[3], x[2] and x[1], and then use x[1]+x[2]+x[3]-x[i] as the answer.

B. Right Triangles

We count the number of right triangles based on the intersection from which two sides that form a 90 degree extend. We use R[r] to denote the number of '*' in the r-th row, and C[c] to denote the number of '*' in the c-th column. Then, if we select any '*' as the point where two sides that form a 90 degree intersect with each other, the number of different right triangles is just (R[r]-1)*(C[c]-1). The reason is that the first side can be selected from all the (R[r]-1) points at the current row, except for the intersection. Similarly, the second side can be selected from all the (C[c]-1) points. Therefore, we can enumerate all the '*' points, and add the corresponding (R[r]-1)*(C[c]-1) together, which is the final answer.

C. Circular RMQ

I find out that this is a famoue RMQ problem, where range minimum query is asked, with range modification, i.e., increase all the elements belonging to some range by the same constant number.

I searched on the internet, however only found out some materials that did not provide quite many details talking about how to solve such a problem (Most of them just show the codes but without many arguments or principles...). May any coders recommend me some articles talking about this :D 52C - Circular RMQ

  • Vote: I like it
  • +3
  • Vote: I do not like it