11573 - Ocean Currents

[jurajz]

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!

[kn]

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]

> 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]

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]

> 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

Rio, would you please describe your codes in details?
e.g. the graph representation, STL used, the while loop of Dijkstra...

I wonder why my code has such a long runtime

[Jan]

I think you can avoid heap easily. I avoided stl, and got accepted in .7 seconds.

[kn]

Thanks for your hint!
I finally got it AC in 1.0xx sec.

I use BFS in my final implementation

Complexity : O(1000*1000)

[jurajz]

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]

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]

i cant undrestand this problem
for this case

Code: Select all

Accepted

[doxi]

[doxi]

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]

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