Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

rng_58's blog

By rng_58, history, 13 months ago, ,

We will hold AtCoder Grand Contest 034. This contest counts for GP30 scores.

The point values will be announced later.

We are looking forward to your participation!

• +102

 » 13 months ago, # |   +1 Is the website ok? It responds slowly as hell
•  » » 13 months ago, # ^ |   0 It works fine for me now.
•  » » 13 months ago, # ^ |   0 It works on my machine
 » 13 months ago, # |   +8 How to solve C?
•  » » 13 months ago, # ^ |   +58 Editorials are yploaded now.
 » 13 months ago, # |   0 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.
•  » » 13 months ago, # ^ | ← Rev. 2 →   +10 As I see from my solution we take $1000$ days for exams $4, 10$ and $540$ for $9$
 » 13 months ago, # |   +13 Congrats to Petr the single guy to solve all problems.
 » 13 months ago, # |   +83 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.
 » 13 months ago, # |   +26 D is so beautiful! Thanks for the great contest!
 » 13 months ago, # |   -8 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?
•  » » 13 months ago, # ^ |   0 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).
 » 13 months ago, # |   -15 This contest was good, but... the solutions of problem A, B, C, E was greedy. Is it "GreedForces" or "AtCoder Greedy Contest"? :)
•  » » 13 months ago, # ^ |   +19 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.
 » 13 months ago, # | ← Rev. 2 →   +10 This submission of Task A gives answer "NO" for test case 10 1 9 2 10 ..######.. 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.
•  » » 13 months ago, # ^ |   0 Probably weak testcases.
•  » » 13 months ago, # ^ |   0 My submission is giving YES. I think the test case was not included for checking.
 » 13 months ago, # |   +8 How to solve D in $O(S\log{n})$?
•  » » 13 months ago, # ^ |   0 Basically, in the flow solution, find each shortest augmenting path in $O(log n)$.
•  » » » 13 months ago, # ^ |   0 So you need to maintain 4 heaps at each part and bruteforce each possible way how augmenting path may look?
 » 13 months ago, # |   0 Is it possible to find the minimum possible sum in problem D faster than $O(S N^2)$?