hello world
Apr 14 2025
10:00 PM
10:00 PM
hi
...
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
I'm applying for a couple summer camps right now, and one of the applications included this prompt:
What person or event in your science and mathematics education has been the most influential in your decision to pursue a career in science or mathematics?
Here's my response. I think it speaks to my core philosophy pretty well:
...tags: life
And I don't want the world to see me
'Cause I don't think that they'd understand
When everything's made to be broken
I just want you to know who I am
- "Iris", The Goo Goo Dolls
I have offline query school for the next two days!!
We didn't get a huge amount of snow, only two or three inches, but the temperature is so low that it isn't melting naturally or artificially.
So, I have asynchronous school. Unfortunately this is happening literally when my finals were supposed to be, so they're being pushed back into 2nd sem..
also I need to update blog more often lol
the dragonfly is such an enigmatic, dynamic creature. its rise and fall on ghostly wings is unpredictable as chaos itself.. ehh what am I saying.... let's just say, it rises, yet again. if you know you know! ;)
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
today felt kinda surreal ngl
so my school is fake asf and is giving us the entire week of thanksgiving off.. as a result I had tests / inclass essays / projects due from literally every class yesterday and today :skull:
but anyway none of my classes had anything going on past noon + there were club events and stuff going on
this weekend im gonna be going to PUMAC with some friends - probably gonna absolutely throw but wtv
tags: math
I think I got 108 pts (AC x16, WA x1)
Honestly not terrible, I'll take it.
tags: math
Took AMC 12 yesterday, it went ehhh
First of all, performance: I solved 17 questions, left the rest blank.. Overall I was limited on time, but there were also a rather large number of problems that I didn't know how to solve.
I do feel though that the problems were.. a lot less 'standard' than previous years? This might just be an artifact of my lack of comp math practice over the last year, but several people I have talked to seem to think the same.. And also, if so, this would probably be good for me seeing that I haven't properly practiced in so long that I forget most of the usual constructions...
Anyway, at the very least, this can serve as practice for the 12B :D
tags: math
that the thing which most negatively impacts my productivity is idling on discord
oh and listening to music too, it seems.. rip
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
idk, recently just not much going on / too busy to post / too lazy etc. School been alr, had psats a while back. Bunch of tests/projects recently but nothing really memorable.
Currently in LA; parents at 20-year Caltech reunion. Can't do ABC/ARC both due to lack of time and also time zone.
Really interesting event though! Lots of accomplished people, interesting presentations, etc. Been doing a lot of self-reflection recently as well.
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
I've been sleeping kind of late recently and it is really interesting to see how it has been affecting my productivity. Particularly I noticed that I physically have lower energy, even many hours after I wake up, and that my focus is worse, procrastination, etc. I really didn't realize that lack of sleep could have so much of an effect on a person.. good to know!
The average small friend-group discord server starts simple, starts close-knit. And time passes, friends of friends join, eventually forming a distinction between the 'old' and the 'new'. More time passes, and the climate slowly changes; no longer quite so close-knit. Then inevitably, one of the first original members leaves. And this is in most cases the beginning of the end, a change that can only be delayed, not reversed.
As more members leave, the server drifts farther away from the vision it was set out to be, and more and more of the core members go inactive or leave entirely. Once this reaches critical mass, the server either burns out or overturns its members, its focus, its goal.
This is a pattern I've seen countless times in online communities. Much like any other social space, they are in a continual, inevitable state of change, in cycles where they are born, mature, grow old, and eventually die.
But though the same sort of patterns happen across nearly all social circles, every cycle's start is unique, its middle-age plays out unlike any before, and ends in its own way, too. So perhaps such a pattern isn't about the rigidity of social norm, but a meta-pattern in human behavior itself, and the way we respond and adapt to changes in ourselves, those around us, in the way we all interconnect; Seeing that larger, more physically-based communities still experience these same effects but over a longer timescale, what does this imply about the world we live in today?
tags: life
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
Weekend was pretty great. Took the atcoder on Saturday, was pretty nice. Had to sort out a bunch of stuff for most of the rest of the day, cant say here, kinda confidential. Today had ARML practice :D :D then did a pretty quick half cycle and kinda bricked on ioi18p5 :skull: oops
Atcoder breakdown...
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
Hey guys. Not a lot has happened recently, so I haven't been posting a lot. I might try out semi-regular casual posts similar to what jasonwei does. Not sure.
School has been going fine so far. Workload is actually kinda suspiciously low, but it's probably going to increase a lot once lang and physics ramp up.. Clubs and stuff are starting around now, but I kinda don't have the time or energy to be that involved in many (and contest club is out of question due to not enough ppl) nor do really any of them particularly interest me tbh.
Some classes are kinda free rn so I can get away with coding...
tags: school
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
Life isn't a zero-sum game.
So stop using grundy theory.
- unnamed
Junior year begins tomorrow!
I somehow ended up with 50% course overlap with two of my close friends - will be interesting for sure. Also my school gives an obscene amount of free time so I probably can get away with upsolving atcoders or something like that because imagine socializing.
tags: school
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
Here's to the ones who dream,
foolish as they may seem...
- "Audition", La La Land
Wow, school is starting soon!
Last year at the start of the school year I made a promise to stop procrastinating. It didn't hold. The year before that I did the same. It also didn't hold. I am again making a promise to stop procrastinating, so surely by induction, it won't hold...
tags: life
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
Over the course of the past week, I've had a lot of ideas come through my head that I haven't been able to incorporate into blog posts of their own. I'll try to put them out here, and hopefully some meaning can be derived from my ramblings...
tags: life
Going to be driving a circuit across northeast America, starting west to Ohio, then north through Toronto, Montreal, etc, then back down through New York. Will take about 10 days :D
Might not be able to update blog as often, but will continue contest programming grind :pray:
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've been having trouble falling asleep recently.
No, it isn't anything physical - I'm not sick, and my sleep schedule isn't quite erratic enough to be the cause. What keeps me up at night is the future.
...tags: life
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
I was shown this puzzle by @hy3na_xyz, a member of the Rutgers competitive programming discord server. Credit goes to them!
Given an N-dimensional tic-tac-toe board of side length L, how many winning paths are there? A winning path is a sequence of L cells that follow a linear path through the N-dimensional hypercube of the game board. ...
tags: math
So I decided to reformat artifacts as they are currently so that rebuilding is possible. The system works really well - but not only that: I'll be able to merge my old blog posts into mainstream without issues!
...tags: starship-dev
I'm quickly realizing how useful the ability to edit/delete previous pages is..
Not even just editing previous posts, but making layout changes comes with an inconvenience factor which scales O(n) with...
tags: starship-dev
My little sister's blog now uses Starship. Its styling looks really nice!
Also, while helping her set it up, we found a bug in the link generator code for standalone pages :P
The old blog has been nuked due to major breaking changes between v1.2 and v1.3 backend. Most pages are now...
tags: starship-dev