chokudai's blog

By chokudai, history, 3 years ago, In English

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!

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

| Write comment?
»
3 years ago, # |
  Vote: I like it +37 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

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

    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 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Problem D is exactly similar to the problem in this blog

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

      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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
Rev. 2   Vote: I like it +37 Vote: I do not like it

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

I really miss contests like ABC 216.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    We can use __int128 integer type in atcoder.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    I dont see where do you need to you bigint for binary search

»
3 years ago, # |
Rev. 2   Vote: I like it +22 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve and get the solution for problem D?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    l = 0, r = 1e18 ==> mid = 5e17 mid * k ==> 5e17 * 200000 will overflow

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

    You are doing

    if (sum >= mid * k)

    if l is 0 and r is 1e18

    mid is 5e17

    and mid * k will be greater than long long range

    you can just use something like

    if ((__int128)sum >= (__int128)mid * k)

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # |
  Vote: I like it +4 Vote: I do not like it
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    It is enough to check the max H*W different values of a[i][j].

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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 years ago, # |
  Vote: I like it +23 Vote: I do not like it

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 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Why putting so trivial G after so hard DEF?