[gcj] Round 1B 2020 Expogo - WA For Test Set 3

[Bob Shepard]

I've been looking at other submissions and even ran 100 random coordinates 
between (-10^9, -10^9) and (10^9, 10^9), but I get the same results as 
those that passed.  I'm not sure why my solution got a WA for test set 3, 
maybe I'm missing an edge case.  I think what I did is similar to what the 
analysis shows and some of the solutions that I've seen.  I think the only 
difference is I worked my way backwards from the target coordinate to (0, 
0) and reverse the string.

Here's the code that I submitted:

#include <algorithm>
#include <cmath>
#include <functional>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>

int main()
{
  int testCaseCount = 0;
  std::cin >> testCaseCount;

  for ( int t = 0; t < testCaseCount; ++t )
  {
    int x_goal = 0;
    int y_goal = 0;

    std::cin >> x_goal >> y_goal;

    auto IsValidCoord = []( int x, int y )
    {
      return ( std::abs( x ) % 2 ) != ( std::abs( y ) % 2 );
    };

    bool possible = IsValidCoord( x_goal, y_goal );
    std::string solution;

    if ( possible )
    {
      int total_distance = std::abs( x_goal ) + std::abs( y_goal );
      int min_jumps = std::ceil( std::log( total_distance + 1.0 ) / 
std::log( 2.0 ) );

      std::vector<int> jumps;
      for ( int i = 0; i < min_jumps; ++i )
      {
        jumps.push_back( 1 << i );
      }

      int current_x = x_goal;
      int current_y = y_goal;

      for ( ; !jumps.empty(); )
      {
        // Last move must be in E/W direction
        if ( std::abs( current_x ) > std::abs( current_y ) )
        {
          if ( current_x > 0 )
          {
            solution.insert( solution.begin(), 'E' );
            current_x -= jumps.back();
          }
          else
          {
            solution.insert( solution.begin(), 'W' );
            current_x += jumps.back();
          }
        }

        // Last move must be in N/S direction
        else
        {
          if ( current_y > 0 )
          {
            solution.insert( solution.begin(), 'N' );
            current_y -= jumps.back();
          }
          else
          {
            solution.insert( solution.begin(), 'S' );
            current_y += jumps.back();
          }
        }

        jumps.pop_back();
      }
    }

    std::cout << "Case #" << t + 1 << ": " << ( possible ? solution : 
"IMPOSSIBLE" ) << "\n";
  }

  return 0;
}


Any Ideas?

-- 
You received this message because you are subscribed to the Google Groups 
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/google-code/72bafa04-3238-4e0a-9ff5-0997ffe82e7d%40googlegroups.com.