A function F(l, r) is defined as follow:

F(l, r) = 0 if l > r

else m is the index of the largest element from l to r.

F(l, r) = r — l + 1 + F(l, m — 1) + F(m + 1, r)

Given a permutation of length N and Q queries (l, r), calculate F(l, r) for each queries.

N <= 1e6, Q <= 1e6

Thanks!

Given n block numbered from 1 to n, you start at block 1 and want to reach block n. From block[i] you can move to block i + 1

or block i + 2. Each block has a colour c[i] associated with it. There are m colour, each colour has cost w[i]. At the start,

you decided to purchase a subset S of colour, the cost of which is the total w[i] of all i chosen. Find the minimum cost of such

subset S that you are able to go from 1 to n stepping on only blocks with a chosen color. (c[i] is in S)

Input:

8 8

6 4 1 5 2 8 4 2

19 15 13 10 3 9 13 13

Output: 37 (S is {2, 6, 4, 5})

Thanks!

N <= 3e5, M <= 40

Given the string s. Find a maximum integer k such that there is a non-empty substring in the string s that is a concatenation of

k equal strings. This problem is from: https://mirror.codeforces.com/edu/course/2/lesson/2/5/practice/contest/269656/problem/F

|s| <= 4e5

Thanks!

Given a graph with n nodes, each with the value ai, and m edges in the form of (ui, vi, wi).

While still possible, print the smallest index i of an edge so that ui and vi are in different connected components, and the sum of ai in the two components >= w[i].

Then connect ui and vi

N, M <= 300000

ui, vi <= N

a[i], w <= 1e9.

Thanks!

Given n objects the ith of each cost ai.

Given q queries in the form of s,a, b.

Count the number of subsets that contains a and b but sum of cost does not exceed s.

K is the sum of all Ai

N,Q,K<=4000

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

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

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!

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!

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

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!

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.

Calculate A^B mod C

A <= 10^100000

B <= 10^100000

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

Thanks :)).

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.

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

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.