atcoder_official's blog

KEYENCE Programming Contest 2024（AtCoder Beginner Contest 374） Announcement
By atcoder_official, history, 3 months ago, In English

We will hold KEYENCE Programming Contest 2024（AtCoder Beginner Contest 374）.

We are looking forward to your participation!

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

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

hope that I can get to 1200 this time

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope that I can get to 800 this time!!!

I'm not strong enough...

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

    I hope that I can go to 150 this time! Sorry,I seldom join abc...

    → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

But why is the page of ABC374 red?

All other competition pages are normal.

Maybe it's an important contest?

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    It is sponsored by KEYENCE. If you search all past KEYENCE sponsored contests on atcoder, all of them have their competition pages red.

    → Reply
»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Good luck! And have fun!

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope that I can get to 1750 this time.

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

Why is the page of ABC374 red?

Because Chinese National Day?

→ Reply
»
3 months ago, # |
  Vote: I like it +3 Vote: I do not like it

hope to AC at least 5 problems

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope that I can get to 1400 this time.

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hope i can get 800...last contest i have been -12...

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope F and G will be not abstract

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

    ***_fan has been -37! Share it!

    → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope that I can get to -114514 this time!!!

I'm not strong enough...

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Most of people here are Chinese(including me)!————Happy National Day!

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope that I can get to 0 this time!!!

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope I can get to 800 this time.

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

How to solve problem E? Is it some well known problem?

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Let's find the minimal cost for $$$i$$$-th process to produce $$$y$$$ products. Assume we bought $$$i$$$ machines of first type and $$$j$$$ machines of second type.

    $$$a \cdot i + b \cdot j \ge y$$$

    $$$p \cdot i + q \cdot j \rightarrow min$$$

    Let the first type of machine be "better" than the second: $$$\frac{a}{p} \ge \frac{b}{q}$$$. If we could buy fraction of machine, then we would use only the first type. But it can be the case, that we it is more effective to buy the second type machine (for example, if it is not effective, but we need only one last product, while the first type machine produces a lot).

    There is one quite known fact: $$$j$$$ is limited by some number. If we have $$$b \cdot (\alpha + \beta)$$$, where $$$j = \alpha + \beta$$$ and $$$b \cdot \alpha$$$ is divisible by $$$a$$$, then we can increase $$$i$$$ by $$$\frac{b \cdot \alpha}{a}$$$ and decrease $$$j$$$ by $$$\alpha$$$. This means, that $$$j$$$ is not greater, than $$$max(a, b)$$$ (in these case, it is possible to choose such $$$\alpha$$$, which is equal to $$$a$$$, so $$$b \cdot \alpha$$$ will be divisible by $$$a$$$).

    So we just check all possible $$$j$$$ from $$$0$$$ to $$$max(a, b)$$$.

    For the whole problem. Use binary search on answer and in check function calculate sum if all these $$$p \cdot i + q \cdot j \rightarrow min$$$ and check if it is not greater than $$$x$$$.

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Example to (if it is not effective, but we need only one last product, while the first type machine produces a lot)

      Cost = 16

      Machine 1 produces 10 items per day with cost 10 per unit.

      Machine 2 produces 6 items per day with cost 8 per unit.

      item to cost ratio of machine 1 is better then machine 2 but still we will buy 2 machines of type 2 to get 12 items per day at cost = 16.

      → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Thanks a lot. This explains the reason for jiangly taking the bound to be 100 .

      Thanks for the wonderful explanation

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

      Thank you so much for your detailed and clear explanation! I didn't figure out this proof, and instead just made a guess and set the upper bound to 4e4 (at first I tried 1e5 but got TLE and then I changed it to 4e4) to make it AC.

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

      Thanks for the insights. I created a video editorial for E: Sensor Optimization Dilemma 2

      → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I got 8 testcases TLE on problem E lol.

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

az

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Guys solution for problem C?

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

    bitmask and take min

    → Reply
  • »
    »
    3 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    2 ways to do that, both ways involve trying out all possibilities (Notice that N is small here)

    • Backtracking to try both groups for every department.
    • Enumerating all bitmasks which represent which departments will be in group 1 (The bit is off) or group 2 (The bit is on) (For example, if N is 5, a bitmask of 01010 means the first, third and fifth departments will be in group 1, the second and fourth departments will be in group 2).
    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Using bit manipulation is actually crazy omg also thank you guys!

      → Reply
»
3 months ago, # |
  Vote: I like it +3 Vote: I do not like it

in E why the machine costing higher price per product will be atmost 100

