Блог пользователя chokudai

Автор chokudai, история, 3 года назад, По-английски

We will hold KEYENCE Programming Contest 2021 (AtCoder Beginner Contest 227).

The point values will be 100-200-300-400-500-500-600-600.

We are looking forward to your participation!

  • Проголосовать: нравится
  • +84
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +37 Проголосовать: не нравится

Few months back, I used to solve 3 out of 6 problems and sometimes, the 4th problem too. But I wasn't satisfied so I practiced more and today I could solve 3 out of 8 problems. :(

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +27 Проголосовать: не нравится

    Few months ago I could solve 4 problems consistently and sometimes 5th problem too and today I could solve only 2 out of 8 problems. I am evolving, just backwards :(

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      The satisfaction I felt today after solving C is equivalent to one I got solving E few months back :D

»
3 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Round is more unbalanced than usual... How to solve D?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I tried using a priority_queue.

    First put the K biggest departments onto the queue, then iterate the remaining departments biggest first.

    Take the smallest department from the q, add the current department, and push it back onto the queue. Then, in the end, the smallest department on the queue should be ans. But WA for some reason:/

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    Let's say you are able to do $$$X$$$ projects, then consider iterating over $$$A_i$$$ in non-increasing fashion. Let's also have a variable $$$take$$$ initialized to $$$0$$$, which stores the amount of members assigned to each of the $$$X$$$ projects.

    If for some $$$i$$$, $$$A_i$$$ $$$\geq$$$ $$$X$$$, then we can simply pick $$$X$$$ members of this department and individually assign them one of the $$$X$$$ projects. In this case increment $$$take$$$ by $$$1$$$.

    If $$$A_i$$$ $$$\leq$$$ $$$X$$$, then let's store the sum of such $$$A_i$$$ in another variable $$$res$$$. Finally increment $$$take$$$ by $$$res / X$$$.

    If $$$take$$$ $$$\geq$$$ $$$K$$$, we can do $$$X$$$ or more projects. So you can binary search over $$$X$$$.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Problem D is exactly similar to the problem in this blog

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I somewhat remembered your approach in that blog and tried something similar with ternary search. But it still didn't pass :(

      Can you please see where it's wrong : submission

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    When you set X projects, you can not assign over X persons from one department. it is proved by pigeonhole principle.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +37 Проголосовать: не нравится

In my humble opinion this is the most unbalanced and crazy ABC recently.

I really miss contests like ABC 216.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Had to use BigInteger in one place while writing the Binary search for D.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +22 Проголосовать: не нравится

Everytime I do ABC contests. I question my rank whether I am so bad that I cant even do beginner problems ?

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

How to solve and get the solution for problem D?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In D, I am getting WA by taking the right limit of binary search as 1e18, but AC if I take it as 1e18/k. Any ideas why? I can't see where it is overflowing. Here is my Submission for reference

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Here's a solution I got accepted for D:

Consider the $$$N-K+i$$$ companies with the smallest number of people for some $$$1 \leq i \leq K$$$ and call them small. Note that every selection of $$$K$$$ companies must include at least $$$i$$$ small companies, so the answer is at most $$$\frac{\sum \text{people in small companies}}{i}$$$. Now take the minimum among all $$$1 \leq i \leq k$$$.

Clearly this condition is needed, but can anyone prove sufficiency/hack this solution?

»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone explain F? I didn't got the editorial. They are saying for some fixed X but X can be ~ 1e9.

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

That prove for D sounds simple, but I still do not get it. Can somebody explain with more words?

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    me too

    Edit : I think I have understood in a visual way

    For example

    4 projects(k=5):

    1 : 1 2 3 5 6

    2 : 1 2 3 4 5

    3 : 1 2 3 4 5

    4 : 1 2 3 4 5

    Watch one thing as number of element 5 is less than p it won't ever collide with 4, that's the thing

»
3 года назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

Does ABC means only problem A,B,C for beginners?

And I'm so frustrated when I find G much easier than E,F.I lose a chance to be yellow again!

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Can someone explain the proof for the D problem, I don't understand how P*k<sum ensures that there can be at minimum P projects. where sum is the sum of min(Ai,P) and P is the number of projects.

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    They have used induction to prove that when $$$P*K \leq sum$$$ where $$$sum = \sum_{i=0}^n min(A_i, P)$$$, we can always construct at-least $$$P$$$ projects

    We sort the array $$$A$$$ in non-increasing order (let's call this array $$$B$$$) and use the following construction: Pick the first $$$K$$$ elements from $$$B$$$, take 1 employee from each and create a new project

    Here is the proof by induction:

    1. Let's say we have more than $$$K$$$ departments in $$$B$$$ such that $$$B_i \geq P$$$. Here we can simply create $$$P$$$ projects from the first $$$K$$$ elements of $$$B$$$

    2. If above condition doesn't hold, we can still pick first $$$K$$$ departments from $$$B$$$, choose $$$1$$$ employee from each and create $$$1$$$ project. Now, we are left with $$$P-1$$$ more projects to construct. But the $$$sum$$$ has also changed, let's say it becomes $$$sum'$$$. The following equation holds true : $$$sum \geq sum' \geq sum-K$$$. This is because we choose $$$min(A_i, P)$$$ employees for each $$$i$$$ while calculating $$$sum'$$$. So, we may end up subtracting $$$1$$$ or we may end up subtracting nothing for each $$$i$$$ in $$$[1, K]$$$ depending upon whether $$$A_i \geq P$$$ or not.

    Now, we end up with following simple derivation that proves that by induction, we can construct remaining $$$P-1$$$ projects in a similar way.

    $$$P*K \leq sum$$$
    $$$(P*K) - K \leq (sum) - K$$$
    $$$(P-1)*K \leq sum -K \leq sum'$$$

    Hope this helps!

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Why putting so trivial G after so hard DEF?