11157 - Dynamic Frog

[deepesh]

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

[Ivan]

I personally did a binary search over the length of the longest jump
combined with a kind of greedy.
It would be interesting to here from Sohel did he consider some kind of
DP solution as a working one in the given time limits?
Nice problem, Sohel!

[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.

[Ivan]

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 feel that this is optimal, but I am unable to prove.

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 idea
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...

[sohel]

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?

[tobby]

I get AC with a completely intuitive O(N) algorithm. I get that algorithm by drawing some small cases on paper and studying them. I haven't tried to prove rigorously if that algorithm is indeed correct, but the idea of proof is quite clear.

[Ivan]

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!

[deepesh]

I just coded what I felt and my code has got accepted on the first submission. Will just code from next time based on the idea.

[tobby]

I have thought deeper and I see that the correctness of my O(N) algorithm implies the correctness of your methods with binary search, and probably most working greedy algorithms.

[artie]

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?

I am newbie in C++, so would you tell me please how could I read input for this problem? I used

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]);    
    }    

but think it's too ugly

[sohel]

Code: Select all

      for (int i = 1; i <= n; i++) { 
          scanf("%s", str);
          rt[i] = str[0];
          sscanf(str+2, "%d", &dist[i] );
     }

A quicker approach.

[krijger]

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.

[Per]

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.

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.

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';
  }

[rio]

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.

[tobby]

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.

Hi, I used exactly the same algorithm.

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