Hi! I have been trying the following problem for some time now and haven't been able to come up with a solution better than O(N^2).

Given an array A with N integers, define max_i, j to be the maximum value in A[i..j] and min_i, j to be the minimum value in A[i..j]. A[i..j] denotes the subarray starting from index i and ending at j. Compute the following sum:

Please let me know if this problem is available on some OJ.

Hi!

How to solve the following problem: https://www.hackerearth.com/problem/algorithm/hanumant-and-his-love/description/

The problem asks to solve the following summation:

where p is a prime and φ(m) is the Euler totient function.

Thanks!

Hi!

How to solve this problem: https://www.codechef.com/ACMIND16/problems/ICPC16E ?

Thanks!

Hi all!

I don't have the exact problem statement, it was asked in one of the coding tests for an interview but I think I remember the problem quite well.

Given an array of n values, we have to make two sets such that size of first is at most k and size of second is at most s. The difference of sum of values in first set and sum of values in second set is minimum. I need to find this minimum value.

The sets must be non-empty.

Constraints: n<=200, k,s<=100, 0<values in array<=1000

Please let me know if something is unclear.

Thanks!

Hi all!

Following is the problem:

Dr Emmett Brown has decided to change his job and is now working as a Computer Science teacher in a high school. The Dr Brown's class has n students. Dr Brown wants to run a programming contest for his students. But his classroom only has k computers, so he needs to run a team contest. Dr thinks that the teamwork would be good for the students if the students in the team all have close levels of their skills. For each student Emmett Brown knows its skill level ai. He has decided to create teams in such way that for any two teams there is a number x such that students in one team have skill level at most x, and in the other team all students have skill level at least x. There must be exactly k teams, each team must have at least one student, but there is no upper limit for the number of students in one team. Help Doctor to find out how many ways are there for him to create the teams. Two ways are different if there are two students that are in the same team in of the them, and in different teams in the other. You should output the number of ways modulo 10^9 + 7.

Constraints: 1<=n, k<=2000 1<=ai<=n

Sample: n=3, k=2, a=[1,2,3] ans = 2

n=7, k=3, a=[2,4,3,4,3,3,2] ans = 53

Here is the editorial for the problem: http://codeforces.net/blog/entry/44517

Can someone please explain the editorial? I do not understand how the dp relation works and the intuition behind it.

Help is appreciated. Thanks!

Hello!

I am trying to solve this problem https://www.codechef.com/problems/QCHEF using Mo's Algorithm+Segment Tree but my solution times out. Complexity of my solution is . Is it possible to eliminate the log factor? I know there is an editorial with the problem, (it uses a different decomposition, I think) but I am wondering if my solution can be optimised to .

My solution: https://www.codechef.com/viewsolution/10638667

Thanks!

Hello all! :)

I stumbled upon this problem but I do not know how to solve it.

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

The sum can be written as

but this doesn't make the problem any easier. I can evaluate the first sum but its not easy to evaluate the second. Please give me some ideas to solve this.

Any help is appreciated. Thanks!

Hello all! I came across this problem: https://www.codechef.com/problems/ACM14AM5/

I honestly have no idea where to start with this one. Can somebody please provide me some hints to start with? Thanks! :)

Hello all! I was trying to solve this problem from the recent APAC contest: https://code.google.com/codejam/contest/10214486/dashboard

I think this problem can be solved by dijkstra's shortest path algorithm. I precompute the minimum time taken from the source for every value of S so that the queries can be answered in constant time.

Here's my code: http://ideone.com/cle94b

I don't see why I am getting a WA.

Any help is appreciated. Thanks!

Hello all! I found this problem on CodeChef: http://www.codechef.com/problems/PRYS09

I honestly don't know where to start. The brute force approach obviously won't work. Also, there are no solutions and editorials available probably because this is an old contest problem and remained unnoticed by the users. Please help!

Thanks!