Problem 270

[zwuupeape]

Is this correct:

C(3)= 870
C(4) = 17210

[harryh]

Nope. The numbers you give are too high I'm afraid.

[quilan]

Just double checking my brüte force works:
C(3) = 604
C(4) = 12168

That being said, I'd rather not wait a few hours for that to run on C(30).

[harryh]

Yep! So far, so good

[balakrishnan_v]

Cross-checking on test cases gives a lot of hint which I think is not a good idea!

[TripleM]

I agree.. it seems nowadays every single problem people are trying to get test cases confirmed. Never used to happen, it makes solving the problems so much easier now

[elendiastarman]

I suppose it's to be expected due to the rising general difficulty of the problems. Not to mention their largely original nature...

[zwuupeape]

Perhaps it's true for problems of combinatorial nature. I don't know how examples for lower test cases in any way make this problem easier to solve. If your real program runs for a few minutes and you can debug lower test cases with small numbers, it only makes the problem more comfortable and fun to solve - not easier (I could have waited a few minutes for the real program to run, in that case). There are no patterns in these numbers and I even checked OEIS . So I don't see what's wrong.

[Stache]

In this case, I don't see that the additional test cases really gave anything away. Nonetheless, personally, I'd rather not see it. I'm a huge fan of "If you can't solve it, then you can't solve it!" That principle has occasionally kept me plugging away at a problem that was eluding me...such as this one! In fact, I'm at 100% and I only recently discovered these forums - and now that I know about them, until I solved a problem, I would only look here if I were having trouble interpreting the problem statement...which has actually never happened, since they are so well-crafted.

[TripleM]

I guess it was more that, when I first came across Project Euler, I could get stuck on a problem, and wouldn't know whether it was just a simple bug, or something more complex. I would spend ages debugging it, and finally work it out - was so much more fulfilling once the problem was finally solved. Now the debugging aspect is made 10 times simpler for people by having extra test cases to work with - they instantly know whether it is a trivial bug or something wrong with their core algorithm. But it's probably too late to stop it now that it is becoming the trend every problem.

[zwuupeape]

It's not a trend for every problem. Some problems are crystal clear and there is no point to ask for confirmation, but personally this forum helped me a lot with some questions. First, it gives me motivation to know that I got at least the basics right. Perhaps I give up earlier than you do. Secondly, sometimes it is not completely clear what is even asked and the forum is helpful. The slightly more 'dangerous' type is with problems like Triangle Centers and the one with the Fibonacci that I solved with very slow brute force solutions (few hours) and it was good to know I'm not wasting so much CPU time for nothing .

I don't know... I don't think it really matters. Congratulations for solving it, by the way. This problem is wicked sick... I had an Eureka a few times and was sure I was going to solve it but so far came up with nothing :\

[quilan]

I don't know... I don't think it really matters. Congratulations for solving it, by the way. This problem is wicked sick... I had an Eureka a few times and was sure I was going to solve it but so far came up with nothing :\

Yeah, it's a fun one. Took me three eureka moments: My first trick which was a glorified slightly memo brute force (above) caused memory to overflow extremely shortly on 30. The second attempt was much quicker but still overflowed memory. The third was juuuuust right (ala Goldilocks) and blazes. It was really fun watching how my approach morphed over time. Keep at it, and you know it'll come soon!

[garethrees]

I agree with TripleM and balakrishnan_v—by asking for and getting extra test cases you avoid some of the difficulties of a problem. In the case of problem 270, it's quite a lot of work to get good test cases: C(3) is already too large to reliably compute by hand.

If you need more test cases than the problem gives you, then I think you will get the most satisfaction if you compute them yourself. For problem 270, you could write a brute-force solver by generating all possible subsets of cuts and checking that none of the cuts in the set intersect. This wouldn't be able to compute C(30) in a reasonable amount of time, but it would be able to compute C(3) and C(4), which you could use as test cases for your more efficient solver.

[ffff0]

Good day.

I've build a good algorythm that gave correct answer for 2,3,4 but wrong answer for 30. I don't know what i'm missing and need a little help. Can someone verify this values please:
6 - 4393224
8 - 1467097236

And I've got 1697975438563970965479425532110345896 for 30. Is it too big or too small?

Thanks.

P.S. Have found the bug. All this numbers are too small.