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

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

Post 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:
Impossible is nothing
Top
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
Contact Krzysztof Duleba

Post 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
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...
Top
Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:
Contact Solaris

Post 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 ??
Where's the "Any" key?
Top
ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post 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
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program
Top
the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:
Contact the LA-Z-BOy

Post 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 ?
Istiaque Ahmed [the LA-Z-BOy]
Top
Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:
Contact Moha

Post 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?
Top
Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:
Contact Moha

Post 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!
Top
the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:
Contact the LA-Z-BOy

Post 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!
Istiaque Ahmed [the LA-Z-BOy]
Top
Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:
Contact Moha

Post 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.
Top
Bunda001
New poster
Posts: 6
Joined: Wed Jan 02, 2008 12:45 pm

Post by Bunda001 »

Hi people, is someone here, who could send here AC program code - i really need it - please... i am hopeless :(
Top
red_apricot
New poster
Posts: 48
Joined: Sun Jun 22, 2014 6:14 am

Re: 10923 - Seven Seas

Post by red_apricot »

One vagueness of the problem: "you move and then the ship moves" --- this constitutes *one* move.
Top
just_yousef
New poster
Posts: 50
Joined: Tue Dec 17, 2013 11:01 pm

Re: 10923 - Seven Seas

Post 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 :)
Top
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10923 - Seven Seas

Post 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.
Check input and AC output for thousands of problems on uDebug!
Top
just_yousef
New poster
Posts: 50
Joined: Tue Dec 17, 2013 11:01 pm

Re: 10923 - Seven Seas

Post 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
Top
Post Reply

Return to “Volume 109 (10900-10999)”