## 11573 - Ocean Currents

Moderator: Board moderators

jurajz
Learning poster
Posts: 69
Joined: Sat Sep 02, 2006 7:30 pm
Location: Slovakia

### 11573 - Ocean Currents

During the contest, I tried solve it with Dijkstra with binary heap -> TLE.

Then I had better idea, using combination BFS and DFS in this way:

Initially, in queue1 is only starting point and result =0 and visited[rs,cs]=true (all another points visited[r,c]=false)

Then, repeat this steps while visited[rd,cd]=false:

1. For all points in queue1 run DFS (respecting flow of the lake) and give all this unvisited points to queue2
2. If visited[rd,cd]=true then end this loop and write result
3. queue3 = queue1+queue2
4. Increase result and for all points from queue3 give all unvisited points neighbouring to points from queue3 to queue4
5. queue1 := queue4

This is still TLE. I think, that this algorithm runs in O(n*m) for one test case, O(k*n*m) for k test cases. imho it should pass time limit 3 seconds for maximal value of variables (k=50, n=m=1000). But I am wrong.

Have someone better idea to pass the time limit?

kn
New poster
Posts: 28
Joined: Fri Apr 13, 2007 8:53 am

### Re: 11573 - Ocean Currents

What heap did you use?
Heap of (Dist, x, y) ?

I use Heap of (Dist, z) (using C++ STL - priority_queue)
where z is encoded by x and y
and got accepted in 2.9xx -_-

I tried using Heap of (Dist, x, y) and got TLE for several attempts.

Hope it helps.

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

### Re: 11573 - Ocean Currents

> junrajz
I used the same algorithm as you described. It got accepted in 0.65 s without any optimization.
Maybe some flaw in your code.

-----
Rio

jurajz
Learning poster
Posts: 69
Joined: Sat Sep 02, 2006 7:30 pm
Location: Slovakia

### Re: 11573 - Ocean Currents

>kn

I used Heap of (Dist, z). But not in C++ STL, I used "homemade" Heap and in Pascal. Maybe I have more complicated representation of graph.

>rio

Now I know, that my idea was OK. I try to see my code, maybe here are some flaws (wasting of time or infinite loop).

kn
New poster
Posts: 28
Joined: Fri Apr 13, 2007 8:53 am

### Re: 11573 - Ocean Currents

rio wrote:> junrajz
I used the same algorithm as you described. It got accepted in 0.65 s without any optimization.
Maybe some flaw in your code.

-----
Rio
e.g. the graph representation, STL used, the while loop of Dijkstra...

I wonder why my code has such a long runtime

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

### Re: 11573 - Ocean Currents

I think you can avoid heap easily. I avoided stl, and got accepted in .7 seconds.
Ami ekhono shopno dekhi...
HomePage

kn
New poster
Posts: 28
Joined: Fri Apr 13, 2007 8:53 am

### Re: 11573 - Ocean Currents

I finally got it AC in 1.0xx sec.

I use BFS in my final implementation

Complexity : O(1000*1000)

jurajz
Learning poster
Posts: 69
Joined: Sat Sep 02, 2006 7:30 pm
Location: Slovakia

### Re: 11573 - Ocean Currents

Thanks one more time, finally I have AC.

By random-generated test cases I noticed really stupid mistake in my code - in my BFS I wrote "false" instead of "true" and that means, that I don't marked squares added to queue4 as visited. After this, I have WA, after fixing have AC in 1.060.

jurajz
Learning poster
Posts: 69
Joined: Sat Sep 02, 2006 7:30 pm
Location: Slovakia

### Re: 11573 - Ocean Currents

Here are my random-testcases, when someone have WA, this may help:

Input:

Code: Select all

``````10 10
6051134354
2321601626
4333237711
7100435246
1073373445
7444061776
7570714166
2261637531
6527302645
2035001421
50
2 3 4 1
8 7 8 6
8 2 10 7
2 5 8 5
2 1 3 1
10 3 6 6
10 6 2 4
10 8 4 5
3 1 5 5
1 4 4 5
10 8 9 7
5 8 3 7
10 8 7 8
2 8 2 9
2 2 10 2
5 5 7 2
8 10 7 3
6 5 3 5
1 10 2 1
1 6 2 10
10 1 7 9
2 2 1 2
5 1 10 9
8 4 1 2
2 6 8 6
5 4 9 8
9 7 4 6
9 10 3 5
6 7 5 4
10 8 10 7
7 10 8 5
8 7 4 6
8 10 5 6
2 5 2 6
6 3 2 4
4 3 3 8
1 1 1 8
4 4 3 1
1 9 7 4
7 8 2 5
9 5 4 9
3 4 7 3
1 6 6 7
3 6 7 7
2 9 10 7
6 3 1 8
9 9 5 6
1 2 6 2
9 4 5 2
8 8 2 7
``````
Output from my AC program:

Code: Select all

``````2
1
3
3
1
3
3
3
1
1
1
2
3
0
3
2
4
2
5
0
4
1
3
3
3
2
2
4
2
1
2
1
2
1
2
2
3
2
2
3
2
2
2
1
5
3
3
3
2
3
``````

vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

### Re: 11573 - Ocean Currents

i cant undrestand this problem
for this case

Code: Select all

``````Accepted
``````
Last edited by vahid sanei on Tue Dec 29, 2009 9:42 am, edited 1 time in total.
Impossible says I`m possible

doxi
New poster
Posts: 2
Joined: Tue May 26, 2009 3:38 am

### Re: 11573 - Ocean Currents

doxi
New poster
Posts: 2
Joined: Tue May 26, 2009 3:38 am

### Re: 11573 - Ocean Currents

I just used BFS + priority_queue
7153693 11573 Ocean Currents Accepted C++ 1.112
but I think it's not very good ,
but I got TLE at

http://acm.jlu.edu.cn/joj/showproblem.php?pid=2558

look this massage : The input contains several test cases so My program is not very good .....

used another

7153702 11573 Ocean Currents Accepted C++ 0.376

and get ac now

U can visit map[x][y] just one time

first wolk to the place where there need no energy and then 1 energy ..... and so on ....

just a bfs /..

prashantharshi
New poster
Posts: 22
Joined: Wed May 21, 2014 10:16 am

### Re: 11573 - Ocean Currents

i used dijkstra with heap
u can also use c++ stl priority queue
here is my AC code
http://ideone.com/EO771i