algorithm problem in C++

  • (2 Pages)
  • +
  • 1
  • 2

18 Replies - 525 Views - Last Post: 15 October 2019 - 01:36 PM Rate Topic: **--- 3 Votes

#16 baavgai   User is offline

  • Dreaming Coder
  • member icon


Reputation: 7501
  • View blog
  • Posts: 15,544
  • Joined: 16-October 07

Re: algorithm problem in C++

Posted 15 October 2019 - 02:47 AM

View PostSkydiver, on 13 October 2019 - 01:51 PM, said:

but it's hard to satisfy the 1 second time limit when f: 700000000, r:700000000, c:700000000.


Dammit. You made me do this bloody thing.

There's a simple trick to it: you need only solve for one week. Which is to say, each full week will eliminate 3a, 2b, 2c.

So, if you want play along at home:
int bestDay(int a, int b, int c);
int targetWeek(int &a, int &b, int &c);

void test(int a, int b, int c, int testAnswer) {
    std::cout << a << ','<< b << ','<< c;
    int week = targetWeek(a, b, c);
    std::cout << " => week: " << week << ", new abc: " << a << ','<< b << ','<< c;
    int n = bestDay(a,b,c);
    int answer = week * 7 + n;
    std::cout << " bestDay: " << n << " : " << testAnswer << " == " << answer;
    std::cout << std::endl;
}

int main() {
    test(2,1,1, 4);
    test(3,2,2, 7);
    test(1,100,1, 3);
    test(30,20,10, 39);
    test(700000000,700000000,700000000, 0);
    return 0;
}



Results:
2,1,1 => week: 0, new abc: 2,1,1 bestDay: 4 : 4 == 4
3,2,2 => week: 1, new abc: 0,0,0 bestDay: 0 : 7 == 7
1,100,1 => week: 0, new abc: 1,100,1 bestDay: 3 : 3 == 3
30,20,10 => week: 5, new abc: 15,10,0 bestDay: 4 : 39 == 39
700000000,700000000,700000000 => week: 233333333, new abc: 1,233333334,233333334 bestDay: 5 : 0 == 1633333336


Was This Post Helpful? 0
  • +
  • -

#17 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 7135
  • View blog
  • Posts: 24,239
  • Joined: 05-May 12

Re: algorithm problem in C++

Posted 15 October 2019 - 04:04 AM

View Postbaavgai, on 15 October 2019 - 05:47 AM, said:

Dammit. You made me do this bloody thing.

int bestDay( ... );
:



Best. Day. Ever! :-)

Yes. I ended up doing the division trick after posting, but I was left trying to see if there was also an algebraic way to solve to the remainders. Or if not an algebraic way, some kind of lookup table. The best I could do was build the lookup table on the first query, and just do lookups after that point onwards. I'm not sure of this it technically amortized O(1) or not.
Was This Post Helpful? 0
  • +
  • -

#18 baavgai   User is offline

  • Dreaming Coder
  • member icon


Reputation: 7501
  • View blog
  • Posts: 15,544
  • Joined: 16-October 07

Re: algorithm problem in C++

Posted 15 October 2019 - 08:50 AM

View PostSkydiver, on 15 October 2019 - 06:04 AM, said:

The best I could do was build the lookup table on the first query

Yeah, I actually generated a lookup table based on a 6-bit int. It can be a constant time lookup, as you could just pop it in an array. I couldn't really derive anything more clever than that. I was never a fan of the big O thing; real world implementation often doesn't seem close enough to ideal to justify it.


Curiously, I ended up doing the table generation in Javascript... you never know when another language will come in handy.
Was This Post Helpful? 0
  • +
  • -

#19 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 7135
  • View blog
  • Posts: 24,239
  • Joined: 05-May 12

Re: algorithm problem in C++

Posted 15 October 2019 - 01:36 PM

And the OP did ask for this in C++, I think it will also be possible to use template metaprogramming to generate the lookup table at compile time. But who has time for that? :-)

Better to just do it the easy way with the Javascript and paste it in.
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2