Cheapest Bus Tickets

Back to General discussions forum

gardengnome     2024-08-29 01:32:16
User avatar

I hope your job hunt goes well.

Rodion (admin)     2024-08-29 04:15:12
User avatar

Thanks Mathias - and also for your solution! I was somewhat in doubt whether to add this problem - but I see now it is very educative to me. To start with, in interview the input data were represented differently - I added this to the "notes" on the problem now. With my interviewer we spent perhaps about 35 minutes in total - initially I proposed recursive function with memoization, not outlining it in details though. Interviewer said it looks right but perhaps let's do without recursion for the fear of stack overflow. My solution, when completed, looked like 15-20 lines (the one submitted as testuser has extra loop to convert input array) - and when we run it, there was trouble with going outside of the dp array, I suggested a fix which looked rude (due to lack of ternary operator in Go), interviewer suggested much more elegant, but incorrect one, which we debugged for some time, before I threw it off and implemented my version.

Looking at your 3-lines code, well, you may guess what I feel :)

As about a hunt, it goes bit more queer than previously, but as I routinely change jobs almost yearly, I get used to it. Just checked - about 60 applications since beginning of the August - of them 24 in "rejected" state, 13 in "reviewed", 9 in "not reviewed" and 5 "invited" (to interview). Just 4 interviews with HRs happened, and only one technical - this first from which I brought the task. I said "queer" because year ago the same exactly CV (just year less experience) brought about 4 technical interviews in the period of 2-3 weeks. Anyway:

There is nothing like looking, if you want to find something
(or so Thorin said to the young dwarves).
You certainly usually find something, if you look,
but it is not always quite the something you were after...

I remembered the phrase from reading the book in the age of 7 - and it definitely helps :)

gardengnome     2024-08-29 04:30:31
User avatar

Out of interest, what should the solution be for 2 2 3? I say 27 but it's not entirely clear.

Rodion (admin)     2024-08-29 05:08:59
User avatar

Hm. You have submitted the last version at 0:16 and you are (still? already?) online by 4:30 - I wonder, if you have more than four cats :)

what should the solution be for 2 2 3? I say 27 but it's not entirely clear.

I'm slowpoke probably for I can't immediately see the issue you perceive. We get 27 with one 3-days and one single-trip ticket. We also can buy 2-days ticket and make two trips on simple ones (28 right?) or use two 2-day tickets (36) which is worse than all single-trips (35)... Is there something I miss?

gardengnome     2024-08-29 05:14:32
User avatar

I'm currently on the other side of the world, so it's evening here.

And agree with your cases. The question was about whether 3-day ticket plus extra single ticket is allowed, and that's how I read it. All good.

Rodion (admin)     2024-08-29 06:20:32
User avatar

Now Vladimir is beating records: his solution is almost one-liner, and judging by @cache it is what I meant initially myself (though I won't be able to write it so short for my life).

zelevin     2024-08-29 13:36:18

Thanks for the kind words!

Interestingly enough, my solution got 2 2 3 wrong, so I added a (straightforward) fix to account for cases like that.

nalbe666     2024-08-31 12:56:11
User avatar

Hello. Is this { 2, 2, 4, 2, 2 } some kind of spec case or smth? Similar to above { 2, 3, 2 } ?

gardengnome     2024-08-31 13:06:29
User avatar

Hi,

You and tzyLee (30 minutes earlier) are the only ones who have thought about this special case; most (all?) other solutions do not handle this correctly. This includes my own original solution, and thus I have updated it now. Still thinking how to handle this elgantly with a linear DP though ...

gardengnome     2024-08-31 13:34:45
User avatar

I think we can extend that once further: 3 1 4 2 4 1 3.

nalbe666     2024-08-31 22:43:47
User avatar

Ok. Can you check some data, please?

28
6 7 1 2 0 2 1 3 2 1 1 5 3 6 1 6 1 1 4 2 3 7 3 2 3 3 2 0
my: 214, Expected answer was: 216

31
4 5 3 2 2 1 1 2 1 4 1 2 1 2 3 4 2 3 3 2 7 4 0 4 3 3 2 3 2 3 1
my: 248, Expected answer was: 253

31
0 1 5 4 0 0 5 5 3 3 5 3 2 4 1 6 1 2 2 3 4 5 4 2 4 2 1 2 0 4 4
my: 229, Expected answer was: 221?

gardengnome     2024-09-01 00:20:23
User avatar

I get 216, 253 and 229 which of course might be wrong. Can you work out what tickets you use, for instance in the first case?

nalbe666     2024-09-01 02:17:25
User avatar

I changed something and now:
31
4 5 3 2 2 1 1 2 1 4 1 2 1 2 3 4 2 3 3 2 7 4 0 4 3 3 2 3 2 3 1
my: 238

I ended up with recursion, so it is a pain to retrieve a human-readable backtrack path.
There is a typical solution where you go through the array and choose the best option with a backward lookup.
Here is a slightly more complicated version. Since there may be chains of 3-day tickets, you need to look for them all
(for example, recursively), but at each step of the recursion, you need to check not only the 3-day ones
but all other options as well.

gardengnome     2024-09-01 02:59:18
User avatar

... foo(i - 2, v + a[i - 1] + a[i - 2] - 7) + 22 ... - is the -7 correct?

nalbe666     2024-09-01 04:00:12
User avatar

Yep, my bad. Thanks. Now it looks fine. I test it tomorrow.

Rodion (admin)     2024-09-01 05:11:51
User avatar

most (all?) other solutions do not handle this correctly. ... Still thinking how to handle this elgantly with a linear DP though

I got a bit nervous about the checking code when read this yesterday, but was unable to join. Testuser's solution blatantly reflect's it though regretfully in fancy language.

2 2 3   yields 27
3 1 4 2 4 1 3   yields 66

If these are not correct, checker may need fix too.

gardengnome     2024-09-01 09:58:51
User avatar

Hi Rodion,

What does the checker report for the following test case?

31
0 1 5 4 0 0 5 5 3 3 5 3 2 4 1 6 1 2 2 3 4 5 4 2 4 2 1 2 0 4 4

nalbe666's comment seems to suggest that the expected answer was 221.

Rodion (admin)     2024-09-01 10:30:43
User avatar

It is 229. I think one of the ways to get such a sum is to split mainly into pairs of days:

0 1 | 5 4 | 0 0 | 5 5 | 3 3 | 5 3 | 2 4 | 1 6 | 1 2 2 | 3 4 | 5 4 | 2 4 | 2 1 2 | 0 | 4 4

It will give one ticket for 5, ten for 18 and two for 22 kopecks.

What is the supposed way of getting to 221?

gardengnome     2024-09-01 10:53:25
User avatar

I get 229 as well. Just wanted to check as nalbe666's earlier post said 'expected answer was: 221?'.

Rodion (admin)     2024-09-01 12:07:02
User avatar

Ah, I see now, thanks!

It looks the task conditions are not extremely well balanced and when there are on average more than 3 trips every day, 3-days tickets are rarely needed.

nalbe666     2024-09-01 15:24:09
User avatar

Now my results match yours. It looks like the problem is solved. Thanks everyone.

LilyBottie     2024-10-09 20:55:17

honestly I'm surprised a (sightly optimized) bruteforcer finds the solution in a few seconds (and I'm on a low power machine to).

