I have been trying this dp problem . But couldn't figure out the recurrence relation. The problem description is given below:

Problem Statement:

A long, linear field has N (1 <= N <= 1,000) clumps of grass at unique integer locations on what will be treated as a number line.Think of the clumps as points on the number line.

Bessie starts at some specified integer location L on the number line (1 <= L <= 1,000,000) and traverses the number line in the two possible directions (sometimes reversing her direction) in order to reach and eat all the clumps. She moves at a constant speed (one unit of distance in one unit of time), and eats a clump instantly when she encounters it.

Clumps that aren't eaten for a while get stale. We say the "staleness" of a clump is the amount of time that elapses from when Bessie starts moving until she eats a clump. Bessie wants to minimize the total staleness of all the clumps she eats.

Find the minimum total staleness that Bessie can achieve while eating all the clumps.

Input:

• Line 1 : Two space-separated integers: N and L.
• Lines 2..N+1: Each line contains a single integer giving the position P of a clump (1 <= P <= 1,000,000).

Output:

• Line 1: A single integer: the minimum total staleness Bessie can achieve while eating all the clumps.

Sample Input:

4 10

1

9

11

19

Sample output:

44

Hint:

INPUT DETAILS: Four clumps: at 1, 9, 11, and 19. Bessie starts at location 10.

OUTPUT DETAILS: Bessie can follow this route:

• start at position 10 at time 0
• move to position 9, arriving at time 1
• move to position 11, arriving at time 3
• move to position 19, arriving at time 11
• move to position 1, arriving at time 29

Recently I tried to solve this problem. But couldn't figure out any solution. It will be help if anyone explain the solution of this problem. The problem Link is Here

I am working to make an website, in which I need to parse the Json data of codeforces. For that I am following the API documentation of codeforces. But here I am facing a problem. To get the data of upcoming contest I am sending request from my website using contest.list method. The problem is, it returns all the contests of codeforces. But I just need to get the contest list which phase value is BEFORE. By parsing the data of all the contest it's making my website slower. Is there any way to get the contest list which phase value is BEFORE efficiently ??

UPD: Problem solved. I kept a locale file containing the json data and set a fixed time (say 1 hour). Then I check when the file was last modified. If it is less than the fixed time then the program use the locale cached file. This is making my website faster.

I tried to solve this problem but failed. Would anyone please help me to solve this problem

Problem Statement:

Sameen has:

1.An array having N integers

2.Q friends

His friends are curious about the array. So, each of his friends asks Sameen a question about the array. Every question is described by 3 integers: i, j and k. In reply to a question, Sameen has to say the “k alternating sum” of the subarray starting at position i and ending at position j [1 based indexing]

“k alternating sum” of a subarray starting at position i and ending at position j can be calculated in the following way:

Add the first k numbers[starting from position i]

Subtract the second k numbers[starting from position i+k]

Add the third k numbers[starting from position i+2*k]

Subtract the fourth k numbers[starting from position i+3*k]

And so on till adding/subtracting the j-th number…

(j-i+1) will be divisible by k.

[See sample Input/output and explanation section for more details]

Can you help Sameen in answering the questions?

Input:

The first line of input contains two integers N and Q. The next line contains N integers, the numbers in the array. Then each of the following Q lines contains 3 integers i, j & k.

Output:

For each query output an integer in a separate line, the answer for that query. Queries should be answered in the order given in the input.

Constraints:

1 ≤ k ≤ 100000

1 ≤ N ≤ 100000

1 ≤ Q ≤ 100000

-1000000000 ≤ Value of a number in the array ≤ 1000000000

(j-i+1) will be divisible by k.

Sample Input:

6 6

4 1 -2 -3 4 5

2 5 2

1 6 1

1 6 3

1 6 6

3 3 1

3 4 1

Sample Output:

-2

3

-3

9

-2

1

I tried this problem with segment tree first and got TLE. Then I used square-root but again got TLE. To solve the problem with square-root i used tree which size is sqrt(n) * sqrt(n), where n is the size of the array. In every block of the tree I kept sqrt(n) elements of the array sorted in ascending order. When update occur I push the element in a block where it's index remain and again sort this block. And when i got query operation for every block which is in the range I found how many elements are less than the given value. This can be done with binary search for every block. Please tell me where i should optimize my code. Here you can have a look at my code .

I tried to solve this problem with the help of bitmask. Because the number of prime is very low. But couldn't come up with a exact solution. It will be helpful if anyone help me to find out a solution. The problem statement is given below:

You are given N(1<=N<=100000) integers. Each integer is square free(meaning it has no divisor which is a square number except 1) and all the prime factors are less than 50. You have to find out the number of pairs are there such that their gcd is 1 or a prime number. Note that (i,j) and (j,i) are different pairs if i and j are different.

Input:

The first line contains an integer T(1<=T<=10) , the number of tests. Then T tests follows. First line of each tests contain an integer N. The next line follows N integers.

Output:

Print T lines. In each line print the required result.

Sample Input:

1

3

2 1 6

Sample Output

8

I tried this problem for a long time but could not solve.. How to solve it?? Any explanation or hints from expert will be helpful for me..The problem statement is given below:

Given n objects you’d have to tell how many different groups can be chosen if r objects are taken at a time.

Input

Input consists of 100 test cases. Each test case begins with two integers n (0 < n ≤ 50), m (0 ≤ m ≤ n). The next line will contain the labels (numbers in the range 1 to n) of the n objects you are to choose from. Two objects with the same label are considered equivalent. Then in the last line for that test case, you’d have m values for r. There will be a single space separating two consecutive numbers in a line. Input is terminated by a test case where n = 0, you must not process this test case.

Output

For each test case, print the test case number. And for each query number r, print the number of different groups that can be formed if r objects are taken from the given n objects. You can assume that for all input cases, the output will always fit in a 64-bit unsigned integer and (0 ≤ r ≤ n).

Sample Input

5 2

1 2 3 4 5

2 1

4 1

1 2 3 4

2

0 0

Sample Output

Case 1:

10

5

Case 2:

6

In 620C - Жемчужинки I watch some source code of other people. Most of them used map. They iterate for n times and count the element of the array using map when they find that the value of current element in the map is 2 then they clear the whole map.. For that I am bit confused about that solution. It will be pleasure if anyone tell me what is the actual complexity of that solution :)

How can I find out the number of bi connected component in a graph? I can find both articulation point & bridge but failing to implement bi connected component..Any pseudo code will be helpful...

How can i find the articulation point in a graph using DFS algorithm ??? Any pseudo code or source code will be helpful for me......