We will hold AtCoder Grand Contest 034. This contest counts for GP30 scores.
- Contest URL: https://atcoder.jp/contests/agc034
- Start Time: https://www.timeanddate.com/worldclock/fixedtime.html?iso=20190602T2100&p1=248
- Duration: TBD (around 2 hours)
- Number of Tasks: 6
- Writer: yosupo, maroonrk, sigma425
- Rated range: All
The point values will be announced later.
We are looking forward to your participation!
Is the website ok? It responds slowly as hell
It works fine for me now.
How to solve C?
Editorials are yploaded now.
How to get 2540 on the last sample testcase in C? I got only 2626 and I can't see the bug in my idea.
As I see from my solution we take $$$1000$$$ days for exams $$$4, 10$$$ and $$$540$$$ for $$$9$$$
Congrats to Petr the single guy to solve all problems.
How to get your best result to date on AtCoder?
Start by implementing both A and B before submitting each of them, because that's what all the cool kids do. Get two Wrong Answers. Attempt to fix A only to get another Wrong Answer. Contemplate throwing your laptop into a fire.
After 45 minutes, having A,B,C, skip D in favor of E, because the former is obviously too difficult. Observe that E is indeed trivial and can be even solved in $$$O(N)$$$. Don't listen to your suspicious voice, implement it and get WA. Contemplate throwing the laptop into a fire again.
Then realise you're an idiot and fix E. Subsequently read D and remember that you know this trick. Solve it in 10 minutes and then painfully watch how your penalty is dragging you down each minute.
D is so beautiful! Thanks for the great contest!
Why is it legal to divide in F?
The solution is something like $$$\frac{[1-2^n, 1, 1, 1]}{[1, 0, 0, 0]-input}$$$, but why is it OK to perform the division with zeroes in the denominator?
Because there are no zeroes in the denominator. Each denominator is of the form $$$-1\pm p_0\pm p_1\ldots\pm p_{2^N-1}$$$, where half of $$$\pm$$$ signs is replaced with $$$+$$$ and half is replaced with $$$-$$$. Because the sum of $$$p_0,\ldots,p_{2^N-1}$$$ is $$$1$$$, the denominators cannot be zero (except the denominator at index $$$0$$$, which is special-cased).
This contest was good, but... the solutions of problem A, B, C, E was greedy.
Is it "GreedForces" or "AtCoder Greedy Contest"? :)
Problem E is $$$dp$$$. Either way, I don't find this so surprising since a big proportion of all the problems are greedy and because AtCoder has an inclination towards less technical tasks, greed & math are the most widespread types.
This submission of Task A gives answer "NO" for test case
But it still got accepted, I think the correct answer should be "YES", is this a case of weak test cases or am I making a mistake.
Probably weak testcases.
My submission is giving YES. I think the test case was not included for checking.
How to solve D in $$$O(S\log{n})$$$?
Basically, in the flow solution, find each shortest augmenting path in $$$O(log n)$$$.
So you need to maintain 4 heaps at each part and bruteforce each possible way how augmenting path may look?
Is it possible to find the minimum possible sum in problem D faster than $$$O(S N^2)$$$?