<< problem 243 - Resilience | Prime Subset Sums - problem 249 >> |

# Problem 247: Squares under a hyperbola

(see projecteuler.net/problem=247)

Consider the region constrained by 1 <= x and 0 <= y <= 1/x.

Let S_1 be the largest square that can fit under the curve.

Let S_2 be the largest square that fits in the remaining area, and so on.

Let the index of Sn be the pair (left, below) indicating the number of squares to the left of S_n and the number of squares below S_n.

The diagram shows some such squares labelled by number.

S_2 has one square to its left and none below, so the index of S_2 is (1,0).

It can be seen that the index of S_32 is (1,1) as is the index of S_50.

50 is the largest n for which the index of S_n is (1,1).

What is the largest n for which the index of S_n is (3,3)?

# My Algorithm

Each square has a lower-left corner (x_0,y_0) and an upper-right corner (x_1,y_1) such that:

(1) x_1 - x_0 = y_1 - y_0 = side (length of each side of that square)

The hyperbola y = 1/x must go through the upper-right corner:

(2) y_1 = dfrac{1}{x_1}

Substituting (2) in (1):

(3) x_1 - x_0 = dfrac{1}{x_1} - y_0

And solve for x_1:

(4) x_1 - dfrac{1}{x_1} = x_0 - y_0

(5) dfrac{x^2_1 - 1}{x_1} = x_0 - y_0

(6) x^2_1 - 1 = x_1 (x_0 - y_0)

(7) 0 = x^2_1 - x_1 (x_0 - y_0) - 1

(8) 0 = x^2_1 + x_1 (y_0 - x_0) - 1

That's a quadratic equation with parameters:

(9) p = y_0 - x_0, q = -1

(10) x = -frac{p}{2} \pm sqrt{(frac{p}{2})^2 - q}

Omitting the second solution:

(11) x_1 = -frac{y_0 - x_0}{2} + sqrt{(frac{y_0 - x_0}{2})^2 + 1}

(12) x_1 = frac{x_0 - y_0}{2} + frac{1}{2} sqrt{(x_0 - y_0)^2 + 4}

(13) x_1 = 0.5 * (x_0 - y_0 + sqrt{(x_0 - y_0)^2 + 4})

Therefore the length of a side in (1) becomes:

(14) side = x_1 - x_0

(15) side = 0.5 * (x_0 - y_0 + sqrt{(x_0 - y_0)^2 + 4}) - x_0

And a bit simplified:

(16) side = 0.5 * (-x_0 - y_0 + sqrt{(x_0 - y_0)^2 + 4})

(17) side = 0.5 * (sqrt{(x_0 - y_0)^2 + 4} - x_0 - y_0)

That formula can be found in `Square::setSideLength`

.

My program starts with a single square whose lower-left corner (x, y) is at (1, 0).

All squares are stored in an `std::set`

named `todo`

which is sorted descendingly by the square's size

(the overloaded `Square::operator<`

returns the "wrong" result on purpose because an `std::set`

is sorted ascendingly by default).

I always pick the largest (→ the first) square from `todo`

and replace it by its upper and right neighbor.

Each square's position (x, y) and index (left, below) are tracked.

In order to have a square at index (3, 3) I have to have a square at (2, 3) or (3, 2).

Generalized, only if some squares are in `todo`

where left <= 3 and below <= 3 and left + below < 3+3 then it's

still possible to generate a square at index (3, 3).

`candidates`

counts how many squares fulfil that condition. If `candidates`

becomes zero then no more squares can be at (3,3).

The most recent will be printed.

# Interactive test

You can submit your own input to my program and it will be instantly processed at my server:

This is equivalent to`echo "1 1" | ./247`

Output:

*Note:* the original problem's input `3 3`

__cannot__ be entered

because just copying results is a soft skill reserved for idiots.

*(this interactive test is still under development, computations will be aborted after one second)*

# My code

… was written in C++11 and can be compiled with G++, Clang++, Visual C++. You can download it, too.

#include <iostream>
#include <set>
#include <cmath>
// a square is described by its lower left corner (x,y) and its index along x and y axis

