Recently we noticed that the number of international participants to ARC-level contests are declining, so we decided to make announcements here.
When a contest is rated for ~2799, regardless of the name of the contest, the problems are prepared in the same way as ARC contests. We try to make the contest interesting even for reds (by the way, you can estimate the difficulty from point values). I think it's rather a div 1.5 contest rather than a div 2 contest (In this particular contest, since there are no divisions, the contest is like div 1.5 + div2 + div3 contest). We always have English editorials for ARCs these days.
Yahoo Programming Contest 2019 will be held on Saturday (time). The writer is DEGwer.
Contest duration: 120 minutes
The point values will be 100 — 200 — 400 — 600 — 800 — 900.
Let's discuss problems after the contest.
What is the difficulty level of 600....900 in atcoder as compared to codeforces(like is it of div2 D/E) ?
It's difficult to say, but generally, we try to make ARCs a bit harder than CF D2 (because it's rated up to oranges).
Legit thought this was for Yahoo! the American website.
The time links says that event has passed.
Thank you, fixed.
Recently we noticed that the number of international participants to ARC-level contests are declining, so we decided to make announcements here.
And you didn't bump it. :/
How to solve E?
Also, is there a better solution to D than the standard interval-with-maximum-sum segment tree, but with three parts EVEN-ODD-EVEN? That solution was a nightmare to write :/
Gauss
Xor/swap of two rows doesn't change the answer.
https://yahoo-procon2019-qual.contest.atcoder.jp/submissions/4215915
Why this comment is getting so many downvotes?
E : Treat the rows as a m-bit string, and find the number of subsets with xor 0 using Gaussian Elimination (answer is 2n - rank). Then, note that if you fix a subset of rows, the number of subsets of columns that work is 2m - 1 unless the xor of each row in the subset is 0, in which case the answer is 0.
You can solve D with 2 arrays for prefix min path/cycle and 2 for suffix min path/cycle.
For E, note that if we fix a number of columns and there's at least 1 row with odd sum in these columns, there will be 2^(n-1) ways to choose rows, otherwise 0. So for each row we can count the number of ways to choose other rows/columns so that it has odd sum. Now, we need to remove sets that we counted twice. We can uniquely remove these by fixing (i, j) as in i is the first row that has odd sum and j also has odd sum. To find the number of ways to choose columns for these, you can use xor gaussian elimination.
Edit: Looks like it's simpler than what I thought. :P
Can you please explain briefly how you handled Even-Odd-Even case? Editorial has mentioned a different approach.
We can pick a initial path that goes over some part of the values an even amount of times, then some part an odd amount of times, then some part an even amount of times again.
Build a segment tree over the interval. For every segment i, find
val[i][a][b]: How much we decrease the amount of needed operations, if we go over this interval, such that we start at part a, and end at part b, where part 0 is the initial even, part 1 is the odd, and part 2 is the last even.Also find
left[i][a]: How much we decrease the amount of needed operations, if we go over some suffix of this interval, with the suffix ending at part a, andright[i][a]: How much we decrease the amount of needed operations, if we go over some prefix of this interval, with the prefix starting at part a.At every segment also find
ans[i]: The maximum amount we can decrease the needed operations by by traveling over some segment in this interval.Updates are really laborious. For example,
But there's no reason why you would ever want to do this when there are no change-queries, so that's my bad :P
Got it! Thanks a lot mango_lassi :)
For D: you can just use dp with 3*n states representing the 3 even-odd-even states for each index. submission
amnesiac_dusk can you explain more ?
Its clear as explained above that snuke will move first over a segment even, then odd, then even number of times. Now, let dp[i][j] be the maximum number that can be reduced if snuke has moved upto ith dot and in the jth kind of segment(0-first even, 1-odd, 2-even). Now, if we consider a even stone in odd segment or vice-versa, It cannot be completely removed and we can update dp by a[i]-1 otherwise by a[i]. See my submission for more clarity.
how to solve problem d , ears ?
Can anyone tell what is wrong with following approach of D? I checked for all starting position of i. Now, if we fix starting position,I determine ending position by ternary search on cost values from (start+1,end) as it seems function of cost will be decreasing and then increasing. Then will take minimum cost among all i's. It is passing half of test case but failing on rest. Submission
This is about problem D .
how to formulate dp state from it :
Therefore, the problem can be solved by dynamic programming in OLtime, where DP[i][t]: (the minimum number of operations required considering up to thei-th ear when we already passedtof thefour pointsD; S; T; U)
It would be great if AtCoder has problem tags. It's DP problems are really very nice.