https://cses.fi/problemset/task/2072/
Treap is the intended solution to this task, but I didn't know treap well enough to write it on the spot. I did however know skiplist (which imo is less complicated) and so I ended up implementing this goofball:
...tags: programming cses
https://cses.fi/problemset/task/2416/
I had been kinda stuck on this for a while, mostly because I was trying to use some weird segtree bash.
...tags: programming cses
Continuation of my previous post about pattern-matching.
Previously, I explained how to use a depth-first-search of a trie to compute pattern-matchings in a set of strings. However, explicit trie used too much memory for the specific task I was trying to apply it on. (64 megabyte limit)
So I took some advice from Alternet and made the trie implicit - rather than even storing intermediate nodes, the entropy of the strings being stored in the trie was low enough that storing each query individually and sorting it took up less memory than a trie. Then this sorted array could be "dfsed" with divide-and-conquer.
...tags: programming
Hey yall. Been a while.
I 'discovered' an interesting way to pattern-match certain types of strings today. Extended writeup on Codeforces
Enjoy!
tags: programming
Recall that the Floyd-Warshall algorithm computes shortest paths between every pair of nodes. It does so by repeatedly "combining" paths into longer ones: Given three distinct nodes a, b, c form the new path a -> c from the two paths a -> b, b -> c and check if it is an improvement.
How does this "arise" from matrix exponentiation?
...tags: programming
It's been a decent while since I did one of these. Speed still seems to be ok.
Solves:
tags: programming atcoder contest-logs
This post is protected by encryption. Unlock
FGouHpgtkAaTc9eSWB9Xvn15fzXBEmeVHeC0Mlz2IaFSMFfFsaH44HGO5Gc+9hWC1s+EGgxJhH/Wi6IhNQFRZA==
1BBb+QMvnTIAzvw5Uld43lx8rkKTzR+WW8bgIUJN+L0=
Solved CSES Coin Collector - first time working with SCC!
but ya tarjan is cool :D
...tags: programming
This post is protected by encryption. Unlock
e8URR5thE7IdPweCFoFlAoQhc+Z+tnTIONC/N9VR/Kg=
Encryption is done via AES. The password used above is a good password, enjoy!
tags: programming starship-dev
"This ARC also serves as a qualification round to select the 18 contestants for the Japanese national finals, making it significantly more difficult than a regular ARC. Due to circumstances, we replaced the tasks and changed the point values. Since there are no easy tasks, the difficulty level of solving one or more tasks has increased. Please be careful. Since the difficulty level is flat, we recommend reading all the tasks and not necessarily solving them in order."
pov i forget to read this and consequently spend the entire contest on A (and fail to solve)
...tags: programming atcoder
This problem is from today's atcoder beginner contest
You are given a list A of lowercase English strings.
For each string S in A, solve the following problem:
You can perform two operations to S:
- Delete the last character of S (if it is non-empty)
- Add any lowercase character to the end of S
Find the minimum number of operations to convert S into
either the empty string or a string that comes before it in A.
This kind of screams trie...
tags: programming atcoder contest-logs
Took Atcoder Regular Contest 185 this morning. I had done one ARC virtual in the past, but that one had relatively more 'normal' questions than today's contest. I think it went alright? I don't really have a sense of scale with ARC yet.
...tags: programming atcoder contest-logs
I should put more effort into these surely...
tags: programming atcoder contest-logs
Woke up 10 min before contest, slow start but wow.. good contest I think
...tags: programming atcoder contest-logs
Actually very similar problem to IOI11p2 (Race) which I did last weekend, using centroid decomposition and then naive dp. Decided to write this one in C*, which was surprisingly easy.
...tags: programming cses
vced ARC 058 w/ jasonwei
C was theoretically easy, construct from smallest digit, etc. but I messed up overflow case [twice] and that whole mess took like 30m total
D was fun combo, pathfinding nonsense that partition & track crossings kind of deleted
E was some DP that I failed, also managed to forget that complementary counting existed.. smh
didn't have anything substantial on F besides "knapsack" so ya
mid contest, definitely need to work on dp
tags: programming atcoder contest-logs
Easier contest (by nature of its age) but still pretty fun. Due to schedule I started around 3 pm and therefore ended at 8, on both days, so didn't have much time to writeup each day separately.
...tags: programming ioi contest-logs
terrible perf lol. should I take the upcoming AGC? idk.
tags: programming atcoder contest-logs
Took the contest 2 days ago but was pretty busy yesterday (with some discrete math project skull) so doing writeup rn in school lmao
...tags: programming ioi contest-logs
Virtualed IOI14d1 yesterday. Due to time (18:30 - 23:30) I didn't feel like writing up last night, so I'm just doing this while bored at school :p
...tags: programming ioi contest-logs
Today, I was working on some 3d matrix projection stuff for some simulation, and needed a simple sin() approximation. Because I was writing this in a non-compileime CBAS segment, I didn't have access to <math.h>, and was too lazy to add builtin trig functions. That's when I remembered: calc has a pretty simple way to approximate complicated functions with polynomials!
Even better, I didn't need an approximation that would work over all input values of theta - only between -pi/2 and pi/2, so a taylor series to three terms did the trick:
...tags: programming math
Decent contest. Started 6 min late bc I lost track of time while debugging some cses problem :/ but it was fine..
ABC were basically trivial, C had a pretty simple pattern (provable by optimal-choice argument) which I got relatively quickly. D was an adventure, though.
Task essentially asks us to determine in a 2d bitfield the...
tags: programming atcoder contest-logs
@ the halfway point
it only gets harder...
tags: programming cses
I did the ABC today: https://atcoder.jp/contests/abc369
The fumbling started on problem A, where I misread the input format and consequently got 2 WA (don't worry why this caused 2 WA and not 1). Then I did a dumb thing...
tags: programming atcoder contest-logs
I finally stopped procrastinating on upsolving IOI18 day 1 p2 today.. lol
The implementation of this problem was some 2d grid swap updates that update a segtree... overall just a massive pain to deal with
I started writing up (for specifically subtask 5, which enforced that the grid was a line) my solution this morning, building off of the stuff I had from the virtual. Then I kinda got distracted with some cses problems and...
tags: programming ioi
Up until about now I've been using the binlift from this cf blog, which is linear in space and build complexity, but has a higher constant factor. This has really never been useful to me, and it's a little more complicated to write, too..
tags: programming codeforces
Completed the second half of IOI18. Performance was kinda eh, but wasn't expecting much :clown:
Solved Combo. Essentially the construction I found was to guess the next 2 bits in the sequence over the course of two queries: there were 3^2 = 9 possible arrangements of next bits, and each query had three possible return values, which worked out to a...
tags: programming ioi contest-logs
I was attempting some afternoon funsies for most of today, which I basically totally bricked.
Here is a hopefully not too scuffed breakdown. (would say it has spoilers, but I barely solved any of the actually interesting problems so nah)
...tags: programming ioi contest-logs
While helping out a friend on some CSES exponentiation problem, I came up with this humorous way to compute fast exponentiate:
So you see, the standard way to go about this sort of problem is to use binary exponentiation. But sometimes when there is a log based solution, there is a somewhat similar sqrt solution.
...tags: programming
Hey yall. Been a while :P
My schedule has been kinda strange ever since coming back from road trip - firstly I started a project with some friends over that trip, SARA, which took up a decent portion of my first few days back. Then I had to deal with some school related stuff, and got involved with a new project after that... and all in all I haven't had had as much time to work on contest recently, or update this blog.
Finally decided to allocate a block of time to updating blog, so here we are! (hence the title)
Also, now that most of the projects I've been working on are at reasonably complete stages, I can talk a bit about them here! This is a short overview of what I've been up to recently:
...tags: programming life
Finished up ccc '17 s5, which I failed to get in yesterday's practice contest. Ended up using sqrt bucketing, which I've never used before.
...tags: programming ccc
I very recently finished this USACO gold question, and my friend was interested in my (mildly scuffed) binary lifting approach. Here it is, I guess :P
...tags: programming usaco
Simulated this contest today - here are my notes and solutions!
...tags: programming ccc contest-logs
Not much, just my solutions and some comments from my practice contest today :)
Spoiler warning - contains full solutions!
...tags: programming ccc contest-logs
For c-like languages, that is :P
Anyway, I got tired of adding in hundreds of <span> elements anytime I wanted to put up pretty code on my posts, so I wrote this script. It works pretty well!
Example formatting of one of my various half-finished CSES solutions:
...tags: starship-dev programming
I swear binary exponentiation on matrices is actually magic.
While explaining this CSES problem to a friend, it occured to me that I could improve my O(n) solution, which used state machine DP, into a O(log n) one, by using matrix exp.
But even though I've used it quite a few times before, it still feels like magic. Take this task for example:
...tags: programming cses math
Today I was working through another simulated CCC contest and noticed how codeforces/speedforces has shaped my problem triage process - as CF doesn't award partials, my brain has gotten used to this decision tree:
...tags: programming codeforces
So today I was working on this problem on DMOJ.
First, some observations:
Constraint analysis: Result is bounded by something on the order of 4e10, higher than the 32-bit limit.
This is where my bad CF habits kick in...
tags: programming codeforces
Continuation of this post
Previously, we created a basic particle-based physics engine. Each point was stored as simply a position and velocity, and iterated to produce natural-looking motion.
How can we extend this to more complex shapes?
Before we even try to simulate such shapes, we'll need a way to store them. A simple point can be represented fully with a position and velocity, as...
tags: programming
In this blog post, we'll be covering the basics of how iteration-based physics works,and then implementing a very simple proto-engine in C.
Let's start with some background on iterative simulations as a whole.
Essentially all computer animations are done iteratively. Computer displays have a finite...
tags: programming