[Community Puzzle] Thomas and the Freight Cars

https://www.codingame.com/training/hard/thomas-and-the-freight-cars

Send your feedback or ask for help here!

Created by @java_coffee_cup,validated by @Djoums,@TeddyS and @icecuber.
If you have any issues, feel free to ping them.

loved it. very satisfying organizational problem. @java_coffee_cup

Hi, is there a way to get the solution if I’m stuck? Thanks!

I can not think of an algorithm to do this. Does anyone have any help? Can I search the internet for something? I love codingame, but sometimes it’s so out there, that I feel like I can’t learn. I don’t want the solution, but ways of thinking.

I’ve tried a few ways, like “if this is bigger or smaller” add it here and so on.
But it seems that my ideas get broken if say 2 in a row don’t make sense.
Or i end up over deleting “good ones” cause something too high or low get’s added. So i’m guessing i need recursion of some sort, to dig deeper, but i don’t know any algorithms or way of thinking to solve this at all.

If the problem had better tags, I would know what to look up to figure out.

This puzzle is hard so it is classified as “Hard”.
Hard puzzles are intended for challenging people more than educating. Hard puzzles are like hot spicy food that people like it just because it burns their tongues heavily.

So, if you really want a hint to spoil the fun of engaging in a critical challenge, go on to click below…

spoiler

It is somehow related to the idea of Longest increasing subsequence

But this puzzle is trickier than that. Direct implementation of the algorithm cannot solve it. You need to thoroughly understand the standard algorithm and modify it to fit for a specific applications.

1 Like

Since all the cars are given in sequential order, a simple approach is to go car by car and compute what you get if you take the car, and if you don’t. With recursion and a good memoization structure it is enough to solve this problem.

1 Like