11573  Ocean Currents
Moderator: Board moderators
11573  Ocean Currents
I have question about this problem.
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?
Thanks in advance!
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?
Thanks in advance!
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.
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.
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
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
Re: 11573  Ocean Currents
kn and rio, thank you for your answers.
>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
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).
Re: 11573  Ocean Currents
Rio, would you please describe your codes in details?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
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
HomePage
Re: 11573  Ocean Currents
Thanks for your hint!
I finally got it AC in 1.0xx sec.
I use BFS in my final implementation
Complexity : O(1000*1000)
I finally got it AC in 1.0xx sec.
I use BFS in my final implementation
Complexity : O(1000*1000)
Re: 11573  Ocean Currents
Thanks one more time, finally I have AC.
By randomgenerated 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.
By randomgenerated 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.
Re: 11573  Ocean Currents
Here are my randomtestcases, when someone have WA, this may help:
Input:
Output from my AC program:
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
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
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
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 /..
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 /..

 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
u can also use c++ stl priority queue
here is my AC code
http://ideone.com/EO771i