Radewoosh's blog

I've completed Project Euler
By Radewoosh, 13 months ago, In English

It was a beautiful journey full of internet digging, searching for patterns, learning stuff, fighting with formulas on paper, making crazy observations, coming up with brilliant ideas, implementing crazy optimizations, waiting for the programs to finish, suffering when something was wrong, and so on (and each of the mentioned not once not twice took multiple hours).

It's been a couple of months since I was left with the last unsolved problem and finally I did it! I didn't give up and I obtained the answer alone, without anyone's help, like in the rest of the problems (I was using only internet sources created before the publication of the problem). I'm writing this blog because I am bursting with joy and I wanted to share it with the community. I highly recommend PE as most of the problems were definitely very high quality (and some were a real pain in the ass, but they still teach how to overcome stuff that you're uncomfortable with).

Here's a little souvenir for me:

PS I still have no clue how to do anything useful with continued fractions.

  • Vote: I like it
  • +1099
  • Vote: I do not like it

Comments Comments (64)
| Write comment?
»
13 months ago, # |
  Vote: I like it +36 Vote: I do not like it

Wow!

PS. Could you solve problem H from https://codeforces.net/contest/1666 ?

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    I don't get if it's a sarcasm or what xd That's true that the blog has the vibe of bragging, sorry for that, I just wanted to share my happiness that it's over. I'm not insane yet and I don't think that I can solve everything or smth.

    → Reply
    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it +69 Vote: I do not like it

      Sorry, I didn't want it to look sarcastic, it is really cool to solve all PE problems!

      The problem in the link is where you potentially could do something useful with continued fractions :)

      → Reply
      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it +36 Vote: I do not like it

        Oh, ok, sorry, I was totally lost with your message. I might give your problem a try :P

        → Reply
      • »
        »
        »
        »
        13 months ago, # ^ |
        ← Rev. 2   Vote: I like it +109 Vote: I do not like it

        It's the curse of written word in the Internet that with the lack of facial expressions and intonation it is sometimes hard to understand the intended message properly. I guess that everybody of us went through that a few times that we didn't get a sarcasm or a joke in the Internet and were made fun of cause of that, so we are naturally suspecting some traps even where there aren't any :p

        → Reply
        • »
          »
          »
          »
          »
          13 months ago, # ^ |
            Vote: I like it +18 Vote: I do not like it

          I read some theory in linguistics that emojis (and stuff like "lol" ":p" "xD") is a substitution of facial expression in text! So we should use more :)

          → Reply
»
13 months ago, # |
  Vote: I like it +45 Vote: I do not like it

One thing you could do with continued fractions is to use them in order to run Dijkstra on rational weighted graph in near-linear time. Here you go! https://arxiv.org/abs/2311.03321

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I was thinking about solving Pell's equations or stuff like that, but the paper is nice anyway.

    → Reply
    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it +34 Vote: I do not like it

      Wait, how and why were you solving Pell's equations without continued fractions? :smiling_face_with_tear:

      → Reply
      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it +18 Vote: I do not like it

        Reading this everytime and crying. Maybe I've used them a few times in a way which required no/minimum of understanding.

        → Reply
»
13 months ago, # |
  Vote: I like it +19 Vote: I do not like it

Congrats Radewoosh!

→ Reply
»
13 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Radewoosh orz!

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Congratz!

What was your favourite problem?

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    I don't know of Radewoosh's favorite problem, but it truly blows my mind that the process described in https://projecteuler.net/problem=566 always ends. It has to be one of my fav and most legendary problems for me even though I made 0% progress towards solving it

    → Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hard to say, so many of them were so good. I don't remember them all so well, but looking at the list I remember 499 as a one with strong "wow, that's so cool" effect.

    → Reply
»
13 months ago, # |
  Vote: I like it +27 Vote: I do not like it

That's very impressive, congratulations!

→ Reply
»
13 months ago, # |
  Vote: I like it +18 Vote: I do not like it

gg wp

→ Reply
»
13 months ago, # |
  Vote: I like it +141 Vote: I do not like it

Ok, fine, I will start doing Project Euler

→ Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it -22 Vote: I do not like it

congratulations!<3
-also may i ask, is it useful for cp? or should i do something else instead? i mean is it the best usage of time?
-what is the things i should know before start?

→ Reply
  • »
    »
    13 months ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    I solved approx 100 project euler problems and so far i can't say its an efficient way to learn CP. It's way more oriented towards interesting and fun (to me at least) mathematics stuff.

    If you are looking towards 100% completion of a problem set that brings you progress for CP, I find CSES great. It's great at least until "advanced techniques" and "additional problems" which I didn't do yet si I can't say.

    What I really liked about CSES is that it cover most of the essential topics and for each topic, the problem are mostly climbing in difficulty which each problem. It's a perfect introduction to the multiple classes of problems before you face them in contest.

    → Reply
    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      okay this is really helpful, thanks a lot

      → Reply
    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Hmm. I'm pretty curious to know why its getting downvoted.

      Maybe you find that project euler is an efficient way to improve your CP (for people below master)? or maybe you find CSES isn't a great problemset ?

      Really curious to hear a bit more than downvotes on this one, if someone can take the time :)

      → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Congrats man!
