rng_58's blog

By rng_58, history, 2 weeks 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
  • +91
  • Vote: I do not like it

»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Is the website ok? It responds slowly as hell

»
2 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve C?

»
2 weeks 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.

  • »
    »
    2 weeks 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$$$

»
2 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

Congrats to Petr the single guy to solve all problems.

»
2 weeks 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.

»
2 weeks ago, # |
  Vote: I like it +26 Vote: I do not like it

D is so beautiful! Thanks for the great contest!

»
2 weeks 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?

  • »
    »
    2 weeks 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).

»
2 weeks 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"? :)

  • »
    »
    2 weeks 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.

»
2 weeks 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.

»
2 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

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

  • »
    »
    2 weeks 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)$$$.

    • »
      »
      »
      13 days 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?

»
11 days 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)$$$?