### gXa's blog

By gXa, history, 4 months ago, ,

Initially the array contain all 1s.

There are two type of operation:

1 A: update arr[A] = 0.

2 A: Find index of Ath 1 in the array.

Number of elements, 1<=N<=(1e6)

Number of queries, 1<=Q<=(1e6)

I tried tree statistic. However, it didn't pass.

•
• -17
•

By gXa, history, 4 months ago, ,

You are given N candies and K boxes. You need to find the number of ways to divide N candies in K boxes such that each box should have one candy and you should not count repetitive sequences. The boxes and candies are identical.

Is there any question similar asked before?

•
• +3
•

By gXa, history, 10 months ago, ,

This is word search problem but constraints seem to be quite strict. Can somebody help with a solution which could pass time limit?

Find Word in Grid

•
• +18
•

By gXa, history, 11 months ago, ,

Can lower_bound and upper_bound work with vector of pair<pair<int, int>, int> or nested pairs. I tried doing so but it is showing me error. So, how should we do that?

•
• -2
•

By gXa, history, 11 months ago, ,
Suppose there are two piles of plates in the table. One has ‘m’ RED plates and other has ‘n’ BLACK plates. In his/her chance, a player can either pick any number of red plates or any number black plates or equal number of red and black plates. A player loses if he cannot make a move in his/her chance. You are playing this game with your friend. Given that you begin the game and both the players play optimally, output ‘L’ if you will lose or ‘W’ if you will win.


Example:

input: m = 1, n = 2

output: L

input: m = 2, n = 2

output: W

•
• +12
•

By gXa, history, 12 months ago, ,

Give N=no. of players

K=No. of fans

likeMatrix=It is a sting array of size K where each element of array have size N.

(contains 0 and 1 only) where if a[i][j] ==1 represents fan(i) likes player(j)

Ex. N=5

K=3

like={ "10101","00001","01011","...","...." }

Count min. no. of players required to put in team such that each fan likes atleast one player.

I think it is minimum bipartite matching(just opposite to maximum bipartite matching). So, can anybody tell me how to solve it?


•
• +6
•

By gXa, history, 12 months ago, ,

Hi, I have a question:

You are given 100 stations and distance between each adjacent stations. Now you have to select 10 stations(means 10 hops) among those 100 stations in such a way that maximum of distance between any 2 hops will be minimised. By default 1 and 100 stations are selected , so you need to choose only 8 more stations.