Rodion (admin)     2024-10-09 21:30:45
User avatar

Witam i dziękuję za informację! I feel a bit too stupid to grasp your idea at once, but it looks like what you call bruteforce is also recursion but with some different way of restricting "branches" to grow too far? Thus it will do more work than recursion with memoization, but still far less than fully "exponentially growing" recursion without restrictions.

LilyBottie     2024-10-09 23:09:36

the rules are actually quite simple:

  1. don't buy more than 3 single use tickets in a single day
    (since its cheaper to then buy an unlimited ticket, I should've used USTKT_RATIO but I forgor)

  2. always use single use tickets when a small amount of trips are needed in a three day timespan
    (inverse of 1. but also applies to three day tickets)

  3. don't buy a three day ticket if we can't use it for three days
    either because the month ends soon or if it would be used up early (again, cheaper to by an unlimited ticket)

  4. always use unlimited tickets when we need to take a lot of trips (>8 in a three day timespan)
    since buying the additional one use tickets would make it more cost efficient to just buy two unlimited tickets

these four rules work for pretty much all cases, except for when there are many days in a row where two trips are needed. buying a there day ticket will always allow for the optimal cost so just go with that

I'm actually not sure if memoization will help tbh, since the tree is quite varied, but I didn't think of that so I'm not sure. I actually originally wrote a bruteforcer to see what the patterns are on smaller scales. Maybe I missed something but from my testing it seemed like to determine what ticket to buy you had to consider the entire month but apparently not? I really struggle with those kind of algorithms haha, though I don't know if those crazy O(n) solutions actually work on all test cases or only on those you can expect from a random sample.

Rodion (admin)     2024-10-10 06:20:01
User avatar

Hi and thanks a lot for explanations!

I see the idea perfectly now - regretfully, as you mentioned in the comments, this won't work well if ticket types/prices are modified.

As about memoization - I think you can check zelevin's solution, but it is probably in the unfamiliar language. So I tried to show it myself based on your own code. Well it almost work :)

It feels I forgot most of my C but the idea is like this - I wrote the recursive function without memoization first (just what you'll get if you remove all lines with the word memo from the code). It will work on small examples, like the one given in the problem statement.

Then what memo does - it simply checks that if we already called this function with the exactly same pair of parameters, we can return result calculated on the previous run (with such parameters) - these results are stored in the memo.

It is a bit complicated because we use recursive function with two parameters instead of one (number of trips already made), but anyway should work in this clumsy implementation. It yields slightly wrong answer on some tests - I think I'm too stupid now to debug, but you may try to figure this out. Anyway it is a simple idea of "expressing DP via recursion".

If you would like some more problems on DP, just click dynamic-programming tag in the problem list (perhaps one of the first is Sweet Harvest). Also problems authored by Clive (csfpython) are often of this kind. It is a trick very popular in programming contests though not very often met in industrial programming.

Please login and solve 5 problems to be able to post at forum