algorithm problem in C++

• (2 Pages)
• 1
• 2

18 Replies - 525 Views - Last Post: 15 October 2019 - 01:36 PMRate Topic: 3 Votes //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=417540&amp;s=73981ab0291b6bdfcc2ceeba082e9ad5&md5check=' + ipb.vars['secure_hash'], cur_rating: 2, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

#16 baavgai

• Dreaming Coder

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

Re: algorithm problem in C++

Posted 15 October 2019 - 02:47 AM

Skydiver, 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

```

#17 Skydiver

• Code herder

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

Re: algorithm problem in C++

Posted 15 October 2019 - 04:04 AM

baavgai, 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.

#18 baavgai

• Dreaming Coder

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

Re: algorithm problem in C++

Posted 15 October 2019 - 08:50 AM

Skydiver, 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.

#19 Skydiver

• Code herder

Reputation: 7135
• 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.