Written on Sunday, unpublished until (tuesday, probably).
Took USACO yesterday.
Long story short: scored 350, distro was full / 1 / 0.
A rough chronology of how it happened: (timestamps are probably all very off but im estimating)
0:00 read A. I get some of the geo insight but not all of it. I get some $O(n^3/64)$ solve based on counting triangles.
Around 0:20 read B. I mindsolve the $l_0=r_0$ subtask and do some experimentation in code, none of it proves useful.
Around 0:40 read C. I kinda get the observation of the ++ forming diagonals, but I don’t fully understand it.
Anyway around 1:10? ish I decide to stop thinking about C and impl A (the $O(n^3/64)$ solve).
Well I impl it and get like the $N\le 10$ subtask. oops. that was kinda stupid. well at least I have it for stresstesting.
I do some more thinking and get the full solve (around 1:40? ish i’d say). I implement, it takes like 30?? minutes? to pass sample. I submit. All WA. skull emoji.
I do stresstesting. Turns out the problem is the collinear case. Anyway I try random stuff and keep stresstesting.
……
Two hours later (3:45) I’m still doing random stuff and stresstesting (and tilting really hard). At this point I’m tempted to just rage quit. Thankfully I didn’t.
3:50 i AC. Then I do some subtask grabbing. I was going to go for P3, $\min(R,C)=1$, but then I decided that I already had brute force for B so I got the brute force subtask for that one. Perhaps it would be better to go for the P3 subtask but I think I was tilting hard enough that I probably wouldn’t have gotten it.
It looks like results haven’t come out yet but 350 is better than I thought it was. Supposedly it might have a chance at leaderboard :skull:
I’m still kinda mad that I took so long on the collinear case. I probably had a chance at nontrivial points on P3. Maybe like 400 or 450 or something.
But I’m actually pretty satisfied with this performance. Oh and I am never ever going for a geo problem ever again. Nothing ever goes well when I go for a geo problem.
A brief editorial for problem 1:
Lets let $u$, $v$, and $w$ represent the vectors corresponding to three cows.
A beats B if $(a\times b)\cdot \langle 1,1,1 \rangle > 0$. Lets set $1=\langle 1,1,1\rangle$ for convenience.
Then, transitivity becomes $(u\times v)\cdot 1>0$, $(v\times w)\cdot 1>0$, and $(w\times u)\cdot 1>0$. Notice that this corresponds to uvw forming a triangle that surrounds the line of $1$.
Let’s project (you don’t need to actually project in the code) $u$ onto the plane perpendicular to $1$.
Now, notice we can use complementary counting. A triple does not contain the origin if they are all on the same half-plane (including the edge). We can angle sweep our vectors, use two pointers, and do some combinatorics.
More specifically: Angle sweep, let’s say we’re at vector $i$. 2p to get the last vector $j$ that we win or tie against. Add $j-i-1$ choose 2 triangles (one is $i$, and you choose two from the half-plane).
So this solves the base problem. Now, the problem is the collinear case.
Let’s say (the most cancer scenario) that you have like a line, and two points on one side and one point on the other. Then you will end up counting everything three times or so. This is a pain.
First, add some random vectors in like a triangle shape to make sure that your pointer won’t wrap around to collinear points that are before your point (such that you considered a cyclic shift of the triangle).
Then, maintain a third pointer. So one pointer represents the last one that you tie against, and the other one represents the last one you win against. And then you subtract the pairs such that all three are ties.
Or like roughly something like this. Honestly I’m not 100% sure why what I did works, it just does…
I also probably can solve P2, the $l_i=r_i$ subtask. So I’ll continue thinking about P3, later…