struct Square
{
Square(double x_, double y_, unsigned int left_, unsigned int below_)
: x(x_), y(y_), left(left_), below(below_)
{
setSideLength();
}
// lower-left corner
double x;
double y;
// number of squares on the left side
unsigned int left;
// number of squares below
unsigned int below;
// length of a side
double side;
// note: sort in reverse, therefore return true if it's the larger (!) value
bool operator<(const Square& other) const
{
return side > other.side;
}
private:
// find length of edges of the largest square whose lower-left corner is at x,y
void setSideLength()
{
// see my explanations above
side = 0.5 * (sqrt((x - y) * (x - y) + 4) - x - y);
}
};
int main()
{
unsigned int indexLeft = 3;
unsigned int indexBelow = 3;
std::cin >> indexLeft >> indexBelow;
// square's number
unsigned int result = 0;
// create first square with lower-left corner at (1,0) and no other squares on its left or bottom side
std::set<Square> todo = { Square(1, 0, 0, 0) };
unsigned int candidates = 1; // => the first square is left of and below all other squares
while (candidates > 0)
{
result++;
// pick first (= largest) square
auto current = *(todo.begin());
// and remove it
todo.erase(todo.begin());
// create a new square on top of the current square
Square top (current.x, current.y + current.side,
current.left, current.below + 1);
todo.insert(top);
// and a square on the right side
Square right(current.x + current.side, current.y,
current.left + 1, current.below);
todo.insert(right);
// count how many squares could be on the left or bottom side of a square with index (3, 3)
if (top .left <= indexLeft && top .below <= indexBelow)
candidates++;
if (right .left <= indexLeft && right .below <= indexBelow)
candidates++;
if (current.left <= indexLeft && current.below <= indexBelow)
candidates--;
}
// show ID of last square with index (3, 3)
std::cout << result << std::endl;
return 0;
}

This solution contains 12 empty lines, 16 comments and 3 preprocessor commands.

# Benchmark

The correct solution to the original Project Euler problem was found in 0.19 seconds on a Intel® Core™ i7-2600K CPU @ 3.40GHz.

Peak memory usage was about 25 MByte.

(compiled for x86_64 / Linux, GCC flags: `-O3 -march=native -fno-exceptions -fno-rtti -std=c++11 -DORIGINAL`

)

See here for a comparison of all solutions.

**Note:** interactive tests run on a weaker (=slower) computer. Some interactive tests are compiled without `-DORIGINAL`

.

# Changelog

August 14, 2017 submitted solution

August 14, 2017 added comments

# Difficulty

Project Euler ranks this problem at **65%** (out of 100%).

# Links

projecteuler.net/thread=247 - **the** best forum on the subject (*note:* you have to submit the correct solution first)

# Heatmap

*Please click on a problem's number to open my solution to that problem:*

green | solutions solve the original Project Euler problem and have a perfect score of 100% at Hackerrank, too | |

yellow | solutions score less than 100% at Hackerrank (but still solve the original problem easily) | |

gray | problems are already solved but I haven't published my solution yet | |

blue | solutions are relevant for Project Euler only: there wasn't a Hackerrank version of it (at the time I solved it) or it differed too much | |

orange | problems are solved but exceed the time limit of one minute or the memory limit of 256 MByte | |

red | problems are not solved yet but I wrote a simulation to approximate the result or verified at least the given example - usually I sketched a few ideas, too |

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |

26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 |

51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 |

76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 |

101 | 102 | 103 | 104 | 105 | 106 | 107 | 108 | 109 | 110 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | 121 | 122 | 123 | 124 | 125 |

126 | 127 | 128 | 129 | 130 | 131 | 132 | 133 | 134 | 135 | 136 | 137 | 138 | 139 | 140 | 141 | 142 | 143 | 144 | 145 | 146 | 147 | 148 | 149 | 150 |

151 | 152 | 153 | 154 | 155 | 156 | 157 | 158 | 159 | 160 | 161 | 162 | 163 | 164 | 165 | 166 | 167 | 168 | 169 | 170 | 171 | 172 | 173 | 174 | 175 |

176 | 177 | 178 | 179 | 180 | 181 | 182 | 183 | 184 | 185 | 186 | 187 | 188 | 189 | 190 | 191 | 192 | 193 | 194 | 195 | 196 | 197 | 198 | 199 | 200 |

201 | 202 | 203 | 204 | 205 | 206 | 207 | 208 | 209 | 210 | 211 | 212 | 213 | 214 | 215 | 216 | 217 | 218 | 219 | 220 | 221 | 222 | 223 | 224 | 225 |

