Problem 728

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
endagorion
Posts: 5
Joined: Mon Nov 21, 2011 9:19 pm

Problem 728

Post by endagorion »

So I would have expected a lot of solves now, also I'm pretty sure my answer is correct. Does the statement have the correct $N$, and system the correct answer?
bobby_eletrica
Posts: 2
Joined: Sun Jul 31, 2016 3:37 pm

Re: Problem 728

Post by bobby_eletrica »

Have you been able to get the right values for their examples??
Under the assumption that exactly k (instead of over k) consecutive coins must be turned each go I calculated (brute force), $F(8,3)=0$, $F(9,3)=384$, $S(3)=12$, $S(10)=7990$.
User avatar
heteroing
Posts: 3
Joined: Thu Sep 10, 2020 10:23 am

Re: Problem 728

Post by heteroing »

A friend and I are also getting correctly matching values for the test values, and the (same) incorrect value for 10^7, using at least three different programs.
Image
User avatar
heteroing
Posts: 3
Joined: Thu Sep 10, 2020 10:23 am

Re: Problem 728

Post by heteroing »

bobby_eletrica wrote: Sun Oct 04, 2020 2:58 am Have you been able to get the right values for their examples??
Under the assumption that exactly k (instead of over k) consecutive coins must be turned each go I calculated (brute force), $F(8,3)=0$, $F(9,3)=384$, $S(3)=12$, $S(10)=7990$.
Also the image included in the problem description clearly shows $F(8, 3) \geq 1$.
Image
bobby_eletrica
Posts: 2
Joined: Sun Jul 31, 2016 3:37 pm

Re: Problem 728

Post by bobby_eletrica »

:lol: :lol: :lol: :lol: :lol: probably you noticed I was counting unsolvable configurations
aleksey
Posts: 7
Joined: Thu Nov 01, 2007 11:19 am

Re: Problem 728

Post by aleksey »

Same problem here, test values match, the result is incorrect.
user202729
Posts: 17
Joined: Tue Dec 29, 2015 2:58 pm

Re: Problem 728

Post by user202729 »

Same problem for me.

