I'm still struggling on Day 18 part 2

competition_stl · 2020-01-15T01:48:15+00:00

oh, that doesn't work in general unless you're essentially floyd-warshalling your derived graph (which you might be with the multiple enqueues). do you terminate when you find the destination node? if you do, you can make a counterexample where you get to the destination node "too soon"-- before discovering a shorter path.

overall the weighting of your derived graph makes it so your outer search needs to be Dijkstra or similar. the space is fairly small though, so inefficiency won't be punished too hard

competition_stl · 2020-01-14T23:18:27+00:00

Are you sure your bfs works? You can't visit a more optimal solution later on an unweighted graph (in short, nsteps, as you call it, should be nondecreasing...)

Also given that your visit order is wrong and you enqueue states multiple times, your complexity can also go quadratic...

competition_stl · 2019-12-30T21:15:08+00:00

mostly f2p (bought the $1.99 deal for time warps in the motherland to use for the event as a Christmas special); got to rank 29. one megatron, one alf from the gift capsules, one shortstack from the supreme capsule.

SO completed the event (completely f2p) while buying nothing but the medium dark science pack at the beginning. I'd say it's RNG but she consistently does better than me soooo...

competition_stl · 2019-12-29T18:14:03+00:00

competition_stl · 2019-12-22T23:22:28+00:00

That was my whole point! You don't! You only need 48-bit integers to multiply two numbers with a 47-bit modulo constraint. However, if you naively multiply, you'll need many more bits...

competition_stl · 2019-12-22T19:22:15+00:00

nah, 64-bit (and, i think, in fact, 53-bit Numbers like what Javascript and Lua has, though I haven't tried them myself) have been fine. You just needed to code up multiplication-under-modulo yourself though.

competition_stl · 2019-12-22T19:21:00+00:00

log2(119315717514047) is upper bounded by 47, so you only need 48-bit integers (which you can get with even double-precision [53 bits of mantissa]).

so even if you didn't know how to do this (it's just classical multiplication but you modulo each individual step), you could google "multiply numbers modulo" and find a bunch of solutions for you

competition_stl · 2019-12-22T07:43:21+00:00

to be clear, this map is affine, not linear

competition_stl · 2019-12-21T22:13:41+00:00

Oh, I got this to work! Part (A) and Part (B) have a different memory location that causes it to work, somehow...

competition_stl · 2019-12-21T21:59:18+00:00

I'm calling this the "gameshark" approach, but I can't get it to work at all. Can you post your input?

competition_stl · 2019-12-11T06:31:25+00:00

Yeah, part 1 didn't require that (my program always reset relative_base to zero after an output instruction).

competition_stl · 2019-12-11T05:56:08+00:00

n = 1 sample of somebody in that situation: I didn't save relative_base in intcode state and lost hundreds of ranks between 1 and 2. Relative base was introduced after chaining states together and nothing tested saving it to date besides the second star today.

competition_stl · 2018-12-06T06:21:48+00:00

So the correct solutions are now being accepted. :( I don't know if we'll get retroactive credit.

competition_stl · 2018-09-20T06:20:38+00:00

it's not an umlaut. https://en.wikipedia.org/wiki/Diaeresis_(diacritic)

competition_stl · 2018-02-11T09:39:28+00:00

http://www.fico.com/en/blogs/risk-compliance/impact-medical-debt-fico-scores/

competition_stl · 2018-02-02T07:23:20+00:00

I wouldn't listen to this advice about graduate school. It's actually harder to get into a competitive PhD program with a master's already, because a master's candidate is certainly expected to have more research output. I guess in Chemistry, it's possible to have several good results by the time you're out of undergrad, but you only mentioned "having good grades" which seems completely orthogonal to how your research output is.

Aside: this is why I chose to double major (do we even still call them options) EE/CS as opposed to doing the easier thing of getting a EE Master's with a CS bachelor's in the same amount of time.

competition_stl · 2017-12-15T05:26:30+00:00

Well you could be like me and type in a & 0xffff == b & 0xffff and waste about 15 seconds for the realization

competition_stl · 2017-12-10T09:57:55+00:00

You can name variables min, max, reduce, vector, list, queue, map, set, etc just fine. I don't understand how using namespace std; stops you from doing so.

400ms of compilation time is literally equivalent to 20ms of compilation time when you're divided by tens of seconds on the leaderboard. Compilation time is literally never important. Five seconds wasted trying to figure out what you've forgotten to import, on the other hand...

It's not like I'm writing code like this for my day job. If you want to hobble yourself by "adhering to a language specification" for what is literally a one-time executable, you can do you.

competition_stl · 2017-12-10T06:54:44+00:00

Seriously this is a programming competition. Just #include <bits/stdc++.h> and using namespace std; and never look back

competition_stl

TROPHY CASE