i came accross thisproblem from one web page, i have tried my best to resolve. i couldn't. i think i am lacking in the logic. can any one solve and tell me the logic with source code..
Problem is:
<div>Meeting Point (50 Points)</div> <div> </div>
There is an infinite integer grid at which N people have their houses on. They decide to unite at a common meeting place, which is someone's house.
From any given cell, all 8 adjacent cells are reachable in 1 unit of time.
eg: (x,y) can be reached from (x-1,y+1) in a single unit of time.
Find a common meeting place which minimises the sum of the travel times of all the persons.
Input Format: N
The following N lines will contain two integers saying the x & y coordinate of the i-th person.
Output Format: M M = min sum of all travel times;
Constraints: N <= 10^5
The absolute value of each co-ordinate in the input will be atmost 109
HINT: Please use long long 64-bit integers;
Input #00:
4
0 1
2 5
3 1
4 0
Output #00:
8
Explanation: Sums of travel times of the houses are 11, 13, 8 and 10. 8 is the minimum.
It would be easier to understand if you drew a grid on a blank peice of paper with a pencil.
For the sake of comprehension, pretend the centermost cell is the closest to all random persons. Now randomly pick other cells and count how many cells they're away from the center cell. Once you understand that, write the code for it.
can any one solve and tell me the logic with source code
probably mathematicians who specialize in graph theory could mentor you; you might have to write the code yourself
ashok2009cse
There is an infinite integer grid
it's unsolvable if it's infinite.
ashok2009cse
From any given cell, all 8 adjacent cells are reachable in 1 unit of time.
no, edge cells can reach fewer houses ... look at a chess board
N.B.: let's use a chess board, home position, as an example,
rowas are 1 to 8; columns are a to h
let's say that both White bishops (c1 and f1) wish to meet with their count parts (c8 and f8) at d4
if your cells are squares of the same size, like the chessboard, then your problem is simple ...
however, since you do not know where the meeting will take place, in pseudo code, your logic would be
something like this ...
(a) create an arrary (Int32, Int32) of n by m where n is the total number of cells (64), m are the number of participants
[0, 0] would be the distance for the c1 bishop to a1 (2);
[0, 1] would be the distance for the f1 bishop to a1 (5);
et cetera
b) you'd also need to store your path ... for c1 to a1, the path is c1==>b1==> a1
(c) NOTE: a1 is the White Queen Rook's house ... you said someone's house
so according to your problem definition, that someone might not be one of the people who wish to meet.
(d) your problem is simpler if the someone's house must be a home of one of the meeting participants ... for this restricted case, the distance for one participant will always be
zero. so you basically would compute the routes from everybody to everybody else ...
note: in the case of the four bishops, any house will do because of the symmetry of their positions on the chessboard.
g.
B-) Please help me by completing my school survey about computer programmers on my website. Thank you!!! Gerry Lowry +1 705-429-7550 wasaga beach, ontario, canada
p.s.: via Google, or your favourite search engine:
graph theory shortest path algorithm
B-) Please help me by completing my school survey about computer programmers on my website. Thank you!!! Gerry Lowry +1 705-429-7550 wasaga beach, ontario, canada
no, edge cells can reach fewer houses ... look at a chess board
Again, not true. Because the grid is infinite, there are no edges. The chessboard doesn't help here at all.
For the OP, the exam questioner (or homework assigner, if you like) has made life easier for you, as you can trivially calculate the distance between any two homes as the larger of dX and dY (where dX is the difference in the X coordinates, and dY is the
difference in the Y coordinates) due to the fact that the cost of moving diagonally is (artificially) the same as moving horizontally or vertically.
To calculate which is the optimal, simply
Set a variable (call it average distance) to 0.
Loop through all N participants.
For each, calculate the average (Mean, Median or Mode is up to you to think about) distance to all the other houses. If it's less than the variable above, remember it (and remember which house you're currently processing)
Now this is a brute force approach (if you like), so it is clearly inefficient as N tends to large numbers. But it doesn't require you to hold more than one house identifier and two distances in memory at any time, so it's very memory efficient. Unfortunately,
gerrylowry's approach cannot work due to the infinite nature of the grid.
N people constrained by N <= 10000 gives
N == 0 | 1 | 2 | 3 | ... | 9998 | 9999 | 10000 since we can not have
< 0 people.
N == 0 has no solution.
if we only meet at the home of a participant, N == 1 would meet in her/his own home, a distance of
zero.a
OTOH, if the meeting home can be any home, given a infinity grid there is
no solution ...
from cell c to cell c' is one unit, fromcell c to cell c'' is 2 units, fromcell c to cell c'" is 3 units, fromcell c to cell c'''' is 4 units, fromcell c to cell c''''' is 5 units, fromcell c to cell c'''''' is 6 units, ...
there will always be one cell further away from the previous cell in each of eight directions ...
... no solution Q.E.D.
However, the O.P. stated a second constraint, no co-ordinate's absolute value >
10^9 ... imho, this is a bit of a silly constraint because the problem does not state the co-ordinate system to be used ... so let's invent one of our own:
from x we can move only in 8 directions (assuming our
cells are uniform squares) ...
our directions are up, down, left,
right, diagonally up left, diagonally up right,
diagonally down left, and diagonally down right
this means that we can not always move in a straight line
so, our co-ordinate system much be a direction and a value
if x is at 0, 0, then we
could have someone (harry) at 999 999 999
up
if x is at 0, 0, then we
could have someone (mary) at 999 999 999
down
now, we have a problem ... (harry) and (mary) each meet the distance constraint (10^9) with
x, but fail it with each other.
for simplicity, let's pretend that we have an
edge corner, like a1 on the chessboard, and called it
0, 0 ... we can also have 0, 999 999 999 right and
0, 999 999 999 up ... the n,n diagonal would take us from 0, 0 to 999 999 999 diagonally up right, .... because we are measuring distance by
cell count, 0, 0 to 999 999 999up,
0, 0 to 999 999 999diagonally up right, and
0, 0 to 999 999 999 right ALL seem to be the same distance, however, the
diagonal (hypoteneuse) distance is larger (Pythagorous).
(again, keeping it less complex, every house would have to be in the centre of it's cell and every house would have to be the same size ... even that's a problem because the houses would have a front door, back door, and meybe one, even two side doors,
but not likely also corner doors for people approaching diagonally).
back to the chessboard for a moment: let''s move the white queen from d1 to a3;
d1, c1, b1, a1, a2, a3 == 5 cells away
d1, c2, b2, a3 == 3cells away
d1, c1, b1, a2, a3 == 4 cells away
of course, if we gave the queen a helicopter, she could fly directly to a3 but we'd have to add in the take off and landing distances because the queen's helicopter would not want to crash into other chess pieces on its way to a3.
i am not a mathemation .... however, it's
reasonable to make some assumptions ...
(a) we will have 2 to 9999 houses distributed pseudo randomly in a 999 999 999 x 999 999 999 grid;
(b) we will not visit houses of strangers so we will ignore the houses on non-meeting participants
(c) our 999 999 999 x 999 999 999 grid is one of infinite 999 999 999 x 999 999 999 grids on our infinite super grid
(d) our problem is only solvable within the boundaries of any one or more 999 999 999 x 999 999 999 grids but if and only if we restrict the total number of grids to a finite number.
(e) the house(s) nearest the centre of the grid will not always be the ideal destination (back to the chessboard, the black queen, if on d5 would have to travel towareds a1 if the other meeting participants were on a1, b1, and c2) ... occassionally,
a home in the largest cluster of homes may turn out to be the best soulution.
(f) often, there will be multiple best solutions ... example, 4 participants, one each, at (0,0), (9,0), (0,9), and (9,9).
B-) Please help me by completing my school survey about computer programmers on my website. Thank you!!! Gerry Lowry +1 705-429-7550 wasaga beach, ontario, canada
i am not a methematician ... so DMW, either there are no edges in our
infinite grid or there are infinite edges ...
likely you are correct when you state "Because the grid is infinite,
there are no edges".
g.
B-) Please help me by completing my school survey about computer programmers on my website. Thank you!!! Gerry Lowry +1 705-429-7550 wasaga beach, ontario, canada
Have you actually read the problem definition. It is really clear and really precise, and it is definitely solvable.
If you read the problem, you realise that
1. The universe is defined as a square grid of square cells. There is no need to try to invent a coordinate system, as one is defined.
2. Pythag doesn't apply. It VERY CLEARLY states that moving diagonally is IDENTICAL IN COST to moving horizontally or vertically. This means that the "distance" of moving from (0,0) to (5,5) is IDENTICAL to moving from (0,0) to (0,5) or (0,0) to (5,0).
3. The ABSOLUTE VALUE of a coordinate is 10^9 (or possibly 109, but I don't think so). There is no constraint as to the distance between houses.
4. The infinite distance that you refer to abve clearly doesn't apply, and there will be a definite solution, because you only need to work out the distance between the houses for the N people. The problem statement does NOT state that there is a house in
every cell of the grid, so there is no need to calculate assuming that there is.
5. Introducing physical world concepts of front and back doors to houses is daft. It is clear from the problem statement that there is no orientation to the house, and that entering it from any direction is allowed, otherwise it would have been stated.
I really don't think that you're helping the OP by applying your own artificial constraints to a fairly well known and common algorithmic homework problem, albeit that the problem has absolutely nothing to do with ASP.NET(!). By announcing (incorrectly)
that the problem statement is unsolvable or incorrect makes it much harder for the OP to tackle the problem and therefore complete their homework, as you're probably making them more, rather than less, confused.
Dave, your brute force method for the O.P. is an over simplification ... it fails when the pseudo random distribution offers multiple solutions, such as my example wthere there will be multiple best solutions ... example, 4 participants, one each, at
(0,0), (9,0), (0,9), and(9,9).
Likewise, 12 participants, one each, at ((0,0), (0,1), (1,0)), ((9,0),
(9,1), (8,0)), ((1,9),
(0,8), (0,9)), and ((9,8),
(8,9), (9,9)).
B-) Please help me by completing my school survey about computer programmers on my website. Thank you!!! Gerry Lowry +1 705-429-7550 wasaga beach, ontario, canada
Hi Dave ... yes, i have read the problem definition many times from which i have concluded that the problem definition is defective because it allows for assumptions.
1. (a) the universe is definition by the O.P. as "an infinite integer grid".
(b) a co-ordinate system is not defined, only hintedat:
"The absolute value of each co-ordinate in the input will be at most 10^9"
{the O.P.'s choice of font size looks like 10_subscript 9;
i'm guessing the O.P. intended 10_superscript 9 ???}
2. Pythagoras could apply, i was giving Pythagorous as an example at to what i perceive as a flaw ...
"eg: (x,y) can be reached from (x-1,y+1) in a single unit of time."
3,6 2 , 7
9 ..........
8 ..........
7 ..o.......
6 ...o......
5 ..........
4 ..........
3 ..........
2 ..........
1 ..........
0 ..........
0123456789
3. the problem definition, by constraining the ABSOLUTE VALUE of a coordinate is
ipso facto constraining the distance.
4. one only needs "to work out the distance between the houses for the N people" BUT N can be
0 to 10000 houses ... i've made no assumption that every cell has a house (although every cell could have a house); from the set of ALL houses, at any given time, we will
never select more that 10000 and those houses must be selected from houses within the
implied distance constraint.
(we also are assuming varible speed because the problem definition speaks about
uniform units of time rather that distance; thus moving diagonally from corner to corner takes the same time even though the Pythagorean distance is greater on the diagonal).
5. "daft" ??? ... maybe ... Dave, please note that this was introduced only to demonstate the weakness of the problem definition ... the problem definer imho should have left out houses and used something like "cell surface" instead.
----
Dave, the O.P.'s problem is looking for a c# solution and could be related to ASP.NET (albeit a stretch) if one is creating a web page to solve such problems.
As a former college teacher, and also as a tutor to university and college students, imho, when a problem is poorly defined, as this one is, the student needs to query the problem definer in order to have a clear problem statement
that may be difficult for the O.P. because the problem was simply found on some web page somewhere on the internet.
N.B.: imho, the problem, as stated by the O.P., is unsolvable.
Would you please share the link to the problem with us?
thnx/gerry
B-) Please help me by completing my school survey about computer programmers on my website. Thank you!!! Gerry Lowry +1 705-429-7550 wasaga beach, ontario, canada
ashok2009cse
Member
173 Points
123 Posts
need solution to this problem in c#- help
Mar 07, 2012 11:13 AM|LINK
hi all,
i came accross thisproblem from one web page, i have tried my best to resolve. i couldn't. i think i am lacking in the logic. can any one solve and tell me the logic with source code..
Problem is:
<div>Meeting Point (50 Points)</div> <div> </div>There is an infinite integer grid at which N people have their houses on. They decide to unite at a common meeting place, which is someone's house.
From any given cell, all 8 adjacent cells are reachable in 1 unit of time.
eg: (x,y) can be reached from (x-1,y+1) in a single unit of time.
Find a common meeting place which minimises the sum of the travel times of all the persons.
Input Format:
N
The following N lines will contain two integers saying the x & y coordinate of the i-th person.
Output Format:
M M = min sum of all travel times;
Constraints:
N <= 10^5
The absolute value of each co-ordinate in the input will be atmost 109
HINT: Please use long long 64-bit integers;
adamturner34
Contributor
4394 Points
1102 Posts
Re: need solution to this problem in c#- help
Mar 07, 2012 02:04 PM|LINK
It's basic math and basic looping.
It would be easier to understand if you drew a grid on a blank peice of paper with a pencil.
For the sake of comprehension, pretend the centermost cell is the closest to all random persons. Now randomly pick other cells and count how many cells they're away from the center cell. Once you understand that, write the code for it.
gerrylowry
All-Star
20577 Points
5721 Posts
Re: need solution to this problem in c#- help
Mar 07, 2012 03:45 PM|LINK
@ ashok2009cse
is this a homework assignment:
probably mathematicians who specialize in graph theory could mentor you; you might have to write the code yourself
it's unsolvable if it's infinite.
no, edge cells can reach fewer houses ... look at a chess board
N.B.: let's use a chess board, home position, as an example,
rowas are 1 to 8; columns are a to h
let's say that both White bishops (c1 and f1) wish to meet with their count parts (c8 and f8) at d4
if your cells are squares of the same size, like the chessboard, then your problem is simple ...
however, since you do not know where the meeting will take place, in pseudo code, your logic would be something like this ...
(a) create an arrary (Int32, Int32) of n by m where n is the total number of cells (64), m are the number of participants
[0, 0] would be the distance for the c1 bishop to a1 (2);
[0, 1] would be the distance for the f1 bishop to a1 (5);
et cetera
b) you'd also need to store your path ... for c1 to a1, the path is c1==>b1==> a1
(c) NOTE: a1 is the White Queen Rook's house ... you said someone's house so according to your problem definition, that someone might not be one of the people who wish to meet.
(d) your problem is simpler if the someone's house must be a home of one of the meeting participants ... for this restricted case, the distance for one participant will always be zero. so you basically would compute the routes from everybody to everybody else ...
note: in the case of the four bishops, any house will do because of the symmetry of their positions on the chessboard.
g.
gerrylowry
All-Star
20577 Points
5721 Posts
Re: need solution to this problem in c#- help
Mar 07, 2012 03:51 PM|LINK
@ ashok2009cse
p.s.: via Google, or your favourite search engine:
graph theory shortest path algorithm
DMW
All-Star
15943 Points
2353 Posts
Re: need solution to this problem in c#- help
Mar 07, 2012 08:19 PM|LINK
Not true. It's only unsolvable if N is infinite.
Again, not true. Because the grid is infinite, there are no edges. The chessboard doesn't help here at all.
For the OP, the exam questioner (or homework assigner, if you like) has made life easier for you, as you can trivially calculate the distance between any two homes as the larger of dX and dY (where dX is the difference in the X coordinates, and dY is the difference in the Y coordinates) due to the fact that the cost of moving diagonally is (artificially) the same as moving horizontally or vertically.
To calculate which is the optimal, simply
Set a variable (call it average distance) to 0.
Loop through all N participants.
For each, calculate the average (Mean, Median or Mode is up to you to think about) distance to all the other houses. If it's less than the variable above, remember it (and remember which house you're currently processing)
Now this is a brute force approach (if you like), so it is clearly inefficient as N tends to large numbers. But it doesn't require you to hold more than one house identifier and two distances in memory at any time, so it's very memory efficient. Unfortunately, gerrylowry's approach cannot work due to the infinite nature of the grid.
Dave
gerrylowry
All-Star
20577 Points
5721 Posts
Re: need solution to this problem in c#- help
Mar 08, 2012 08:23 AM|LINK
@ DMW
the problem statement appears defective ...
the infinite grid may be a red herring.
The constraints are interesting.
N people constrained by N <= 10000 gives N == 0 | 1 | 2 | 3 | ... | 9998 | 9999 | 10000 since we can not have < 0 people.
N == 0 has no solution.
if we only meet at the home of a participant, N == 1 would meet in her/his own home, a distance of zero.a
OTOH, if the meeting home can be any home, given a infinity grid there is no solution ...
from cell c to cell c' is one unit,
from cell c to cell c'' is 2 units,
from cell c to cell c'" is 3 units,
from cell c to cell c'''' is 4 units,
from cell c to cell c''''' is 5 units,
from cell c to cell c'''''' is 6 units, ...
there will always be one cell further away from the previous cell in each of eight directions ...
... no solution Q.E.D.
However, the O.P. stated a second constraint, no co-ordinate's absolute value > 10^9 ... imho, this is a bit of a silly constraint because the problem does not state the co-ordinate system to be used ... so let's invent one of our own:
x is the center of our Flatland-ish universe ...
from x we can move only in 8 directions (assuming our cells are uniform squares) ...
our directions are up, down, left, right, diagonally up left, diagonally up right, diagonally down left, and diagonally down right
this means that we can not always move in a straight line
so, our co-ordinate system much be a direction and a value
if x is at 0, 0, then we could have someone (harry) at 999 999 999 up
if x is at 0, 0, then we could have someone (mary) at 999 999 999 down
now, we have a problem ... (harry) and (mary) each meet the distance constraint (10^9) with x, but fail it with each other.
for simplicity, let's pretend that we have an edge corner, like a1 on the chessboard, and called it 0, 0 ... we can also have 0, 999 999 999 right and 0, 999 999 999 up ... the n,n diagonal would take us from 0, 0 to 999 999 999 diagonally up right, .... because we are measuring distance by cell count, 0, 0 to 999 999 999 up, 0, 0 to 999 999 999 diagonally up right, and 0, 0 to 999 999 999 right ALL seem to be the same distance, however, the diagonal (hypoteneuse) distance is larger (Pythagorous).
(again, keeping it less complex, every house would have to be in the centre of it's cell and every house would have to be the same size ... even that's a problem because the houses would have a front door, back door, and meybe one, even two side doors, but not likely also corner doors for people approaching diagonally).
back to the chessboard for a moment: let''s move the white queen from d1 to a3;
d1, c1, b1, a1, a2, a3 == 5 cells away
d1, c2, b2, a3 == 3cells away
d1, c1, b1, a2, a3 == 4 cells away
of course, if we gave the queen a helicopter, she could fly directly to a3 but we'd have to add in the take off and landing distances because the queen's helicopter would not want to crash into other chess pieces on its way to a3.
i am not a mathemation .... however, it's reasonable to make some assumptions ...
(a) we will have 2 to 9999 houses distributed pseudo randomly in a 999 999 999 x 999 999 999 grid;
(b) we will not visit houses of strangers so we will ignore the houses on non-meeting participants
(c) our 999 999 999 x 999 999 999 grid is one of infinite 999 999 999 x 999 999 999 grids on our infinite super grid
(d) our problem is only solvable within the boundaries of any one or more 999 999 999 x 999 999 999 grids but if and only if we restrict the total number of grids to a finite number.
(e) the house(s) nearest the centre of the grid will not always be the ideal destination (back to the chessboard, the black queen, if on d5 would have to travel towareds a1 if the other meeting participants were on a1, b1, and c2) ... occassionally, a home in the largest cluster of homes may turn out to be the best soulution.
(f) often, there will be multiple best solutions ... example, 4 participants, one each, at (0,0), (9,0), (0,9), and (9,9).
gerrylowry
All-Star
20577 Points
5721 Posts
Re: need solution to this problem in c#- help
Mar 08, 2012 08:40 AM|LINK
@ DMW continuing my reply to you ...
(i) if the grid is infinite, there is no solution
(ii) f the grid is finite, there are edges
(iii) unlike folding our universe*, our grid is and will remain Flatland-ish for this problem
example: http://astronomy.nmsu.edu/geas/lectures/lecture28/slide02.html
"Does the Universe have an Edge?"
i am not a methematician ... so DMW, either there are no edges in our infinite grid or there are infinite edges ...
likely you are correct when you state "Because the grid is infinite, there are no edges".
g.
DMW
All-Star
15943 Points
2353 Posts
Re: need solution to this problem in c#- help
Mar 08, 2012 08:54 AM|LINK
gerry
Have you actually read the problem definition. It is really clear and really precise, and it is definitely solvable.
If you read the problem, you realise that
1. The universe is defined as a square grid of square cells. There is no need to try to invent a coordinate system, as one is defined.
2. Pythag doesn't apply. It VERY CLEARLY states that moving diagonally is IDENTICAL IN COST to moving horizontally or vertically. This means that the "distance" of moving from (0,0) to (5,5) is IDENTICAL to moving from (0,0) to (0,5) or (0,0) to (5,0).
3. The ABSOLUTE VALUE of a coordinate is 10^9 (or possibly 109, but I don't think so). There is no constraint as to the distance between houses.
4. The infinite distance that you refer to abve clearly doesn't apply, and there will be a definite solution, because you only need to work out the distance between the houses for the N people. The problem statement does NOT state that there is a house in every cell of the grid, so there is no need to calculate assuming that there is.
5. Introducing physical world concepts of front and back doors to houses is daft. It is clear from the problem statement that there is no orientation to the house, and that entering it from any direction is allowed, otherwise it would have been stated.
I really don't think that you're helping the OP by applying your own artificial constraints to a fairly well known and common algorithmic homework problem, albeit that the problem has absolutely nothing to do with ASP.NET(!). By announcing (incorrectly) that the problem statement is unsolvable or incorrect makes it much harder for the OP to tackle the problem and therefore complete their homework, as you're probably making them more, rather than less, confused.
Dave
gerrylowry
All-Star
20577 Points
5721 Posts
Re: need solution to this problem in c#- help
Mar 08, 2012 09:08 AM|LINK
@ DMW concluding my reply to you ...
Dave, your brute force method for the O.P. is an over simplification ... it fails when the pseudo random distribution offers multiple solutions, such as my example wthere there will be multiple best solutions ... example, 4 participants, one each, at (0,0), (9,0), (0,9), and (9,9).
Likewise, 12 participants, one each, at ((0,0), (0,1), (1,0)), ((9,0), (9,1), (8,0)), ((1,9), (0,8), (0,9)), and ((9,8), (8,9), (9,9)).
g.
gerrylowry
All-Star
20577 Points
5721 Posts
Re: need solution to this problem in c#- help
Mar 08, 2012 09:50 AM|LINK
@ DMW
Hi Dave ... yes, i have read the problem definition many times from which i have concluded that the problem definition is defective because it allows for assumptions.
1. (a) the universe is definition by the O.P. as "an infinite integer grid".
(b) a co-ordinate system is not defined, only hinted at:
"The absolute value of each co-ordinate in the input will be at most 10^9"
{the O.P.'s choice of font size looks like 10_subscript 9;
i'm guessing the O.P. intended 10_superscript 9 ???}
2. Pythagoras could apply, i was giving Pythagorous as an example at to what i perceive as a flaw ...
"eg: (x,y) can be reached from (x-1,y+1) in a single unit of time." 3,6 2 , 7 9 .......... 8 .......... 7 ..o....... 6 ...o...... 5 .......... 4 .......... 3 .......... 2 .......... 1 .......... 0 .......... 01234567893. the problem definition, by constraining the ABSOLUTE VALUE of a coordinate is ipso facto constraining the distance.
4. one only needs "to work out the distance between the houses for the N people" BUT N can be 0 to 10000 houses ... i've made no assumption that every cell has a house (although every cell could have a house); from the set of ALL houses, at any given time, we will never select more that 10000 and those houses must be selected from houses within the implied distance constraint.
(we also are assuming varible speed because the problem definition speaks about uniform units of time rather that distance; thus moving diagonally from corner to corner takes the same time even though the Pythagorean distance is greater on the diagonal).
5. "daft" ??? ... maybe ... Dave, please note that this was introduced only to demonstate the weakness of the problem definition ... the problem definer imho should have left out houses and used something like "cell surface" instead.
----
Dave, the O.P.'s problem is looking for a c# solution and could be related to ASP.NET (albeit a stretch) if one is creating a web page to solve such problems.
As a former college teacher, and also as a tutor to university and college students, imho, when a problem is poorly defined, as this one is, the student needs to query the problem definer in order to have a clear problem statement
that may be difficult for the O.P. because the problem was simply found on some web page somewhere on the internet.
N.B.: imho, the problem, as stated by the O.P., is unsolvable.
-----
@ ashok2009cse
Would you please share the link to the problem with us?
thnx/gerry