We will hold AtCoder Grand Contest 038. This contest counts for GP30 scores.
- Contest URL: https://atcoder.jp/contests/agc038
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20190921T2100&p1=248
- Duration: TBD (around 2 hours)
- Number of Tasks: 6
- Writer: maroonrk
- Rated range: All
The point values will be announced later.
We are looking forward to your participation!
So B, C, D are all worth $$$700$$$ points O_o, interesting!
How to solve A?
https://atcoder.jp/contests/agc038/submissions/7635895
Use some picture like this:
$$$ 1 1 0 0 0$$$ (here $$$A$$$ ones)
$$$ 0 0 1 1 1$$$
($$$B$$$ times repeat this pair)
and then just:
$$$ 1 1 0 0 0 $$$
for all remainings
Loop over the amount of rows you'll assign a ones to (n), and the amount of columns you'll assign b ones to (m), until you find n, m such that both give the same amount of ones for the whole array. If you find no such n, m, output -1
For the first m columns, set their need to b. For the other columns, set their need to h-b.
For the first n rows, put a 1 at the a columns with maximum need, and decrement their need.
For the next h-n rows, put a 1 at the w-a columns with maximum need, and decrement their need.
I've been thinking this way but couldn't prove that it works. In general if you are given degrees of the vertices the fact that sum of both parts is equal is not enough for a simple graph to exist. I couldn't find any criterion. Does anybody know it?
You can model it as a flow network. Criterion that it doesn't exist translates to existence of some cut.
EDIT: Quoting you from below: "typical flow problem" :D
Well, $$$O(n)$$$ flows seemed too slow. And too hard for A.
Yeah, I didnt mean that it was supposed to be solved like that. Intended way of solving A was "cout<<(i<A)^(j<B);" (I completely agree it's very hard to come up with, took me a lot of time to notice this), but the solution to the problem with fixed degrees in bipartite graph is flow.
At least it seems that A is so complicated nobody can explain it. So no need to be mad for not solving it :)
How to solve C
Editorial
Thanks for the cool F! However, C is very typical.
F also seemed like a typical flow problem to me.
I've solved thousands of flow problems and still have no idea how to solve this one even though friends are explaining it to me for like 10 minutes already xd.
You have some cycles, for each cycle you either make all $$$a_i = i$$$(first type) or $$$a_i = p_i$$$(second type), the same for $$$q$$$. The obvious idea would be to find a mincut between the cycles of the first type and the second type. But all our penalty edges are between the cycles of the same kind, so it doesn't work. But the graph is bipartite so we flip one of the parts: we take cycles of the first type in $$$p$$$ and cycles of the second type in $$$q$$$ and need to find min cut between cycles that we take and don't take.
Yes C is typical, and in fact, it was not intended to set this problem. We were preparing another hard problem (which should have been F) but a significant issue arose form that task and we had to remove it. Then this C was inserted to the problem set and old CDE was moved to new DEF.
I will try my best to avoid such cases in future contests. Anyway, thank you for taking part in the contest!
C: ORIGINAL PROBLAM DO NOT STEEL
A, B, D were pretty nice. D could have benefited from a bit more points (900?), it wasn't hard to implement but there's a lot of things to consider.
How to solve B?
I believe this is the intended solution : For all subarrays in A of size L, see to it that the left element of leftmost element and right element of current subarray is lesser and larger than all the elements of current subarray, because if it is so, then we have a repeating subarray, think about it, it's just the same as previous subarray considered after sorting ? But are those all the repetitions? No! Repetitions could occur if 2 subarrays are already sorted right? To check a subarray of being sorted, check largest length till which subarray is sorted starting at that position(2 pointers kind of deal). But remember to keep 1 instance of the permutation where this kind of repetition occurs,ie,when 2 or more subarrays are sorted.
Failed to implement B with the sliding window so I implemented segment tree with hashes (2 bases was needed) :D
+
I implemented it with set, was thinking of deque before, but even after that, failed 2 test cases ☹️ out of 32
Can someone explain the PIE idea on E? I'm pretty confused by the editorial.
As for how inclusion-exclusion is applied:
Let's pretend we generate an infinite sequence, and find the expected value of the number of turns before all $$$B_i$$$ are reached. A turn counts toward our expected value if at least one of the following is true: before the turn, the number of $$$i$$$ in our sequence is less than $$$B_i$$$.
Now for each turn, we can use inclusion-exclusion using these statements as events, to calculate the probability that it counts toward our sum.
Task C — LCMs is probably standard for a lot of people but it was new for me and I wasn't able to figure out the intuition behind the approach. The editorial is pretty unintuitive (atleast for me , like from where does those wi come from ? ) . Can someone explain the intuition behind it ?
I believe C can be done much simpler than in editorial, by simply determining what is $$$f(d) = \sum_{gcd(a_i, a_j) = d} a_i a_j$$$ for every $$$d$$$ explicitly. The trick is to consider values of $$$d$$$ in descending order and noting that $$$f(d) = g(d) - \sum_{k \ge 2} f(kd)$$$, where $$$g(d) = \sum_{d|a_i, a_j} a_i a_j$$$.
$$$g$$$ can be trivially determined, so can be $$$f$$$.
Got it. Thanks a ton ! Btw the functions 'f' and 'g' you defined are pretty clever. I was wondering that this way we can even avoid doing mobius inversions at a lot of places if we define a such recurrences , is this true ? Are there any helpful resources to learn these or links to similar problems ? How did you learn this stuff ?
I learn this stuff the hard way, by solving the same problem but with gcd instead of lcm on high school workshop and then presenting my solution with that inclusion-exclusion stuff, mobius inversion bullshit etc. and after 0,5h of explaining where all the people stopped listening long ago one guy came to board after me and showed this trick within a minute and I was like :oooo
Hah, I remember trying and failing to solve this or something very similar. I didn't realise it was so simple back then, but I remembered not to make the same mistake now.
Can you please explain what is g used in calculating the g(d) above. Also what do sum1, sum2 and sum_p represent in your submission your submission and how do they help in calculating sum_prods[g].
I added a newline in my previous post, does that answer your first question :D?
When my loop is at x, sum_1 is sum of a_i for a_i's divisible by x, sum_2 is sum of a_i^2 for a_i divisible by x (I use $$$2 \sum a_i a_j = (\sum a_i)^2 - \sum a_i^2$$$). sum_p is g(x) and from these I derive f(x) which is sum_prods[x]
Thanks a lot.
Are there any updates on WTF? Are you planning to increase the number of advancers? How many AGCs (or similar) are yet to be in 2019? Can you update the scores? rng_58
Probably on February next year. What information do you want to know in advance?
No, sorry, this year the number of advancers will be 8 again.
We are planning 12 per year, so 4 more I hope.
Updated.