Loserinlife's blog

By Loserinlife, history, 2 weeks ago, In English

Hi can I ask about the approach to this problem? Thanks!

Link: https://dmoj.ca/problem/scp4

Full text and comments »

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

By Loserinlife, history, 4 weeks ago, In English

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!

Full text and comments »

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

By Loserinlife, history, 5 weeks ago, In English

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!

Full text and comments »

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

By Loserinlife, history, 2 months ago, In English

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

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By Loserinlife, history, 5 months ago, In English

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!

Full text and comments »

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

By Loserinlife, history, 6 months ago, In English

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

Thanks in advance.

Full text and comments »

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

By Loserinlife, history, 6 months ago, In English

Calculate A^B mod C

A <= 10^100000

B <= 10^100000

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

Thanks :)).

Full text and comments »

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

By Loserinlife, history, 6 months ago, In English

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.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By Loserinlife, history, 6 months ago, In English

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 :))

Full text and comments »

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

By Loserinlife, history, 6 months ago, In English

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.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it