The problem is to process Q queries of the form X on N pairs of integers a[i] and b[i] (N, Q <= 2e5 and a[i], b[i] <= 1e6).

Assume there is a pointer initially pointing to a[i] or b[i]. For each query, if the number being pointed to is less than X, the pointer switches between a[i] and b[i]. For each query X, find the sum of the entire N-array based on the value pointed to by the pointer. Calculate the sum of all numbers in all configurations after going through Q queries.

Example input: 5 3

10 20

15 25

5 3

7 12

1 4

5

25

8

Output: 168 Explanation: (10+15+5+7+4) + (20+25+3+12+1) + (20+25+5+12+4)

Hi guys, recently I got this problem which has been bothering me for quite a while.

Given an array of N elements and a positive integer K, it is possible to "split" the original array into 1 to k+1 subarrays.

(i.e. slice the original array as much as 0 to k times). Your task is to give the sum of the arrays sub-arrays so that their sum is the smallest, especially the sum of 1 sub-array will be rounded to tens (>=5), ie the sub-array has a sum of 95, it will be counted as 100, if 94, it will be counted as 90.

For instance:

8 2

1 2 3 4 5 6 7 8

output 30, split into 1 2 | 3 4 5 6 7 8

output is 3 (to 0) | 33 (to 30)

And the limit is K<=200 and N<=2000.

Yet this might looks to be a easy problem, I'm scared that my solution could be wrong because my friends have much more complex way to solve like using dijsktra, dp with divde and conquer,...

Here's my solution, please have a look and comment, thank you so much

https://ideone.com/Obwq0N

Hi guys, without further redo, let's get straight to the main problem!

PROBLEM

You're given an N nodes tree, which each of the node contains a weight ai, we call g(x, y) means GCD or greatest common divisors of all the nodes stay on the path from node x to node y, and d(x, y) is the distance between node x and node y. Your task is to find the longest path or the maximum d(x,y) which gives the g(x,y) strictly larger than 1 (>1).

N <= 2*1e5, a[i]<=N, d(x,x) = 1;

Definition for input: 1st line is N, 2nd line is N weights of N nodes, 3rd line + n-1 is the connection of node X to node Y

Example test case:

Input:

3

2 3 4

1 3

2 3

Output:

2

Time limit : 0.5s

Memory limit: 256 mb

little note: this problem is told to be existed somewhere in this Codeforces platform, if anyone know where is it, please give me the link. Thank you so much for your help.

Hello those who are reading my entry, I have a small problem that i'm kinder curious about my solution.

***The problem is:

You have an array of integers (a[i]<=1e6) sized of n (n<=1e3). You have to split the array m different segment which cover the whole array. An action will take 1 unit of time which let you do 1 of those 2 at a time (each take 1 unit of time):

• You can minus 1 from a[i]

• You can plus 1 from a[i]

Your task is to mange to split the segments somehow that all of the value in 1 segment need to be the same by using those action i mention. And also those segment action work separately, which mean the answer would be the maximum action of 1 of those m segments.

Test Case:

Input:

6 2

1 1 2 3 4 3

Output:

1

Explain: 2 segments are 1 1 2 and 3 4 3, you can turn it into 1 1 1 and 3 3 3***

My idea:

Due to the fact that actions need for a subarray is going to be larger if it contains more value (or the subarray is larger) because the action we have to use is abs(a[i]-median) so base on the linear spec, we could use greedy to put as many as we could into a segment so that their action won't exceed the answer (cause we only focus about the max value).

I would use binary search to search for the answer, for each mid I search, I would check it for each segment as I mention to make sure that none of them could exceed by using 2 pointer L and R. For each L, I will find all the median in (L, R) and check to make sure the actions follow the rule by extend the R pointer to the furthest position (rightest what I mean).

And if everything is ok, then just print the answer. However, the time limit could be O(n^2*LogN^2), which mean 20*20*1000*1000 or 400 million calculations, may exceed 1 second limit. Forgot to mention, I use Persistent Data Structures to find the (r-l+1)/2 smallest value to find the median.

time limit: 1s

memory limit: 256mb

Hi, I have a small problem that has been bothering me for a while.

Heres the problem: You're given an array which contains N integers (N <=2*1e5). Your task is to print out the sum of GCD of all 2^n-1 (pow(2,n)-1 for clear statement) subsequence. The definition of an subsquence is a set of index i1, i2, i3, ..., ik that i1<i2<i3<...<ik. You have to moduluo the answer by 1e9+7 otherwise is gonna be overflowed, also a[i] <=1e6 and N <=2*1e5.

A sample test case is:

input: 3 1 2 3

output: 10

input: 5 3 6 9 5 10 output: 72