Hey, can someone tell me what are some of their favorite Div 2 rounds whether they are too old or new, from which they learn new tricks, techniques. Also, who are some good problem setters who set very interesting problems in the past as well as present.

Any suggestions would be helpful. Thanks!

You are given an array of N elements. You have to minimize the absolute difference between the max and minimum element. You can peform this operation any number of times. N can be upto 10^5. A[i] <= 10^9

The elements which are odd you can multiply it by 2. The elements which are even you can divide it by 2.

Eg.

arr[] = 1 2

divide 2 by 2. array becomes 1. Now minmum difference is 1-1 = 0. How to solve this problem.

You are given an array of N integers where N <= 10^5 and arr[i] >= 1 and arr[i] <= 10^6. Each time you find the sum of all the elements in the array, divide it by 2 and take the floor value. The number which is closest to this value is removed from the array, in case of tie the number with lowest id is removed. The process continues until there is single element in the array. Find the single element. The array can have duplicates.

How to solve this problem in the given time constraints. Brute force will be O(n^2)

Example :

N = 4 arr[] = 1 3 5 7

Output = 5

in first step, sum = 16, its half = 8, closest to it = 7, remove 7, now the array is 1 3 5

in second step, sum = 9, its half = 4, closest to it is 3 and 5, 3 is with lowest id, remove it, now array is 1 5

in second step, sum = 6, its half = 3, remove 1. final array is 5.

There were 3 problems, one was valid bracket sequence, other was in out dp but n was 1000 so it can be solved with normal dfs too in N^2. this was the last problem

How to approach this problem. My approach was to find the prfix from 0 to i and suffix from n — 1 to i + 1. concatenate both for a new string and find longest palindromic subsequence for the current string. But it gave wrong answer and later I realized that my approach will not work always.

Any other approach for this problem. The tag was dp for the problem.

Thanks.

Hello. I would be glad if this approach is helpful to anyone.

Solution: x = wins y = draw z = loss

First think that there is no z in the question and we have to satisfy x + y <= n and w*x + d*y = p. if(p % __gcd(w,d) != 0) answer is always -1. Else:

First calculate how much max wins we can achieve, i.e maxwins = p / w. Now calculate the remaining points that are left for us. It is p — maxwins*d, let's say it remaining_points. Now calculate how much max draws we can achieve with the remaining points. It will be remaining_points/d.

Now calculate total points = maxwins_point + draw_points. If this is equal to p, then here is our answer. We have to handle case x>=0 and y>=0 and z >=0.

Now if total_points < p. We calculate the difference between them. i.e difference = p — total_points. If there exists an answer then we must increase our draws and reduce our wins which we earlier calculated as max_wins and draws.

Suppose we increase draw by j more and decrease wins by k. Then this j and k must satisfy d*j — w*k = difference. Now we will iterate on j from 1 to say x. and for each j we check the condition whether there exists a useful k which satisfies our condition. If there is then we get the answer, else it will be -1.

Now what is x. X will depend on our max difference that will arise after dividing remaining_points(mentioned above) / d. since rp % d < d . hence max difference < d. so we iterate from 1 to 1e5. and check for every possible j and k.

Hope this is clear. (http://mirror.codeforces.com/contest/1244/submission/62568232)

MikeMirzayanov Hello, I am facing this problems since 2 days and it is much worse now.

1. Not able to view test case, have to refresh page multiple times and click on "Click to see test details" a lot of times to open it. Many a times there is no link. Even after clicking on "Click to see test details" click link I am not able to view any testcase.

2. In mysubmissions Page, again have to click 10+ times to open mines or any other submission.

Please resolve it asap. MikeMirzayanov

How to find kth largest element each time where k will vary and array is modifiable. That is you can add new elements to the array array can have duplicates.

for example say array is 10 , 20 , 15.

2nd largest = 15

add 17 to array

array becomes 10 15 17 20

3rd largest = 15

Q <= 10^5.

The question is you are given an array A of N integers N<=10^5 and q queries, q <= 10^5.

The are for types of query operation.

1. 0 x y --> find the sum in the range x to y , 0 based index.

2. 1 x --> Append element with value x to the end of array.

3. 2 x ---> Delete element at index x, all the elements from x+1 to n-1 index comes forwards.

4. 3 x y --> Change A[x] to y.

You have to return answer for all sum queries, that is query 1.

How to solve such problem.

answer will be 65 for the 2nd test case?

input 3.

1 , 2 , 4 , 8. and b = 3

fill 1 litre on day 1 and 3 on day 2 , total cost = 7.

my greedy approach of taking as much as we can in a given range with minimum cost fails.

my idea for input 3, fill 3 on day 1, and 1 on day 4 but it gives a cost of 11 which is not optimal.

You are given a permutation of N numbers from 1 to N in an array

You want to sort the array using this operation

1. Send the front-most element X places back in the array;
2. Add x to the total cost.

N<=10^5

Input : A = { 1 , 3 , 2 }

output : 3.

Explanation :

=> Send 1 to index 1. (Cost +1)

A [3, 1, 2]

Send 3 to index 2. (Cost +2)

A = [1, 2, 3]

and the array is sorted.

hence total cost = 3.

Any approach for solving this problem>