226 | 227 | 228 | 229 | 230 | 231 | 232 | 233 | 234 | 235 | 236 | 237 | 238 | 239 | 240 | 241 | 242 | 243 | 244 | 245 | 246 | 247 | 248 | 249 | 250 |

251 | 252 | 253 | 254 | 255 | 256 | 257 | 258 | 259 | 260 | 261 | 262 | 263 | 264 | 265 | 266 | 267 | 268 | 269 | 270 | 271 | 272 | 273 | 274 | 275 |

276 | 277 | 278 | 279 | 280 | 281 | 282 | 283 | 284 | 285 | 286 | 287 | 288 | 289 | 290 | 291 | 292 | 293 | 294 | 295 | 296 | 297 | 298 | 299 | 300 |

301 | 302 | 303 | 304 | 305 | 306 | 307 | 308 | 309 | 310 | 311 | 312 | 313 | 314 | 315 | 316 | 317 | 318 | 319 | 320 | 321 | 322 | 323 | 324 | 325 |

326 | 327 | 328 | 329 | 330 | 331 | 332 | 333 | 334 | 335 | 336 | 337 | 338 | 339 | 340 | 341 | 342 | 343 | 344 | 345 | 346 | 347 | 348 | 349 | 350 |

351 | 352 | 353 | 354 | 355 | 356 | 357 | 358 | 359 | 360 | 361 | 362 | 363 | 364 | 365 | 366 | 367 | 368 | 369 | 370 | 371 | 372 | 373 | 374 | 375 |

376 | 377 | 378 | 379 | 380 | 381 | 382 | 383 | 384 | 385 | 386 | 387 | 388 | 389 | 390 | 391 | 392 | 393 | 394 | 395 | 396 | 397 | 398 | 399 | 400 |

401 | 402 | 403 | 404 | 405 | 406 | 407 | 408 | 409 | 410 | 411 | 412 | 413 | 414 | 415 | 416 | 417 | 418 | 419 | 420 | 421 | 422 | 423 | 424 | 425 |

426 | 427 | 428 | 429 | 430 | 431 | 432 | 433 | 434 | 435 | 436 | 437 | 438 | 439 | 440 | 441 | 442 | 443 | 444 | 445 | 446 | 447 | 448 | 449 | 450 |

451 | 452 | 453 | 454 | 455 | 456 | 457 | 458 | 459 | 460 | 461 | 462 | 463 | 464 | 465 | 466 | 467 | 468 | 469 | 470 | 471 | 472 | 473 | 474 | 475 |

476 | 477 | 478 | 479 | 480 | 481 | 482 | 483 | 484 | 485 | 486 | 487 | 488 | 489 | 490 | 491 | 492 | 493 | 494 | 495 | 496 | 497 | 498 | 499 | 500 |

501 | 502 | 503 | 504 | 505 | 506 | 507 | 508 | 509 | 510 | 511 | 512 | 513 | 514 | 515 | 516 | 517 | 518 | 519 | 520 | 521 | 522 | 523 | 524 | 525 |

526 | 527 | 528 | 529 | 530 | 531 | 532 | 533 | 534 | 535 | 536 | 537 | 538 | 539 | 540 | 541 | 542 | 543 | 544 | 545 | 546 | 547 | 548 | 549 | 550 |

551 | 552 | 553 | 554 | 555 | 556 | 557 | 558 | 559 | 560 | 561 | 562 | 563 | 564 | 565 | 566 | 567 | 568 | 569 | 570 | 571 | 572 | 573 | 574 | 575 |

I scored 13,386 points (out of 15600 possible points, top rank was 17 out of ≈60000 in August 2017) at Hackerrank's Project Euler+.

My username at Project Euler is

**stephanbrumme**while it's stbrumme at Hackerrank.

Look at my progress and performance pages to get more details.

# Copyright

I hope you enjoy my code and learn something - or give me feedback how I can improve my solutions.

All of my solutions can be used for any purpose and I am in no way liable for any damages caused.

You can even remove my name and claim it's yours. But then you shall burn in hell.

The problems and most of the problems' images were created by Project Euler.

Thanks for all their endless effort !!!

<< problem 243 - Resilience | Prime Subset Sums - problem 249 >> |