We will hold AtCoder Regular Contest++ 232. Note that it's on Saturday, not Sunday.
- Contest URL: https://atcoder.jp/contests/arc232
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20261010T2100&p1=248
- Duration: 150 minutes
- Writer: maroonrk
- Tester: snuke, blackyuki
- Rated range: 1600 — 2999
- Point Values: 800-800-800-800-1100
We are looking forward to your participation!
Could you please tell me whether the blank "Date of birth" should be
dd/mm/yyyy(e.g.17/09/2010) ormm/dd/yyyy(e.g.09/17/2010)? I don't know how to fill in that blank.try brute-forcing it
How come for A, a simple cycle detection spfa works, but not my spfa that tracks possible solutions for each location? Should not my spfa be much harder to hack?
Could you explain, how SPFA helps here?
The easy way to think about it is to represent as difference constraint problem. for some constraint x, y, prefix_sum[x] + 2 = prefix_sum[y] so we can bound using two inequalities. Also prefix_sum[i] <= prefix_sum[i+1] <= prefix_sum[i] + 1, so two more inequalities can be used. This solution somehow works even though there are trivial ways to hack it.
My solution involves maintaining the lower and upper bound of each value just checking for contradiction in the range rather than cycle detection. This in theory makes it harder to hack, but I got tle with this.
By thinking of both and choosing a better solution, I somehow got worse score than people who just thought of the first solution.
Many optimized spfa have passed A/fn/fn/fn
Is $$$O(N^5)$$$ intended to pass for D? Decently fast submission, slower but more bruteforcey submission. It's just a simulation DP made more efficient by stuff like precomputing coefficients and skipping zero-transitions.