### jd_sal's blog

By jd_sal, history, 12 months ago, Hello all,

This is a problem from the recent contest Codeforces Round #643 Div 2 named Game with Array (Problem D).

First claim of the editorial is that the answer is "NO" if S<2*N. I find it difficult to reach this conclusion during the contest.

As I can see that a lot of people were able to solve this problem during the contest, so I would like to hear your exact thought process/intuition/reasoning which you used during the contest. It would be great if you explain in detail.

Thank you. By jd_sal, history, 13 months ago, I am not able to understand the solution of the last problem from Hack the interview II -Global, a contest on Hackerrank which finished few days ago.It's labelled 'HARD'.

I don't get what is len = m-2-2*p in the first solution ? Although both the solutions are same.

It will be really helpful if someone explains me the solution. Thanks! By jd_sal, history, 13 months ago, Could you please tell me the topics I need to study for solving DIV2C and DIV2D problems on Codeforces? I have observed that DIV 2C doesn't require any special algorithm or data structure, as it involves basic paradigms like greedy,dp,two pointer,binary search etc with a bit of twist. But what about DIV 2D? Since I am currently focusing on DIV2 A,B,C,D only, please provide me the exhaustive list of topics for problems till DIV 2D. Since many of you have a lot of experience so please guide me with what you observed. Thank you. By jd_sal, history, 19 months ago, Given an array of integers say A and a number k.One operation means choosing an index i of array and increasing A[i] by 1.You can use this operation on a particular index multiple times.You perform at most k operations(not necessarily on a single index) on this array after which some number X is repeated maximum number of times say Y, then print Y,X.If for a Y, multiple X exist then print the smallest such X. For example let A=[1,9,11,19] and k=10. We can form [9,9,11,19],[1,11,11,19],[1,9,19,19] so answer will be X=9, Y=2.

Constraints : A.size()<=10^5 and 0<=K<=10^9 and -10^9<=A[i]<=10^9.

I can do it in O(n^2) but it's obviously not optimal. Any idea how to proceed?

It's not from any ongoing contest. By jd_sal, history, 21 month(s) ago, Problem statement : Given an array of integers A of size N. An array is called power array if floor(maximum of array/2) >= all other elements of array. E.g [5,3,6,13] is a power array since 13/2 >= 5,3,6. Calculate how many subarrays of A are Power Arrays. Note : Single element can never be a power array.Constraints : 1<=N<=10^5 , 1<=A[i]<=10^5 .

I can think of a O(n^2) solution but it will definitely timeout. Any efficient solution? P.S : It's from a contest which has ended!

By jd_sal, history, 21 month(s) ago,  dp,