I am currently preparing for the ICPC, and I have noticed that many teams follow a topic-distribution strategy during their training. I am considering adopting a similar approach with my team.

However, I am unsure about one particular aspect: is it actually beneficial for only one team member to specialize deeply in a specific area?

For example, suppose only one member focuses on advanced geometry for ICPC-level problems while the others do not study it at all. Is this kind of specialization effective, or could it create weaknesses during the contest?

I would appreciate insights or experiences regarding whether strict topic specialization within a team is a good idea.

Help with "Long and Random" Problem

(https://vjudge.net/problem/QOJ-15112)

Problem Statement

Long and Random

Input file: standard input Output file: standard output Time limit: 6 seconds Memory limit: 1024 mebibytes

There is an array a of length n consisting of independent uniformly random integers a_i (1 ≤ a_i ≤ 10^9). Also, there is an array b of length n consisting of independent uniformly random integers b_i (0 ≤ b_i ≤ 1). Laura wants to erase some (possibly zero) elements from array a, then take the prefix of array b with the matching length, and maximize the resulting dot product of the arrays (i.e. sum of a_i * b_i for i from 1 to m). Help her to do that.

Input

In the first line, there is one integer n (1 ≤ n ≤ 4 * 10^5) — the length of the arrays a and b.

In the second line, there are n integers a_1, ..., a_n (1 ≤ a_i ≤ 10^9) — the elements of the array a.

In the third line, there are n integers b_1, ..., b_n (0 ≤ b_i ≤ 1) — the elements of the array b.

It is guaranteed that in all tests, except for the first one (from the examples), all numbers a_i and b_i are generated independently from a uniform distribution over the corresponding ranges.

It is guaranteed that there are no more than 20 tests in total.

Output

Print one number — the maximum possible dot product after erasing some elements from array a.

Examples

Example 1:

Input => 8 1 4 6 5 1 2 3 6 1 0 1 0 1 0 0 1

Output => 15

Example 2:

Input => 4 843693973 430360361 788359887 531088030 1 1 1 0

Output => 2163141890

Note

In the first example, we can erase the first, fifth and sixth elements from a. The result will be equal to the dot product of the arrays [4, 6, 5, 3, 6] and [1, 0, 1, 0, 1] which equals 4*1 + 6*0 + 5*1 + 3*0 + 6*1 = 15.

Question

I've been trying to solve this problem but I'm stuck on the approach. Can anyone help me understand the solution or provide an editorial?

Which one is better in case of Problem solving using Problem set of Codeforces? Solving by the most solved first or the recent ones first?

I am having some difficulty in solving the following problem :

https://mirror.codeforces.com/gym/105789/problem/D

I tried reading the editorial and understood the MST part of it. But I cant understand the next Virtual Node/ LCA part. I thought the problem is quite interesting and important, thats why hoping would get some help from here.

There are $$$N$$$ glasses placed in a row (numbered from $$$1$$$ to $$$N$$$). The $$$i$$$-th glass has:

• a total volume of $$$V_i$$$ liters,
• currently contains $$$W_i$$$ liters of water.

A glass is called good if

and bad otherwise.

Bending Operation

You may perform up to $$$K$$$ non‑intersecting merge operations. In each operation you select a contiguous segment of glasses $$$[l, r]$$$ (with $$$1 \le l \lt r \le N$$$) and merge them into one new glass whose:

• volume is

• water amount is

Segments $$$[l_1,r_1]$$$ and $$$[l_2,r_2]$$$ are non‑intersecting if

Goal

Determine whether it is possible—by choosing some $$$K$$$ non‑intersecting segments (where $$$0 \le K \le N$$$) and merging each—to end up with strictly more good glasses than bad glasses.

• If yes, print:

Yes K l_1 r_1 l_2 r_2 ⋮ l_K r_K

where each $$$[l_i, r_i]$$$ is a chosen segment. * Otherwise, print:

No

Input

• The first line contains a single integer $$$T$$$ ($$$1 \le T \le 100$$$) — the number of test cases.
• Each test case consists of:

1. An integer $$$N$$$ $$$\bigl(1 \le N \le 10^5\bigr)$$$ — the number of glasses.
2. A line of $$$N$$$ integers $$$V_1, V_2, \ldots, V_N$$$ $$$\bigl(1 \le V_i \le 10^9\bigr)$$$ — the volume of each glass.
3. A line of $$$N$$$ integers $$$W_1, W_2, \ldots, W_N$$$ $$$\bigl(0 \le W_i \le V_i \le 10^9\bigr)$$$ — the current water in each glass.

It is guaranteed that $$$\sum N \le 2\times10^5$$$ over all test cases.

Output

For each test case:

• If no sequence of merges yields strictly more good glasses than bad, print No.
• Otherwise, print Yes, the integer $$$K$$$, and then $$$K$$$ lines each containing two integers $$$l_i$$$ and $$$r_i$$$ $$$(1 \le l_i \lt r_i \le N)$$$, representing your chosen non‑intersecting segments.

You may output any valid solution.

Example

Input
2
4
6 4 8 10
4 1 6 1
3
4 4 5
1 2 3

Output
Yes
1
2 3
No

My Solution :

https://ideone.com/S8gKLm

The basic idea was :

1) to merge the consecutive negatives and gain something like + — + — ....

2) if #positives == #negatives, we try to merge a + — pair with sum > 0

3) if #negatives — #positives == 1, we try to merge the first + — pair and last + — pair with sum > 0.

I cant understand why this solution doesnt work. And it would be really helpful if someone points out a solution/editorial to this problem as well.