Can you help me with a question im stuck on?

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Congrats, great achievement!

Do you have any favorite problems?

→ Reply
»
13 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Radewoosh orz!

→ Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it


→ Reply
»
13 months ago, # |
  Vote: I like it +42 Vote: I do not like it

Eyy, nicely done, congrats!

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This is cool! How helpful do you think solving Project Euler problems is for solving problems in Codeforces contests or other programming contests?

→ Reply
»
13 months ago, # |
  Vote: I like it +77 Vote: I do not like it

What was the last problem?

→ Reply
»
13 months ago, # |
  Vote: I like it +35 Vote: I do not like it

How many years did it take you to complete them all? Also congratulations, that is no small achievement.

→ Reply
»
13 months ago, # |
  Vote: I like it +20 Vote: I do not like it

Wow, very cool!

→ Reply
»
13 months ago, # |
  Vote: I like it +38 Vote: I do not like it

waiting for the programs to finish

So now that you've solved every problem(and can access every problem's discussion page), can you tell us if the "one-minute rule" is real?

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it +41 Vote: I do not like it

    You can definitely do every problem within one minute runtime, but:

    • lots of people (perhaps the majority) don't care about it, and you see posts like "finally my solution is finished in 69 days on my 420 cores". Occasionally that skews the solver numbers and fastest solves table significantly.
    • in rare cases (maybe 5%) it takes unreasonable and uninteresting optimizations to achieve. Still most of the time it's a nice hurdle to reach for, and you can learn a lot more if you try to do it the right way.
    → Reply
»
13 months ago, # |
  Vote: I like it +36 Vote: I do not like it

Congrats, Radewoosh!!!

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Bro really took "Gotta Catch 'Em All" too seriously

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Legendary! Congrats!

→ Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

Congratulations Radewoosh! Which topic would you say appealed the most to you among all Project Euler problems, in terms of problem statements and solutions, possibly separately? Separately because my experience with PE has been that there are some problems that look benign but end up being really cool and some that are the complete opposite of this description, so I was wondering whether this is true for others too, especially someone who has solved all problems.

→ Reply
  • »
    »
    13 months ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    I'm not him, but I will share some of my favourite: 851 (see top solvers), 591 (cool theory) and 677.

    Edit: I have 580 solved

    → Reply
»
13 months ago, # |
  Vote: I like it -18 Vote: I do not like it

Will it help me improve my CP skills?

→ Reply
»
13 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Highest rated on Codeforces currently, and now AKed PE. Congrats Radewoosh, you're having quite an year!

→ Reply
»
11 months ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

Hey,

Congrats on the achievement !!

What are some of the resources that you used to refer to revisit math concepts while solving or when stuck on a problem ?

→ Reply
»
10 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Grats!

→ Reply
»
9 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Congrats! If one is to start Euler project what book resources would you recommend to have a chance to solve most of them? I bet I mean book positions from combinatorics, geometry, number theory, game theory, ... ? What set of skills is crucial to solve the most difficult ones?

Thanks a lot in advance for your tips and recommendations. Cheers, Pawel

→ Reply
»
5 months ago, # |
  Vote: I like it +124 Vote: I do not like it

I've completed Project Euler, too.

I had ~4 problems left at the time of this blog post, feeling like I would need many more years, but then I was really motivated by your completion. Congratulations and thank you!

→ Reply
  • »
    »
    5 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    the fact that there are problems that take months for LGMs is scary

    → Reply
    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it -20 Vote: I do not like it

      i don't think you need to know what quasi-modular forms or dirichlet's stuff are in order to be LGM, but you'd definitely need to in order to be level 30+ in projecteuler

      → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Do you guys usually solve PE problems using python or c++? which one do you think is more convenient?

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I usually use C++ just because I'm more familiar with it. I would say Python is more convenient since it has a lot of useful libraries to deal with big integer, high decision floating number, etc. Anw, I only have 123 problems solved for now so I can't speak for the harder problems.

    → Reply
»
2 months ago, # |
← Rev. 2   Vote: I like it +12 Vote: I do not like it

I have now solved half of the problemset; this was my long-term goal.
Solving the full problem set is definitely beyond my range.

Spoiler
→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Please don't be offended by my stupidity but are we supposed to solve it manually by pen-paper or by writing code?

    → Reply
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Code.
      In fact, they claim every problem can be solved with a program that takes less than a minute on a modestly powered computer.

      → Reply
»
2 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Hi Radewoosh, Congratulations on that achievement! Can you please share what resources you used in case you got stuck? I am on level 4 there.

→ Reply