The last contest of the 2020-2021 USACO season is running from April 2nd to April 5th this weekend. Good luck to everyone!
This forum will be read-only for the duration of the contest window. Do not discuss the contest until its conclusion is announced on the USACO website (sometime after 7:00 am April 6th EST).
Contest is over.
3 more benq problems this time jesus christ
What approaches did you use for #1 on the Silver contest? I did a mostly standard dfs, but in the visited array, instead of vis[i][j] being a boolean on whether I had already visited (i, j) or not, because we can go back the way we came and retrace our steps, I made dp[i][j] be an unordered_set of the possible cow tic-tac-toe grids that have already been seen when visiting (i, j). But that approach TLE’ed on test case #10 (which cost me in-contest promo, sad), so I’m curious to see what others did.
I didn’t take the silver contest because I was gold, but something that works is using a ternary mask to store which states you have visited, so you can do vis[25][25][3^9].
I haven’t tested this is faster, because the contest isn’t open yet 
, but I’m assuming so because its much faster than unordered set which typically runs like a logn time set.
Why is Platinum T2 only k=2 and n = 100?
It is a very interesting problem, nice and cute, but the BEST algorithm to find Eulerian circuits is a very straightforward way to solve the problem and without any optimization, it have a time complexity of O(n^3). I personally believe have n=5000, k=2 would be better.
The solution page of Platinum T2 introduced two ways to reach O(kn^2), I felt very confused not to have a larger data entry.
It’s not straightforward unless you already know it …
(Plus I totally didn’t know that this could be applied before the contest ^_^)