check the code of jiangly Link

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

    Well I thought it will be at most 15000 but it's hard to believe that it's at most 100.

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

      Do you understand the maths behind 100 or a particular number?

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

        Even I don't understand, maybe this was a very intelligent bound taken by jiangly.

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

        He has also considered the ratio's $$$a_i / p_i$$$ and $$$b_i / q_i$$$

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

          I got the solution for E!

          For every process i, it is always beneficial to greedily buy the machine with the better output / cost ratio.

          So buy that machine as much as possible, and the remainder products needed will be < 100. Now buy the other machine to fill this remainder.

          Worst case, the remainder is 99 and the other machine's output is 1, so the quantity we buy will be 99. Thats why the max quantity we will buy of this machine is approx 100.

          Submission for reference

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

    For some machine X, Y, say that X produces A products and Y produces B products. Note that any A machines of type Y can be replaced by B machines of type X, and the amount produced stays the same.

    Now, suppose that Y is more efficient than X. Then, observe that it is never optimal to choose more than B machines of type X, as they can always be exchanged for Y, resulting in the same production but less cost.

    A and B are bounded by 100, hence why jiangly can do this.

    Hope this helps!

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

      Note that any A machines of type Y can be replaced by B machines of type X, and the amount produced stays the same.

      how is this true ?

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

        ah sorry I didn't explain this too well:

        Each machine of type Y produces B products. Then, A machines of type Y will produce A*B products total.

        If we replace them instead with B machines of type X, each of these new machines produces A products, and there are B of them. So they produce the same amount.

        The only difference between them is cost, and because Y is "more efficient" than X, it will always be better to swap blocks of X for Y when possible.

        → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone prove why this solution for E is right? I thought it might have been hacked.

The idea is to purchase mostly the 'better' machine, and enumerate the number of the 'worse' machine from 0 to 15000.

Submission: https://atcoder.jp/contests/abc374/submissions/58472647

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

    can you tell why the range was only from 0 to 15000

    → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://atcoder.jp/contests/abc374/submissions/58486583 This is my submission for problem D. Can someone help me check why my solution doesn't even pass the sample inputs? When I run it on my compiler the solution matches with the sample solutions. Thank you!

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Spoiler
    → Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Please remove extra cout << ' ' statements.

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

      ohhhhh I didn't see them :((((( Thank you for helping !!!!

      → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone tell what was the logic on e

i applied ternary search on a binary search but some test cases are giving wrong My submission link

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

    53 cases are a lot!

    → Reply
  • »
    »
    3 months ago, # ^ |
    ← Rev. 4   Vote: I like it +3 Vote: I do not like it

    do binary search on the answer. now notice that, for each process, one of the machines is better than the other: supose we want to make lcm(Ai, Bi) products using a single machine. then, it will cost Pi * lcm(Ai,Bi)/Ai using the first machine and Qi * lcm(Ai, Bi)/Ai using the second machine. without loss of generality, supose the first machine will require less money to make this amount of products. then, you will never make >= lcm(Ai, Bi)/Bi products using the second machine (you could simply make them using the first machine with a lower cost). then, you can just brute force the amount of times you will use the second (worst) machine, which will be <= lcm(Ai, Bi)/Bi <= Ai products.

    → Reply
  • »
    »
    3 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Same, but I took advantage of small N and did ternary search to reduce the search space to <1e4 lol

    → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I failed to construct a checker function for my binary search on E, how can I do this?

→ Reply
»
3 months ago, # |
← Rev. 3   Vote: I like it +6 Vote: I do not like it

Why My Code got Wrong Answer in question E? I can't hack it, Can anyone help me to hack it? It works very well on random datas.

My solution is for each process $$$i$$$, for every $$$a_i \times b_i$$$ product, it is definitely better to choose either all $$$S_i$$$machines or all $$$T_i$$$ machines. The remaining part should not exceed $$$10^4$$$, so it can be solved by brute force.

→ Reply
»
3 months ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

I got the solution for E!

For every process i, it is always beneficial to greedily buy the machine with the better output / cost ratio.

So buy that machine as much as possible, and the remainder products needed will be < 100. Now buy the other machine to fill this remainder.

Worst case, the remainder is 99 and the other machine's output is 1, so the quantity we buy will be 99. Thats why the max quantity we will buy of this machine is approx 100.

Submission for reference

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

    This is the same as jiangly's idea, Can you prove why it's beneficial to use ratio $$$a_i / p_i$$$ and $$$b_i / q_i$$$?

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

      Because buying the machine with better ratio gives you more products per yen.

      Let's say you spend 'x' yen on both the machines. Then obviously you get more products from the machine with the better ratio.

      If the ratios are 5 products/yen and 2 products/yen and I can spend 500 yen, obviously I get more products per yen from the first machine. So then I can reach my threshold with less yen spent.

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

    For every process i, it is always beneficial to greedily buy the machine with the better output / cost ratio.

    So buy that machine as much as possible, and the remainder products needed will be < 100. Now buy the other machine to fill this remainder.

    Both the statements are incorrect. You just got lucky with your code, because you haven't implemented what you are thinking. Your code is correct though.

    Greedily buying efficient machines as much as possible is not optimal. In fact, as counter intuitive as it may seem, you need to buy inefficient machines first (explore all possibility instead of buying greedily) and only then should you buy efficient machines.

    I talk about a counter example to your idea in my video

    → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I screwed myself in E trying to answer the minimum cost for each pair to reach mid in O(1). I don't know why I didn't just loop since the constraints are low.

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

    But why greedily calculating the minimum cost for each pair in O ( 1 ) is wrong. It would be very helpful if we can have some samples where greedily calculating the cost won't work.

    → Reply