(random note: I tried submitting the value of S(10^6), S(10^8), S(2e7), S(5e7) and S(1e7) mod (10^8+7) without success. It's wrong to try random options like this, but at least if it gets accepted I can definitely prove that the result is likely wrong)


Unfortunately, does it mean that the gold medal (first place) for this problem will be meaningless (if the answer is simply updated and multiple people who solved it try to submit it at once)?

Unless Project Euler stores all the incorrect submissions (+their timestamp) for all users, and determine the fastest solver based on that.

jaehyunp
Posts: 1
Joined: Sun Oct 04, 2020 4:10 am

Re: Problem 728

Post by jaehyunp »

I'm also pretty sure that my solution is correct and yet getting wrong answers. I tried a few alternative values but didn't pass: S(1)+S(2)+...+S(10^7), S(11111111), S(12345678), ...
User avatar
utomaya
Posts: 41
Joined: Mon Mar 08, 2010 7:06 am
Location: Okinawa , Japan

Re: Problem 728

Post by utomaya »

same here...

I got S(3)=22, S(10)=10444, and S(1000)=853837042 (mod 10^9+7).
But my result for S(10^7) was rejected.

For such a simple problem, it is strange that there are no solvers til now.
[edit]:
This situation happened before.
http://projecteuler.chat/viewtopic.php? ... 9d0ea9cc27
Image
Mohammad_Ali_B
Posts: 6
Joined: Mon Jan 12, 2015 11:25 pm

Re: Problem 728

Post by Mohammad_Ali_B »

Precisely the same problem here.

I get the correct value for S(3), S(10), S(1000), and I'm sure of my answer for S(10^7).

I too, tried many variations.
I even tried forcing overflows and including common bugs in my code, to see if I could match the wrong answer.
Image
shs.10978
Posts: 3
Joined: Sun Mar 03, 2019 9:33 pm

Re: Problem 728

Post by shs.10978 »

Same here... I was surprised when my answer was not accepted, and even more surprised when no one has got it correct after four hours.
fakesson
Posts: 15
Joined: Thu Jul 12, 2018 1:06 am
Location: New York, NY

Re: Problem 728

Post by fakesson »

Same here. Downloaded the webpage and scripts and tried to see if I could find anything that appears wrong, but it looks the same as for other unsolved problem.
Last edited by fakesson on Tue Oct 06, 2020 9:17 pm, edited 2 times in total.
Image
rkm0959
Posts: 1
Joined: Sun Apr 05, 2020 6:48 pm

Re: Problem 728

Post by rkm0959 »

Darn. I was so excited to get a first solve despite being 3 hours late to the party only to find this out :P
user202729
Posts: 17
Joined: Tue Dec 29, 2015 2:58 pm

Re: Problem 728

Post by user202729 »

fakesson wrote: Sun Oct 04, 2020 6:22 am Downloaded the webpage and scripts and tried to see if I could find anything that appears wrong
Did you know that it's possible to view the HTML source of the problem? https://projecteuler.net/minimal=728

The only thing that "appears wrong" to me is that the last sentence doesn't end with a period.
Find $S(10^7)$. Give your answer modulo $1\,000\,000\,007$
At that time I thought that it's just sloppy writing, I can't imagine that something meaningful can be put after that sentence (in base $16$? Wrapped in quotes? With spaces to separate the thousands? $+1$?)
Mohammad_Ali_B
Posts: 6
Joined: Mon Jan 12, 2015 11:25 pm

Re: Problem 728

Post by Mohammad_Ali_B »

I was also very excited to get a First Solve. Something seemed really off, because honestly, I had implemented $F(n, k)$ quite quickly (it took about 1 minute to figure it out). A fast solution took me about 30 minutes overall.

Anyways, I've tried far too many variations of the inputs for one night. I'm gonna come back in 8 hours hoping that my first "incorrect" submission from about 3 hours ago counted for something :(
Image
User avatar
neverforget
Posts: 38
Joined: Sat Sep 16, 2006 10:10 pm

Re: Problem 728

Post by neverforget »

I also found a solution that works for the test cases but gets WA. For $S(10^8)$ I got something ending in ???, using same modulus. Is it at all possible there is a corner case we all didn't consider that first shows up between $10^3$ and $10^7$?
Last edited by neverforget on Sun Oct 04, 2020 9:47 pm, edited 1 time in total.
Image
Mohammad_Ali_B
Posts: 6
Joined: Mon Jan 12, 2015 11:25 pm

Re: Problem 728

Post by Mohammad_Ali_B »

728 is 222222 in base 3, so I tried submitting the answer in base 3, and this failed. :lol:
Image
philiplu
Posts: 44
Joined: Wed Aug 02, 2017 8:51 pm
Location: Redmond, WA, USA

Re: Problem 728

Post by philiplu »

neverforget wrote: Sun Oct 04, 2020 8:26 am I also found a solution that works for the test cases but gets WA. For $S(10^8)$ I got something ending in ???, using same modulus. Is it at all possible there is a corner case we all didn't consider that first shows up between $10^3$ and $10^7$?
I got the same last 3 digits as you for $S(10^8) \bmod{10^9+7}$ (blocked out in case you remove your value later). Given the simplicity of the formula we probably all found for $F(n,k)$, and the fact that $S(10^3)$ is easy to verify, I'm thinking that, no, we're not missing some weird corner case that only shows up above $10^3$. It's probably a glitch in the submission system, and since it's just now getting on to 9 AM in the UK, presumably Euler or someone else will notice the problem soon.
Image
User avatar
hk
Administrator
Posts: 11258
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: Problem 728

Post by hk »

The answer has been corrected.
Apologies for the inconvenience.
Image
philiplu
Posts: 44
Joined: Wed Aug 02, 2017 8:51 pm
Location: Redmond, WA, USA

Re: Problem 728

Post by philiplu »

Thanks, hk.

So tempting to jump in now and finally get that top 10 Chart Topper award I've never managed, but, nah, it wouldn't feel right. :D

I held out for lucky #13 instead. That's still probably my best showing ever, tainted as it is.
Image
Post Reply