11573 - Ocean Currents

All about problems in Volume 115. 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
jurajz
Learning poster
Posts: 69
Joined: Sat Sep 02, 2006 7:30 pm
Location: Slovakia

11573 - Ocean Currents

Post by jurajz » Sun Feb 15, 2009 10:49 am

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
New poster
Posts: 28
Joined: Fri Apr 13, 2007 8:53 am

Re: 11573 - Ocean Currents

Post by kn » Sun Feb 15, 2009 1:45 pm

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.

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

Re: 11573 - Ocean Currents

Post by rio » Sun Feb 15, 2009 2:20 pm

> 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

Post by jurajz » Sun Feb 15, 2009 2:28 pm

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
New poster
Posts: 28
Joined: Fri Apr 13, 2007 8:53 am

Re: 11573 - Ocean Currents

Post by kn » Sun Feb 15, 2009 2:48 pm

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
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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 11573 - Ocean Currents

Post by Jan » Sun Feb 15, 2009 6:09 pm

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

Post by kn » Sun Feb 15, 2009 9:49 pm

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
Learning poster
Posts: 69
Joined: Sat Sep 02, 2006 7:30 pm
Location: Slovakia

Re: 11573 - Ocean Currents

Post by jurajz » Sun Feb 15, 2009 11:40 pm

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

Post by jurajz » Sun Feb 15, 2009 11:46 pm

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

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

Re: 11573 - Ocean Currents

Post by vahid sanei » Thu Mar 19, 2009 5:47 pm

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

Post by doxi » Tue May 26, 2009 4:01 am

:D

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

Re: 11573 - Ocean Currents

Post by doxi » Tue May 26, 2009 4:07 am

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

Post by prashantharshi » Mon Jun 16, 2014 10:12 pm

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

Post Reply

Return to “Volume 115 (11500-11599)”