10923 - Seven Seas

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

tywok
New poster
Posts: 32
Joined: Sun Oct 30, 2005 2:22 am

Post by tywok » Mon Feb 06, 2006 1:17 pm

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:
Impossible is nothing

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Mon Feb 06, 2006 2:28 pm

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
For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:

Post by Solaris » Mon Feb 06, 2006 7:24 pm

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 ??
Where's the "Any" key?

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » Thu Jun 15, 2006 1:48 pm

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
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

User avatar
the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

Post by the LA-Z-BOy » Sun Jun 18, 2006 3:22 pm

A ship is destroyed if it moves to a cell that contais a rock.
Both your ship and the enemy ships are `ships', right ?
Istiaque Ahmed [the LA-Z-BOy]

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Post by Moha » Thu Aug 10, 2006 1:48 pm

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?

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Post by Moha » Thu Aug 10, 2006 2:16 pm

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!

User avatar
the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

Post by the LA-Z-BOy » Sat Aug 12, 2006 2:30 pm

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!
Istiaque Ahmed [the LA-Z-BOy]

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Post by Moha » Tue Aug 15, 2006 12:02 am

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.

Bunda001
New poster
Posts: 6
Joined: Wed Jan 02, 2008 12:45 pm

Post by Bunda001 » Sun Jan 06, 2008 12:06 pm

Hi people, is someone here, who could send here AC program code - i really need it - please... i am hopeless :(

red_apricot
New poster
Posts: 48
Joined: Sun Jun 22, 2014 6:14 am

Re: 10923 - Seven Seas

Post by red_apricot » Sun Jul 06, 2014 8:14 am

One vagueness of the problem: "you move and then the ship moves" --- this constitutes *one* move.

just_yousef
New poster
Posts: 50
Joined: Tue Dec 17, 2013 11:01 pm

Re: 10923 - Seven Seas

Post by just_yousef » Mon Jul 21, 2014 11:11 am

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 :)

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10923 - Seven Seas

Post by brianfry713 » Tue Jul 22, 2014 10:50 pm

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.
Check input and AC output for thousands of problems on uDebug!

just_yousef
New poster
Posts: 50
Joined: Tue Dec 17, 2013 11:01 pm

Re: 10923 - Seven Seas

Post by just_yousef » Wed Jul 23, 2014 2:20 am

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

Post Reply

Return to “Volume 109 (10900-10999)”