Timus - 1930, Ivan's Car, Why WA

[doctorlai]

http://acm.timus.ru/problem.aspx?space=1&num=1930

I've tried many days for this problem, my solution is using BFS, but keeps getting WA6, any hints?

Code: Select all

class ss
{
   public int id;
   public int depth;
   public int prev;

   public ss(int _id, int _d, int _p)
   {
      this.id = _id;
      this.depth = _d;
      this.prev = _p;
   }
}


   static boolean change(int p, int cur, int next)
   {
      if (p == -1)
      {
         return false;
      }
      return (up(p, cur) != up(cur, next));
   }

   static int search(int a, int b)
   {
      if (a == b)
      {
         return 0;
      }
      Queue q = new LinkedList<ss>();
      q.add(new ss(a, 0, -1));
      Arrays.fill(vis, false);
      vis[a] = true;
      while (q.size() > 0)
      {
         ss k = (ss)q.poll();
         int x = k.id;
         int prev = k.prev;
         for (int i = 0; i < towns[x].size(); i ++)
         {
            int y = (int)towns[x].get(i);
            if (y == b)
            {
               if (change(prev, x, y))
               {
                  return k.depth + 1;
               }
               return k.depth;
            }
            if (!vis[y])
            {
               vis[y] = true;
               if (x == a)
               {
                  q.add(new ss(y, k.depth, x));
               }
               else
               if ((change(prev, x, y)))
               {
                  q.add(new ss(y, k.depth + 1, x));
               }
               else
               {
                  q.add(new ss(y, k.depth, x));
               }
            }
         }
      }
      return 0;
   }

[doctorlai]

It seems to me that my BFS finds the shortest path in terms of roads used (and then returns the number of up/down changes in that path), instead of finding the shortest path in terms of up/down changes.

For example, consider the following:

Code: Select all

a -up-> b -down-> z
|                   ^
up                 |
|                   up
v                   |
c -up->  d  -up-> e

Then the solution of the problem is 0 gear changes, using the path acdez, while the above algorithm returns the path abz with one gear change.

[dfy]

Even though it's a minimal example, it would be kind of cool if you add a small comment saying where you got that example .

Anyways, when I saw your solution, my first idea of a modification to it was to use a priority queue instead of a normal queue. You then always pop the minimal (in terms of cost/depth) element and insert the new neighbours into the automatically sorted priority queue.

This works, but there is one important caveat: You must not mark elements as visited too soon. It's too early to mark them when you find them as a neighbour of the current node. (Why?) It's okay to mark them as visited as soon as you pop them from the stack, thereby guaranteeing minimality.

Then I realized that the priority queue is actually overkill, it is sufficient to maintain two standard queues (I'm actually using lists in my implementation) because there are always only two different depths in the queues anyways! This speeds up everythin quite a bit.

My current code is C++, Timus accepts it in 0.312secs with 4.6MB of memory - let me know if you're interested in it, I could post it on here if you want.

[doctorzlai]

Thanks...great hint..
I will keep trying.

[doctorlai]

using PriorityQueue, Crash at Test 6....

Any hints?

[doctorlai]

finally got accepted in Java!
0.265s and use Memory 12 480 KB

all I need is to add a Comparator

Code: Select all

class ssc implements Comparator<ss>
{
    @Override
    public int compare(ss x, ss y)
    {
      if (x.depth < y.depth)
      {
         return -1;
      }
      if (x.depth == y.depth)
      {
         return 0;
      }
      return 1;
    }
}

http://acm.timus.ru/status.aspx?space=1&num=1930&author=46914

[dfy]

Well done!

I'm tinkering with my input/output at the moment. The C routines (scanf/printf) seem to be so much faster than the C++ stream functions (cin, cout), switching makes my "Anansi's Cobweb" program 3x faster. I have to try that with "Ivan's Car" as well and see what's going to happen...

[doctorzlai]

yes, that is why your C++ code is slow,
the cin/cout takes too much time if there are large input to process.