Here n=100 I have chosen but n can be large( so bruteforce won't work ).


•
• +8
•

By gXa, history, 12 months ago, ,

This is one of Interview Question.

You are given the string of a's and b's, eg. aaabbbaa and some threshold value t which indicates the threshold point, eg if count of a's or count of b's will become equal to t then whose count will be equal to t eg. a or b will win that match, and next game will continue further, eg from that index of a and b new count values will be incremented, and the process will continue, and at the last you have tell who won the match, a or b.

Expected time complexity: O( n*log(n)*log(n) ).

•
• -4
•

By gXa, history, 12 months ago, ,

A tree is given in which each edge is having some weight associated with it and you are given a number K.

So starting from root in K-steps how much maximum weight you can collect. You can traverse in any direction either from parent to child or child to parent. You can visit a node multiple times.

~~~~~ ~~~~~

Spoiler

•
• -2
•

By gXa, history, 12 months ago, ,

Hi, please provide an algorithm for this question: Click

I am trying it from long time but couldn't reach a proper algo.

•
• -17
•

By gXa, history, 12 months ago, ,

This is one of the interview question.

Given row on N house, each is marked either R or B and each house having some gems.

You have to collect gems from these house with some constraint: You can choose gems from any blue house but you have to choose even number of red house ( either from 2 Red houses or from 4 red houses)

Each time you take gem from one house, you will multiply gems received with gems currently, you have.

You have to choose continuous houses and maximise the product.


You have to return start point and end point of house (remember this should be continuous ).

I can think of O(N^2) solution but not better than that. So, can someone recommend a better algorithm.


•
• +1
•

By gXa, history, 12 months ago, ,

You are given a lot of cuboid boxes with different length, breadth and height. You need to find the maximum subset which can fit into each other (length, breadth and height of first block greater than length, breadth and height of second block).

For example:

If Box A has LBH as 7 8 9

If Box B has LBH as 5 6 8

If Box C has LBH as 5 8 7

If Box D has LBH as 4 4 4

Now, algorithm is first sort in terms of length, then find MIS of breadth and from previous result find MIS of height, however order can play a role here.

So, it is requested if someone can give a proper algorithm for this.

•
• +4
•

By gXa, history, 12 months ago, ,

I got solutions on internet but it is quite difficult to understand. Plz can someone explain this.

You are given an integer N. You have to find smallest multiple of N which consists of digits 0 and 1 only. Since this multiple could be large, return it in form of a string.

Note: - Returned string should not contain leading zeroes.

For N = 55, 110 is smallest multiple consisting of digits 0 and 1. For N = 2, 10 is the answer.

•
• +9
•

By gXa, history, 15 months ago, ,

Why is this https://ideone.com/gCdcs4 giving me runtime error but this does not https://ideone.com/14lMhi for http://codeforces.com/problemset/problem/779/C?

I have just changed equality sign. I have figured out the input but not aware of why it is happening so?

•
• +6
•

By gXa, history, 16 months ago, ,

Please tell the complexity of http://www.geeksforgeeks.org/maximum-bipartite-matching/ ?

And if we use directly Ford-Fulkerson Algorithm, will it be better?

•
• +4
•

By gXa, history, 17 months ago, ,

Hi, can somebody point a site or good resources where I could find all APAC editorials. For 2017, I find few blogs on Codeforces, but couldn't find much of previous APACs — 2016, 2015, 2014, etc.

•
• +2
•

By gXa, history, 22 months ago, ,

Hi everyone, I am trying to find all permutations of the input elements which will result in the same Binary Search tree as the one formed with the input array.

Eg: I/P: 4, 3, 1, 2, 6, 5, 7

o/p:4 , 6, 3, 7, 5, 1, 2

4, 3, 2, 1, 6, 5, 7

and so on.

I have gone through links on internet but could not code it.

I am unable to print all the permutations correctly. So, I request community to help me with logic ( if recurive function can be provided too )?

Thank You

•
• +17
•

By gXa, history, 2 years ago, ,

Order in terms of speed?

Algorithm A requires solving 3 problems of size n/3, and takes 4n computation steps to divide and combine.

Algorithm B requires solving 2 problems of size n/2 and takes n log log n computation steps to divide and combine.

According to me:

A == O(nlogn)

B == O(nlogn)

So both have same speed or how we will distinguish between the two?

•
• +10
•

By gXa, history, 2 years ago, ,

Can somebody help me in finding running time of algo: Partitions the problem into two sub-problems of sizes n/5 and 7n/10, and spends O(n/log n) time to divide and combine the solutions.

•
• +10
•

By gXa, history, 2 years ago, ,

Can someone please help me to solve this using recursion tree method, I am trying it but unable to solve it. T(N) = sqrt( N ) T( sqrt( N ) ) + sqrt( N )

•
• -7
•

By gXa, history, 2 years ago, ,

We have designed an new algorithm to sort a list of n numbers. We recursively partition the numbers into groups of size sqrt(n) each until we are left with lists of constant size; at which point we use insertion sort to sort the numbers. To combine solutions, we do a merge of the sorted lists, namely maintaining pointers to the start of the list and at each step advancing the pointer of the list corresponding to the smallest element. Let T(n) denote the running time of this algorithm (we can assume that sqrt(k) is an integer for all k<=n encountered in the algorithm).

Running time : T(n) <= sqrt(n) T( sqrt(n) ) + O(n^1.5)

I can think of it as T(n) = T( sqrt(n) ) + T( n-sqrt(n) ) + O(n) but can't relate to the solution. Plz can anybody explain its running time.

•
• -13
•

By gXa, history, 3 years ago, ,

Can anybody plz explain why the upper bound of n in problem Primes or Palindromes? is 10^7. I have spent a whole day but coul not figure out. Plz can someone explain rigourously.

•
• +1
•

By gXa, history, 3 years ago, ,

Why this compiles: Plz guide me on this:

int main() {

for(int i = 0; 0; i++) {

cout<<"H"; }

}

Can u elaborate the working of this code?

•
• -12
•

By gXa, history, 3 years ago, ,

In java 8, all the commands of java 7 work or not.

I am asking this question because in c++ 11 #define tr(c,it) for(typeof(c.begin()) it=c.begin();it!=c.end();++it) does not work while in c++4.9.2 it works.

So I wanted to know which one is better java 8 or 7 and if java 8 then all commands of java 7 work on it or not. Plz help me in this.

•
• -12
•

By gXa, history, 3 years ago, ,

If N and M are used as double, then for comparing them, can we do this:

if( N<=M ) { cout << "Yes"; }

If not then suggest what to do?

If N is long long and M is double, then for comparing them, can we do this:

if( N<=M ) { cout << "Yes"; }

If not then suggest what to do?

Comparison with double is causing me problem. So guide me what to do?