11157 - Dynamic Frog
Moderator: Board moderators
11157 - Dynamic Frog
Can some one give me a hint as to how I should solve the problem.
In a DP approach,
I see that if we try to denote the state space as every visited "Small Rock" and in the worst case there are 100 small rocks, the algorithm will never run in time.
Is there some greedy algorithm that is possible to solve this problem?
Thank you
Deepesh
In a DP approach,
I see that if we try to denote the state space as every visited "Small Rock" and in the worst case there are 100 small rocks, the algorithm will never run in time.
Is there some greedy algorithm that is possible to solve this problem?
Thank you
Deepesh
I understand that small rocks are the once to be considered, between 2 big rocks, and from the starting point to first big rock and ending point to last rock.
So there should be two distinct set of small stones through which we should be able to reach from any big rock/destination. (going from start to destination is exactly identical to going from start to destination twice.)
I also know that length of the jump is the parameter on which binary search is to be done.
What I am unable to prove is that the first time we go from one end to other, how do we prove that picking the small stones which are farthest away is the best choice. I feel that this is optimal, but I am unable to prove.
I understand that picking the farthest stones will result in minimum number of small rocks being exhausted. Also that when ever there is a big rock reachable, jump on that.
So there should be two distinct set of small stones through which we should be able to reach from any big rock/destination. (going from start to destination is exactly identical to going from start to destination twice.)
I also know that length of the jump is the parameter on which binary search is to be done.
What I am unable to prove is that the first time we go from one end to other, how do we prove that picking the small stones which are farthest away is the best choice. I feel that this is optimal, but I am unable to prove.
I understand that picking the farthest stones will result in minimum number of small rocks being exhausted. Also that when ever there is a big rock reachable, jump on that.
I understand that picking the farthest stones will result in minimum number of small rocks being exhausted. Also that when ever there is a big rock reachable, jump on that.
I felt exactly the same during the contest. So I just decided to rely on my intuition, coded it and it got AC after the first submission. I don't think that looking for formal proofs during a contest is always the best ideaI feel that this is optimal, but I am unable to prove.

After I am done with my stupid philosophy homework assignement on
the issues of "The equal opportunities in the modern world" (due tomorrow!!!) I might look for some kind of a formal proof...
Thank you Sohel!
I got your point and now I do like the problem even more! The BS + flow
approach is indeed a solution that is guaranteed to work. I feel that I
am close to a kind of a formal "proof" of the BS + greedy approach.
Would you mind if I send you tomorrow my solution with some comments
as a private message?
I am so sorry to postpone till tomorrow, but I am still working on my
philosophy homework. It's so hard to prove that in Euclidean geometry
no triangle exists with a sum of angles of 180 degrees!
By the way it was an excellent problem set as a whole!
I got your point and now I do like the problem even more! The BS + flow
approach is indeed a solution that is guaranteed to work. I feel that I
am close to a kind of a formal "proof" of the BS + greedy approach.
Would you mind if I send you tomorrow my solution with some comments
as a private message?
I am so sorry to postpone till tomorrow, but I am still working on my
philosophy homework. It's so hard to prove that in Euclidean geometry
no triangle exists with a sum of angles of 180 degrees!

By the way it was an excellent problem set as a whole!
I am newbie in C++, so would you tell me please how could I read input for this problem? I usedsohel wrote:Nice to know you liked the problem!!
I was also thinking of a (binary search + greedy) solution but wasn't too sure about it. I basically wrote the judge solution with (binary search + network flow).
Can you share your greedy approach?
Code: Select all
for (int i = 1; i <= n; i++) {
while (1) {
scanf("%c", &ch);
if (ch == 'B' || ch == 'S')
break;
}
rt[i] = ch;
scanf("-%d", &dist[i]);
}
per aspera ad astra
Code: Select all
for (int i = 1; i <= n; i++) {
scanf("%s", str);
rt[i] = str[0];
sscanf(str+2, "%d", &dist[i] );
}

Am I the only one here who used DP (complexity O(n^3)) ? I find the problem very similar to the 'round-trip trough canada'-problem, for those who know what I mean. Basically the idea is as follows.
A solution is a set of two paths from one side to the other that have no small rocks in common. We're going to construct both paths simultaniously, so the state is the pair consisting of the position of the first path and the position of the second path. We start with both paths on the left side and then iterate over all states. In a state we can advance the path who's current position is leftmost. It can always jump to all positions after the position of the other path and if the other path is not on a small rock, it can also jump to the same position as the other path. If we let the cost of a state be the distance of the longest jump, the final value of the state with both paths on the right hand side will be our final answer.
Probably this can be optimized to O(n^2) or even more, but it was fast enough to give me AC during the contest.
A solution is a set of two paths from one side to the other that have no small rocks in common. We're going to construct both paths simultaniously, so the state is the pair consisting of the position of the first path and the position of the second path. We start with both paths on the left side and then iterate over all states. In a state we can advance the path who's current position is leftmost. It can always jump to all positions after the position of the other path and if the other path is not on a small rock, it can also jump to the same position as the other path. If we let the cost of a state be the distance of the longest jump, the final value of the state with both paths on the right hand side will be our final answer.
Probably this can be optimized to O(n^2) or even more, but it was fast enough to give me AC during the contest.
I also did DP (with the same state space as you), but it ended up being just one recursive call for each state (move the leftmost position one step if possible, otherwise two steps), so calling it DP feels kind of silly in my case.krijger wrote:Am I the only one here who used DP (complexity O(n^3)) ? I find the problem very similar to the 'round-trip trough canada'-problem, for those who know what I mean. Basically the idea is as follows.
Regarding reading the input, here's another way of doing it:
Code: Select all
for (int i = 1; i <= N; ++i) {
scanf(" %1s-%d", s, &pos[i]);
small[i] = s[0] == 'S';
}
I used a greedy algortihm (without binary seartch), and its not hard to proof it.
The problem is how to jump the consecutive small rocks ( >= 0 ) between two big rocks,because there is no reason for jumping over the big rocks. I gived a strategy to the frog how to jump these small rocks, and the maximum length jump needed will be the answer for these consecutive small rocks.
----
Sory for my poor English.
The problem is how to jump the consecutive small rocks ( >= 0 ) between two big rocks,because there is no reason for jumping over the big rocks. I gived a strategy to the frog how to jump these small rocks, and the maximum length jump needed will be the answer for these consecutive small rocks.
----
Sory for my poor English.
Hi, I used exactly the same algorithm.rio wrote:The problem is how to jump the consecutive small rocks ( >= 0 ) between two big rocks,because there is no reason for jumping over the big rocks. I gived a strategy to the frog how to jump these small rocks, and the maximum length jump needed will be the answer for these consecutive small rocks.

And I say again that our algorithm proves also the correctness of the "binary search + greedy" method mentioned by some other members.