11157 - Dynamic Frog

All about problems in Volume 111. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

deepesh
New poster
Posts: 13
Joined: Sat Dec 23, 2006 5:57 am

11157 - Dynamic Frog

Post by deepesh » Sun Jan 21, 2007 8:43 am

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
New poster
Posts: 35
Joined: Thu Dec 29, 2005 1:00 pm
Location: Sofia, Bulgaria

Post by Ivan » Sun Jan 21, 2007 9:31 am

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
New poster
Posts: 13
Joined: Sat Dec 23, 2006 5:57 am

Post by deepesh » Sun Jan 21, 2007 10:06 am

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
New poster
Posts: 35
Joined: Thu Dec 29, 2005 1:00 pm
Location: Sofia, Bulgaria

Post by Ivan » Sun Jan 21, 2007 10:42 am

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

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Sun Jan 21, 2007 7:11 pm

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
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm

Post by tobby » Sun Jan 21, 2007 7:32 pm

I get AC with a completely intuitive O(N) algorithm. :D 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
New poster
Posts: 35
Joined: Thu Dec 29, 2005 1:00 pm
Location: Sofia, Bulgaria

Post by Ivan » Sun Jan 21, 2007 8:09 pm

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
New poster
Posts: 13
Joined: Sat Dec 23, 2006 5:57 am

Post by deepesh » Sun Jan 21, 2007 9:07 pm

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
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm

Post by tobby » Mon Jan 22, 2007 8:36 am

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
New poster
Posts: 8
Joined: Sun Dec 31, 2006 11:56 am
Location: Russia

Post by artie » Wed Jan 24, 2007 3:10 am

sohel 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?
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
per aspera ad astra

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Wed Jan 24, 2007 6:39 am

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
New poster
Posts: 39
Joined: Wed Jul 21, 2004 12:35 am

Post by krijger » Wed Jan 24, 2007 5:42 pm

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
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Wed Jan 24, 2007 10:06 pm

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

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

Post by rio » Thu Jan 25, 2007 8:45 am

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
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm

Post by tobby » Thu Jan 25, 2007 12:27 pm

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.
Hi, I used exactly the same algorithm. :wink:

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

Post Reply

Return to “Volume 111 (11100-11199)”