Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### danhnguyen0902's blog

By danhnguyen0902, 6 years ago, ,

Given a sequence A of N pairwise-distinct integers. There are Q queries L R K, asking for the k-th element in the increasing-sorted subsequence A[L], A[L+1], ...., A[R-1], A[R]. The original sequence never changes.

• 1 ≤ N, Q ≤ 10^5

• |Ai| ≤ 10^9, 1 ≤ i ≤ N

• 1 ≤ L ≤ R ≤ N

• 1 ≤ K ≤ R-L+1

Example:

Input:

7 (N)

2 1 5 4 3 6 8 (sequence A)

4 (Q)

1 2 2 (L R K)

3 7 4

4 6 2

5 5 1

Output:

2

6

4

3

• -2

By danhnguyen0902, 6 years ago, ,

Could somebody please tell me how to use Heavy Light Decomposition (I'm also fascinated with any other way) to solve these two problems:

Thank you so much in advance!

• 0

By danhnguyen0902, 7 years ago, ,

I don't know what kind of technique required for this problem. Could anyone please point it out? Thank you so much in advance!

There are several rooms in a company. In each room, there are some employers and some employees, and there is no one who's both an employer and an employee.

One person can be in many rooms, but two people cannot be in the same two rooms. -----> Edit: One person can only be in one room.

In a room, every employer gives work to their employees, but the employers do not give work to each other. The efficiency of a room is determined by the "relationship" in that room.

Example: If there are 2 employers and 3 employees in a room, that room's efficiency will be 6 (= 2 * 3).

The company's efficiency is the total efficiency of all rooms.

Write a program to organize the company such that these conditions are met:

1. The company has at least 1 room.

2. The company's efficiency is exactly E.

3. The number of people in the company (let's say N) is minimum.

4. If there are more than 1 solution to get all the first 3 conditions satisfied, find the solution that has the minimum number of employers (let's say S).

5. If there are more than 1 solution to get all the first 4 conditions satisfied, find the solution that has the minimum number of rooms (let's say K).

Example:

Input:

7 (E)

Output:

7 3 2 (N S K)

Explanation:

There are 3 employers (A1, A2, A3) and 4 employees (B1, B2, B3, B4). They can be put into 2 rooms:

• A1 A2 B1 B2 B3 (Efficiency = 2 * 3 = 6)

• A3 B4 (Efficiency = 1 * 1 = 1)

The total efficiency is 6 + 1 = 7.

Constraints:

• 1 <= E <= 10,000

• -18

By danhnguyen0902, 7 years ago, ,

I've heard that the following problem belongs to a Russian programming contest. Does anyone know where it is or how to solve it?

An arithmetic sequence is a sequence of numbers a[1], a[2],... a[N] such that a[i + 1] — a[i] is equal for all 0 ≤ i < N. Given a sequence of N positive integers and M queries [x, y], write a program answer each query whether the consecutive numbers from position x to y form an arithmetic sequence (they could not originally be in increasing order).

Example:

Input:

5 3 (N M)

1 3 2 5 4 (N positive integers)

1 5 (x y)

2 4 (x y)

4 5 (x y)

Output:

YES

NO

YES


Explain:

• The sequence 1 3 2 5 4 forms an arithmetic sequence, which is 1 2 3 4 5.

• The sequence 3 2 5 does not form an arithmetic sequence.

• The sequence 5 4 also forms an arithmetic sequence, which is 4 5.

Constraints:

• 40% test: N, M <= 1,000 .

• 30% test: N <= 1,000 and M <= 10^6 .

• 30% test: N <= 10^5 and M <= 10^5.

• a[i] <= 10^9

• +6

By danhnguyen0902, 7 years ago, ,

Could anyone please tell me how we can perform the Lazy Propagation technique on the 2D Segment Tree? Suppose we're solving this problem: http://www.spoj.com/problems/MATSUM/ with an additional operation:

"SET x1 y1 x2 y2 num" — Find the rectangle from (x1, y1) to (x2, y2) and set all of its cells' values to num.

I think it would be timeout if we don't use the Lazy Propagation technique here.

Thank you so much in advance!

• 0

By danhnguyen0902, 7 years ago, ,

Is there anyone who's gonna translate this book into English? The book contains so many interesting and basic understanding algorithms as well as data structures in Competitive Programming area. That would be very great if it could come out to worldwide readers.

• +17

By danhnguyen0902, 7 years ago, ,

Hi everyone,

This is one of the problems used in our National Olympiad in Informatics, and it has remained unsolved since 2005. Your help would be really appreciated! So here it is:

Given a sequence of N elements a[1], a[2], ..., a[N] and a positive number K. A partition is defined to include several consecutive elements in the original sequence. Write a program that splits the given sequence into k partitions such that the maximum sum among those partitions is minimized. Write out the desired sum.

Constraints:

• 1 ≤ k ≤ n ≤ 15000

• |ai| ≤ 30000

Example:

Input

9 4 (N and K)

1 1 1 3 2 2 1 3 1 (a[1], a[2], ..., a[N]

Output

5

Explain:

We can divide the original sequence into 4 partitions:

(1, 1, 1)

(3, 2)

(2, 1)

(3, 1)

The maximum sum among the partitions above is 5 (= 3 + 2), and it is the best minimum sum we can achieve while splitting the sequence into 4 partitions.

• +4

By danhnguyen0902, 7 years ago, ,

• +3

By danhnguyen0902, 7 years ago, ,

Does anyone know how to solve this problem?

http://www.spoj.com/problems/LQDNUMS/

Or at least please give me the references for it. Thanks a lot in advance.

• 0

By danhnguyen0902, 7 years ago, ,

Let function S(X) equal sum of X's digits.

For ex: S(357) = 3 + 5 + 7 = 15

Given M and N (0 < M, N <= 10^12). Find the minimum number K such that:

• a1 + a2 + ... + aK = N

• S(a1) + S(a2) + ... + S(aK) = M

(a1, a2, ..., aK are arbitrary integers <= N)

Example:

Input (M and N)

1 100

Output (K, if K doesn't exist, print -1)

1

Does anyone have any idea for this problem?

• +3

By danhnguyen0902, 7 years ago, ,

Hi everyone,

I'm struggling with this problem, and I don't have any idea to do it yet. Does anyone know how to solve it?

A positive integer is called a lucky number when the sum of some of its digits equals the sum of its remaining digits. 561743, for example, is a lucky number because 5 + 1 + 4 + 3 = 6 + 7. However, we are about to count the number of unlucky numbers with the length of N and their digits are in the range [0, K], and they could start with a bunch of '0'.

Input: N K Output: The number of unlucky numbers

Example 1:

Input

1 5

Output

5

Example 2:

Input

4 3

Output

164