»
3 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Finally, I (would) reach yellow through get a 2400 perf in this contest.

I have struggled 4 years since I play my first contest in AtCoder.

→ Reply
  • »
    »
    3 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    4 years thanks that helps a lot. I am not the only one struggling it seems .I started 5 months back and i was thinking that why couldnt I solve from d onwards .So if i can solve A,B,C AND ITS BEEM ONLY 5 MONTHS AND THIS IS ONLY my 7 the contest so that means i am not doing bad right

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

    what it requires to reach yellow? solving all the problems fast?

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      I practice a lot and it makes me to deal with the easy tasks very fast, so that I can have more time to think about the harder tasks and to solve them

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

        could i get your atcoder handle ?

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

    congratulations! :D

    → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

anyone please tell me problem c approach?

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

    Try all subsequences using a complete search with bitmasking or recursion.

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

    Given the constraints (n ≤ 20), we can use brute force to explore all possible partitioning of elements. This is possible because we can represent all subsets of a set with a bitmask. By iterating over all masks from 1 to 2^n — 1, you can explore every possible way to divide the elements into two groups (Partition A and Partition B).

    Each bitmask represents a subset where the 1 bits correspond to elements included in Partition A, and the 0 bits correspond to elements included in Partition B. For example, if the bitmask is (01010), this means that elements in positions 2 and 4 belong to Partition A, and the remaining elements go to Partition B.

    For every bitmask, we calculate the sum of elements in both partitions. We then take the maximum of these two sums and compare it to a global minimum, which tracks the smallest possible maximum sum across all subsets. The goal is to minimize the maximum sum between the two partitions.

    → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Will there be english tutorial later? I'd like to check the solution for F and G.

→ Reply
»
3 months ago, # |
  Vote: I like it -12 Vote: I do not like it

//// ~~~~~~

include <bits/stdc++.h>

using namespace std;

define int long long

int minCost(int x, int m1, int p1, int m2, int p2) {

int t = x;
// case 1 
int x1 = (x/m1)*p1;
x %= m1;

int y1 = p1;
int y2 = (x/m2)*p2;
if(x%m2 != 0) y2 += p2;

x1 += min(y1, y2);

// case 2
int x2 = (t/m2)*p2;
t %= m2;
y1 = p2;
y2 = (t/m1)*p1;
if(t%m1 != 0) y2 += p1;
x2 += min(y1, y2);

return min(x1, x2);

}

bool helper(int mid, int x, int n, vectorm1, vectorp1, vectorm2, vectorp2) { int cost = 0; for(int i = 0; i<n; i++) { cost += minCost(mid, m1[i], p1[i], m2[i], p2[i]); if(cost > x) return false; }

if(cost > x) return false;

return true;

}

int32_t main() {

int n, x; cin>>n>>x;
vector<int>m1(n), m2(n), p1(n), p2(n);
for(int i =0 ; i<n; i++)
{
    cin>>m1[i]>>p1[i]>>m2[i]>>p2[i];
}

int low = 0;
int high = 1e9 + 1;

int ans = 0;





while(low <= high)
{
    int mid = low + (high-low)/2;
    if(helper(mid, x, n, m1, p1, m2, p2))
    {
        ans = max(ans, mid);
        low = mid + 1;
    }
    else high = mid-1;

}

cout<<ans;

} ~~~~~~

can somebody tell me where i am going wrong

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody explain please why production capacity in sample#1 of task "E" is 4 if W=min(W1, W2, W3, W4) => W=min(4, 1, 3, 4) = 1, hence production capacity should be 1, not 4?

→ Reply
»
3 months ago, # |
  Vote: I like it +11 Vote: I do not like it

https://www.youtube.com/watch?v=6-w832UQfL4&t=1s I recently created a youtube channel to discuss atcoder solutions. Here's the link for anyone who wants to watch it. It's only my second video so it might not be very good, but I'd be happy if anyone can give me advice!

→ Reply
»
2 months ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

My F solution is different from official editorial:

$$$\text{dp[i][j] = {minimum answer, minimum time of last shipment}}$$$

when considering the first $$$i$$$ orders and we shipped the last $$$j$$$ of them together.

Time complexity: $$$\mathcal{O}(NK^2)$$$ if you optimize calculating disatisfaction to $$$\mathcal{O}(1)$$$.

I initially tried the DP without the 2nd dimension, but it failed. Why do we need the 2nd dimension, or weak tests?

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Fail to debug E :(

→ Reply