Hi Bob!
The WA is, in part, related to the limits of the problem (-10^9 to 10^9)
and variable types. The limits for Test Set 3 are overflowing the ints in
the program. We have to use long long for cases as large as these. However,
after switching up all the necessary types, I still see a WA. The
calculations for total_distance and min_jumps seem fine, even with the new
types. I'll let you know if I think of anything else.
Best,
Matt
On Tuesday, April 21, 2020 at 4:50:39 PM UTC-4, Bob Shepard wrote:
>
> 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 [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/955b6650-f197-405e-b08f-8c572ddee996%40googlegroups.com.
