### Loserinlife's blog

By Loserinlife, history, 2 weeks ago, By Loserinlife, history, 4 weeks ago, Given an isosceles right triangle with vertices (0, 0) (0, d) (d, 0). And N rectangles (x1, y1, x2, y2).

Count number of points (x, y) that is both inside the triangle and at least 1 of the rectangles.

N <= 2e5

d, x1, x2, y1, y2 <= 1e9

x1 <= x2, y1 <= y2

Thanks!

By Loserinlife, history, 5 weeks ago, Given a n * m matrix of 0s and 1s. For each square,find the sum of Manhattan distances from that square to the first kth nearest 1s.

(Distance to closest 1 + distance to second closest 1 + ...)

n, m <= 2000

k <= n * m

There are at least k ones in the matrix. Thanks!

By Loserinlife, history, 2 months ago, Given a weighted undirected graph with N nodes and M edges (u, v, w) meaning node u and v is connected with weight w. Additionally, each node has a value a[i], and you can go from node i to node j with the cost of (a[i] + a[j]) % k, where k is a given constant. Find the shortest path from s to t

Constraints: N, M <= 2e5

a[i] < k <= 1e9

1 <= u, v, s, t <= n

w <= 1e9

Thanks

By Loserinlife, history, 5 months ago, Given an array of n integers and q queries. Each query consists of 4 integers (x, y, u, v) (1 <= x <= y <= n, 1 <= u <= v <= n)

Find the sum of abs(a[i] — a[j]) for all pairs (i, j) where x <= i <= y, for all u <= j <= v

N, Q <= 1e5

Ai <= 1e9

Thanks!

By Loserinlife, history, 6 months ago, Define the distance between two points i, j max(|xi, xj|, |yi — yj|). Given n points (xi, yi). Find a point (X, Y) so that the sum of distances from this point to n points is minimized.

N <= 1e5

xi, yi <= 1e9

By Loserinlife, history, 6 months ago, Calculate A^B mod C

A <= 10^100000

B <= 10^100000

C <= 10^9 (Doesn't have to be a prime number)

Thanks :)).

By Loserinlife, history, 6 months ago, Count the most common occurrence of subarray sum.

Constraints:

N <= 1e6; abs(ai) <= 1e6

Ex:

Inp:

5

1 1 2 1 4

Out:

3 (there are 3 subarray with the sum of 4: (1, 1, 2), (1, 2, 1), (4)

This question appears in ones of my friends competition and I have no idea how to solve it. Can someone help? Thanks.

By Loserinlife, history, 6 months ago, Given a weighted directed graph. Consider a vertice u connected to v1, v2, v3, ... with weight w1, w2, w3,.. You may permute the weight in any way you like. Ex: Edges from u are initially (u, v1, w1), (u, v2, w2), (u, v3, w3).. You can change it to (u, v1, w3), (u, v2, w1), (u, v3, w2). The weight must be permuted before the journey and remain that way through out the journey. Find the largest possible shortest path from 1 to n. Constraints: n <= 1e5, m <= 3e5 u , v <= n w <= 1e6 It sounds really cool but I have no idea how to solve it. Can someone help? Thanks :))

By Loserinlife, history, 6 months ago, Choose k elements from an array so that their GCD is maximise.

Constraints: N <= 3000 K <= N; K <= 100 Ai <= 10^10 (ten to the power of 10) I tried an algorithm of enumerating all divisors of ai and find the largest divisors that exists in >= k elements but it TLE. Can somebody help? Thanks in advance.