Page 2 of 2

Posted: Mon Feb 06, 2006 1:17 pm
by tywok
Your CE is because sort takes as third parameter a StrictWeakOrdering object. See http://www.sgi.com/tech/stl/sort.html for more info.

In your case you should use something like this

Code: Select all

struct Comparator{
 bool operator()(const GridCond &a, GridCond &b){ 
  if(a<b)return true;
  else return false;
 }
};
and when you call sort, just call it with your comparator

Code: Select all

   sort(gcNext, gcNext+nComb,Comparator());
Right now i'm not sure if it needs the double parenthesis after Comparator in the sort call, but im little tired to try it out :roll:

Posted: Mon Feb 06, 2006 2:28 pm
by Krzysztof Duleba
operator mustn't take reference as the parameter. It should be either const reference or value type. So 33rd line should read

Code: Select all

   bool operator<(const GridCond &ob) const

Posted: Mon Feb 06, 2006 7:24 pm
by Solaris
Krzysztof Duleba wrote:operator mustn't take reference as the parameter. It should be either const reference or value type.
Thank you very much Krzysztof ... CONST keyword is what I was missing. The code runs faster without the sorting though :P
tywok wrote: Your CE is because sort takes as third parameter a StrictWeakOrdering object.
In the same site that u referred u will find the following variation of sort function that I have been trying to use. :)

Code: Select all

template <class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);
Thanks again to Krzysztof and tywok and will anybody who got AC in near zero seconds like to share his / her algo ??

Posted: Thu Jun 15, 2006 1:48 pm
by ayon
why problem description so unclear ?
"A ship is destroyed if it moves to a cell that contais a rock."
again, "If an enemy ship reaches your ship, you are dead", then what will be if my ship move to a rock ?

if my ship can move to a rock, it should be told that "only enemy ship is destroyed if it moves to a cell that contais a rock."
and if my ship cannot move to a rock, it should be told that "If an enemy ship reaches your ship or your ship moves to a rock, you are dead",

please clarify me

Posted: Sun Jun 18, 2006 3:22 pm
by the LA-Z-BOy
A ship is destroyed if it moves to a cell that contais a rock.
Both your ship and the enemy ships are `ships', right ?

Posted: Thu Aug 10, 2006 1:48 pm
by Moha
My code passed all of these testcases, but still WA. the problem statements says that less than 10 moves so 10th move is not correct ok?
can anybody help me?

Posted: Thu Aug 10, 2006 2:16 pm
by Moha
Could anyone test these testcases?

Code: Select all

13

.#......
.#...##.
.#...##.
.#..S##.
.####E#.
......#.
......#.
..#####.
........

S#E.....
........
........
........
........
........
........
........
........

S#######
########
########
########
########
########
########
########
EEEEEEEE

........
........
........
...#....
..#S#...
...E....
........
........
........

........
........
..EEEE..
.E....E.
.E....E.
.E....E.
.E....E.
..#S#...
..#.#...

........
........
........
.E....E.
.E....E.
.E....E.
.E....E.
..#S#...
..#.#...

........
........
........
........
........
........
.E....E.
..#S#...
..#.#...

........
........
........
........
........
.E....E.
.E....E.
..#S#...
..#.#...

........
........
........
........
.E....E.
.E....E.
.E....E.
..#S#...
..#.#...

.#......
.#....#.
.#...##.
.#..S##.
.####E#.
......#.
......#.
..#####.
........

.#......
.#......
.#...##.
.#..S##.
.####E#.
......#.
......#.
..#####.
........

.#......
.#......
.#......
.#..S##.
.####E#.
......#.
......#.
..#####.
........

.#......
.#......
.#......
.#..S...
.####E#.
......#.
......#.
..#####.
........

Code: Select all

I'm the king of the Seven Seas!
I'm the king of the Seven Seas!
I'm the king of the Seven Seas!
I'm the king of the Seven Seas!
Oh no! I'm a dead man!
Oh no! I'm a dead man!
I'm the king of the Seven Seas!
I'm the king of the Seven Seas!
I'm the king of the Seven Seas!
I'm the king of the Seven Seas!
I'm the king of the Seven Seas!
I'm the king of the Seven Seas!
Oh no! I'm a dead man!

Posted: Sat Aug 12, 2006 2:30 pm
by the LA-Z-BOy
My AC program gives

Code: Select all

I'm the king of the Seven Seas!
Oh no! I'm a dead man!
Oh no! I'm a dead man!
I'm the king of the Seven Seas!
I'm the king of the Seven Seas!
I'm the king of the Seven Seas!
I'm the king of the Seven Seas!
I'm the king of the Seven Seas!
I'm the king of the Seven Seas!
I'm the king of the Seven Seas!
I'm the king of the Seven Seas!
I'm the king of the Seven Seas!
Oh no! I'm a dead man!

Posted: Tue Aug 15, 2006 12:02 am
by Moha
I got it at last. I did a very nasty mistake in my dfs function. anyway, this is a very simple problem, so a simple dfs is enough, also I think this problem has so many vagueness because I got it with different answers for the posted testcases, especially for my own testcases.

Posted: Sun Jan 06, 2008 12:06 pm
by Bunda001
Hi people, is someone here, who could send here AC program code - i really need it - please... i am hopeless :(

Re: 10923 - Seven Seas

Posted: Sun Jul 06, 2014 8:14 am
by red_apricot
One vagueness of the problem: "you move and then the ship moves" --- this constitutes *one* move.

Re: 10923 - Seven Seas

Posted: Mon Jul 21, 2014 11:11 am
by just_yousef
I solved this problem with BFS But without the need of a visit array, would it make any difference if used it ??
and how can i use a map with the following key and value:

Code: Select all

struct node{
  int arr[10][10];
}
map<node,bool>vist;
the above code does not work most of the time
thanks :)

Re: 10923 - Seven Seas

Posted: Tue Jul 22, 2014 10:50 pm
by brianfry713
I solved this and got AC in 4 different ways:
DFS no visit set: 0.219 seconds
DFS with set<string> visit: 0.015 seconds
BFS no visit set: 0.342 seconds
BFS with set<string> visit: 0.015 seconds

Adding the visit set speeds up DFS and BFS. In DFS you should not remove a visited state when backtracking. It is not possible to reach the same state with a different number of moves.

You should use a set for visit instead of mapping to a bool. Then you can check if the state is in the set or not.

An array address is really a pointer, so you would need to make sure that the data you are pointing to is not changing. It is easier to use a string or vector and then the data instead of the pointer is pushed into the set.

Re: 10923 - Seven Seas

Posted: Wed Jul 23, 2014 2:20 am
by just_yousef
brianfry713 wrote:I solved this and got AC in 4 different ways:
DFS no visit set: 0.219 seconds
DFS with set<string> visit: 0.549 seconds
BFS no visit set: 0.342 seconds
BFS with set<string> visit: 0.015 seconds

Adding the visit set slows down DFS because it's impossible to reach the same state, however it speeds up BFS.

You should use a set for visit instead of mapping to a bool. Then you can check if the state is in the set or not.

An array address is really a pointer, so you would need to make sure that the data you are pointing to is not changing. It is easier to use a string or vector and then the data instead of the pointer is pushed into the set.
You are totally right :D :D
I changed my 2D array into a 1D vector and used "map<vector<int>,bool>" for the visit and and my timing became 0.016 - 11X times Faster -
Thank you brianfry713