This problem was asked in Amazon OA few days back

Algorithm to solve this problem — If all weights were distinct solution is pretty simple — find 'r' the last and only occurrence of smallest number in the weight array — now travel efficiently through the second smallest number and push it to smallest position > r -> now do the same algorithm for the third number — this time 'r' will be the last and only occurrence of the second smallest number

Problem — This algorithm does not work if there are duplicate numbers in the weight array

-> [2 1 1 1 1 2 3 3 3 3 2]

-> [5 1 1 1 1 2 1 1 1 1 100]

It will take 3 moves on w[0] so it gets to a free position on the co-ordinate axis.

But if you make single move on w[5] towards the right — then w[0] can take place of w[5] in just total two moves.

So how to deal with which strategy to apply for duplicated numbers ?

I think it is impossible to solve this problem for duplicate numbers as it is NP-hard problem as per this blog — https://codeforces.net/blog/entry/103255

This problem was asked in recent CodeNation Online Test — Please give your solution idea to it

Given A,B,C — Count the number of valid arrays of size "A"; such that each number of the array is in the range [1,C]; and no subarray of length > B exists in the valid array such that all elements of that subarray are equal

1<=A<=10^9

1<=B<=50

1<=C<=10^5

A = 3

B = 1

C = 3

Output — 12

[121], [123], [131], [132], [213], [212], [231], [232], [312], [313], [321], [323] are all valid arrays.

Idea = Valid Arrays = Total — Invalid arrays = Counting of Invalid Arrays is easier than valid arrays as far as I can conclude.

This problem was asked recently in Atlassian OA.

Given an array ; in 1 operation you can add + 1 to any element of the array

This operation costs c[i] if you perform this operation on element at index "i"

Find minimum cost to make all array elements distinct

1<=N<=100000

1<=A[i]<=1000000000

1<=c[i]<=100000

Input —

A — [1 2 2] C — [1 100 500]

O/P — 100 — Do +1 operation on second element making the array — [1 3 2]

We are given an array "A" of size "N"

Constraints :

1) 1<=N<=100

2) 1<=A[i]<=30

We have to generate an array "b" of size "N" such that for all pairs (i,j) , gcd(b[i],b[j]) = 1, holds true for array "b" .

The value to be calculated is : abs(A[1]-b[1]) + abs(A[2]-b[2]) + ...... + .... + ..... abs(A[n] — b[n]) = x

We have to minimize the value of 'x'.

How to generate an array "b" which minimizes the value of "x" ?

Example array "A" :- {1,2,4,6,8}

Output array "b" : — {1,2,3,5,7}

and x = 3, which is the minimum possible value.

I got code for this problem in a group : — https://ideone.com/VUyN5p

But still cannot get the idea behind the solution.

Given three arrays a,b,c all of same length N. You want to minimize the value of :

max( (a(i)+t)%k + (b(i)+t)%k + (c(i)+t)%k ) , for all 1<=i<=n .

where 't' can be any non-negative integer.

Input : Three arrays of size 'N' and an integer 'k'. How to find a 't' which can minimize this value ?

Link to the problem : https://atcoder.jp/contests/abc138/tasks/abc138_f

Problem Statement : Given are integers L and R . Find the number, modulo 10^9 + 7 , of pairs of integers ( x , y ) , ( L ≤ x ≤ y ≤ R ) such that the remainder when y is divided by x is equal to y XOR x .

1<=L<=R<=10^18

Basically, the crux of the problem is to find all the pairs (x,y) such that y>=x, MSB of "y" and "x" should be same , and wherever(position) the bits of "x" are set(1), at those positions, bits of "y" must also be set.

In the editorial,they solved this task using dp. (but gave close to no explanation what is done in the dp and its states)

Link(s) : 1)https://img.atcoder.jp/abc138/editorial.pdf

2)https://codeforces.net/blog/entry/69181?#comment-536085

But , nowhere is it mentioned what are the states of the dp ?

(dp[i][j][k][l] is used , but whats the meaning of "i" , "j" , "k" and "l" here ?)

Can somebody make the dp-states and transitions explanation simple and to the point ?

Problem : — Given an array ,find the size of the smallest subset with maximum Bitwise OR .

Constraints : — 1<=N<=100000 ; 1<=A[I]<=1000000000

I found an article which solves this problem : https://www.geeksforgeeks.org/size-of-the-smallest-subset-with-maximum-bitwise-or/

But this solution[greedy] fails on the test-case : {56,33,7}

So is there any real solution for this problem ?

This is a graph problem from the previous contest by Codenation .

Can you suggest some ideas to approach it or sketch the solution ?

Problem :- You are given a DAG(Directed A-cyclic Graph)

You are also given a source node- 'X' as input .

For each node 'Y' , find the number of paths that start at 'X' and end at 'Y' , such that the number of nodes visited along that path is even(including X an Y)

Note:- The path from X to X consists of only one node and hence the number of the nodes visited is odd. Hence there are 0 paths for X to X which consist of even number of nodes.

The number of test-cases:- 20

Number of nodes in the graph(n):- 100000.

Edges:- [1,minimum(100000,n*(n-1)/2]

Output:-'n' space separated integers such that the i'th element is the answer for node 'i', mod 1000000007

Thanks :-)

Warning:-This is a beginner's/newbie's doubt so don't read further and waste your precious time if you are not interested :-)

I am new to Codeforces, so please don't down-vote. I'll delete the topic if needed.

We are given an array and I have to calculate the product of frequencies of numbers in a particular range of the array i,e. [L,R].

How to do it?

My approach:- Say, [1,2,2,2,45,45,4]. L=2 and R=6. Answer=3(frequency of 2)*2(frequency of 45)=6.

Just traverse the array and put the frequencies of each number in a map; finally multiply all those values. Is there any better method to do this for multiple range queries online?

Do we require persistence ?

I want to calculate ((a/b)^n)%e.

I know, how to calculate (a/b)%e; the formula is: (a%e * (b^-1%e))%e.

So, the answer to the above question should be,

(a^n%e * ((b^n)^-1)%e)%e

Am I right ?

Plus, I know how to calculate b^-1 , but I want to know, how to calculate (b^n)^-1

Thanks .

You are given a string of length 'n'.

If a string contains at least one character whose frequency is greater than or equal to the half of the length of the string, then the string is called superior.

You are required to find the length of the longest superior substring available in the given string.

Note: Here half is considered under integer division i.e. 5/2=2 , etc.

The string contains only lowercase English alphabets.

I have tried O(n^2) solution(s) with some optimization(s) which obviously got timed out. I realized that there are better:- O(nlogn) or O(n) approaches,can anybody explain them?

Link to the problem statement :- https://www.hackerearth.com/practice/algorithms/searching/binary-search/practice-problems/algorithm/superior-substring-dec-circuits-e51b3c27/

Thanks :-)