HEIR_OF_SLYTHERIN's blog

By HEIR_OF_SLYTHERIN, history, 18 months ago, In English

Question: You are given N circles, with ith represented by coordinates of centre as xi,yi and radius ri(all circles lie on the xy plane). The task is to remove minimum number of circles such that the remaining circles do not overlap or touch each other.
Note: Ci, Cj are overlapping is the distance between their centre points <=ri+rj.
Constraints:
2<=N<=1000
0<=xi,yi,ri<=10000
Input format:
First line contains N
The next N lines contains three integers xi,yi,ri.
Sample input:
3
0 0 3
2 0 3
4 0 3
Sample output
2

Any help in algo or idea is appreciated. Thanks in Advance.

Full text and comments »

  • Vote: I like it
  • +2
  • Vote: I do not like it

By HEIR_OF_SLYTHERIN, history, 19 months ago, In English

Question: A global distribution company has a stack of many items in its warehouse. Each stack is stored in the form of piles. The height of some ples is very high, and the height of some piles is very low and this unevenness is causing problems in the warehouse. To solve this, the company has developed a robot which will help in arranging all the piles property. To do it the company has prepared a list of N piles which contains the total number of items in each pile, each pile in the text has been identified by a unique to ranging from 0 to (N-1). The robot will go through this list first and then remove the items from the piles in such a manner that after removing all the items, the difference between the total items of any two piles is at most K. The robot can also remove a pile completely or left a pile complimely untouched if a pile has been removed completely than that pile will automatically get deleted from the list and will not be used in farther calculation.

Werse an algorithm for the robot to calculate how many items it will remove in seal from the piles

Input: The first line of the input consists of an integer — totalPiles, representing total number of piles in the warehouse(N). The secondline of the input consists of N space seperated integers representing the total number of items in each pile The thirdline of the input consists of an Integer- represents maximum difference between any two piles(K).

Sample testcase input:
4
3 1 5 1
2
output:
2

My idea: Every time we have two choices either remove the smallest element or subtract the excessive items wrt the minimum. Can some one help me with the idea or psuedo code?

Thanking you in Advance.

Full text and comments »

  • Vote: I like it
  • +8
  • Vote: I do not like it

By HEIR_OF_SLYTHERIN, history, 19 months ago, In English

Can someone explain the optimal solution for finding the sum of XOR of all sub-arrays of the array. Example:

Input : arr[] = {3, 8, 13} Output : 46

XOR of {3} = 3 XOR of {3, 8} = 11 XOR of {3, 8, 13} = 6 XOR of {8} = 8 XOR of {8, 13} = 5 XOR of {13} = 13

Sum = 3 + 11 + 6 + 8 + 5 + 13 = 46

Thanks in Advance.

Full text and comments »

  • Vote: I like it
  • +2
  • Vote: I do not like it

By HEIR_OF_SLYTHERIN, history, 4 years ago, In English

Floyd-Warshall's algorithm--

let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
for each edge (u, v) do
    dist[u][v] ← w(u, v)  // The weight of the edge (u, v)
for each vertex v do
    dist[v][v] ← 0
for k from 1 to |V|
    for i from 1 to |V|
        for j from 1 to |V|
            if dist[i][j] > dist[i][k] + dist[k][j]
                dist[i][j] ← dist[i][k] + dist[k][j]
            end if

can someone explain why the order of the last three "for statements(for k from 1 to |V|, for i from 1 to |V|, for j from 1 to |V|" doesn't matter the result of the program??.

Full text and comments »

  • Vote: I like it
  • +12
  • Vote: I do not like it