rng_58's blog

AtCoder Grand Contest 034 Announcement
By rng_58, history, 6 years ago, In English

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!

  • Vote: I like it
  • +102
  • Vote: I do not like it

Comments Comments (20)
| Write comment?
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Is the website ok? It responds slowly as hell

→ Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve C?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    As I see from my solution we take $$$1000$$$ days for exams $$$4, 10$$$ and $$$540$$$ for $$$9$$$

    → Reply
»
6 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Congrats to Petr the single guy to solve all problems.

→ Reply
»
6 years ago, # |
  Vote: I like it +83 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
  Vote: I like it +26 Vote: I do not like it

D is so beautiful! Thanks for the great contest!

→ Reply
»
6 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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).

    → Reply
»
6 years ago, # |
  Vote: I like it -15 Vote: I do not like it

This contest was good, but... the solutions of problem A, B, C, E was greedy.
Is it "GreedForces" or "AtCoder Greedy Contest"? :)

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve D in $$$O(S\log{n})$$$?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Basically, in the flow solution, find each shortest augmenting path in $$$O(log n)$$$.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So you need to maintain 4 heaps at each part and bruteforce each possible way how augmenting path may look?

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it possible to find the minimum possible sum in problem D faster than $$$O(S N^2)$$$?

→ Reply