### Death_Scythe's blog

By Death_Scythe, history, 4 months ago, ,

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 maxi, j to be the maximum value in A[i..j] and mini, 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.

•
• +20
•

By Death_Scythe, history, 14 months ago, ,

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!

•
• +35
•

By Death_Scythe, history, 19 months ago, ,

•
• +13
•

By Death_Scythe, history, 19 months ago, ,

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!

•
• -1
•

By Death_Scythe, history, 22 months ago, ,

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.com/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!

•
• +1
•

By Death_Scythe, history, 23 months ago, ,

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!

By Death_Scythe, history, 2 years ago, ,

Hello all! :)

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

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!

•
• +3
•

By Death_Scythe, history, 2 years ago, ,

Hello all!

This problem is inspired from a math test my brother wrote recently and I thought this could be a cool programming problem. ;)

Please don't downvote if this is a stupid problem because it is very hard for me so I decided to post it. :P

You are given a tree with N nodes. Arrange N people on these nodes such that in any two arrangements, neighbours for all of them are not same.

For example, consider the simplest chain of N nodes (which is also a tree), there are N!/2 arrangements.

Another example, consider a tree with 6 nodes, the edges are 1-2, 2-3, 3-4, 4-5 and 4-6, total possible arrangements = 360.

I don't know what should be the constraints on N so that the problem is solvable. I hope to see interesting solutions, if possible, for this problem.

Thanks! :)

•
• -9
•

By Death_Scythe, history, 3 years ago, ,

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

•
• +3
•

By Death_Scythe, history, 3 years ago, ,

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!

By Death_Scythe, history, 3 years ago, ,

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!