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

- Contest URL: https://atcoder.jp/contests/abc374
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20241005T2100&p1=248
- Duration: 100 minutes
- Writer: physics0523, math957963, ideas of all tasks are provided by KEYENCE
- Tester: yuto1115, nok0
- Rated range: ~ 1999
- The point values: 100-200-300-350-475-550-600

We are looking forward to your participation!

hope that I can get to 1200 this time

May you succeed. Firefly player

Hope that I can get to 1500 this time(

I failed.

It's doesn't matter

Because i'm failed too,,(

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

I'm not strong enough...

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

But why is the page of ABC374 red?

All other competition pages are normal.

Maybe it's an important contest?

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

Good luck! And have fun!

Hope that I can get to 1750 this time.

Did you like lose your old CF account ?

Why is the page of ABC374 red?

Because Chinese National Day?

haha

haha

Happy National Day!

Because it is sponsored by Keyence, just like ABC 325 ( the page is also red. ).

Happy National Day!

hope to AC at least 5 problems

Hope that I can get to 1400 this time.

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

I hope F and G will be not abstract

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

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

I'm not strong enough...

SFLSdalao%%%

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

Happy National Day!

Happy National Day!

me too.

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

I hope I can get to 800 this time.

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

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

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.

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

Thanks for the wonderful explanation

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.

Thanks for the insights. I created a video editorial for

E: Sensor Optimization Dilemma 2I got 8 testcases TLE on problem E lol.

az

Guys solution for problem C?

bitmask and take min

Can u elaborate on that? I did take min but bitmasks?

It is a simple recursion problem. Assuming you understand basic recursion, this should help you understand https://atcoder.jp/contests/abc374/submissions/58460153

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

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

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

check the code of jiangly Link

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

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

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

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

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

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!

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 ?

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.

Understood thanks bro

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

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

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!

SpoilerPlease remove extra

`cout << ' '`

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

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

53 cases are a lot!

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.

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

can you share your submission

Here

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

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.

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

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$$$?

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.

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

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.

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.

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.

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

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

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

could i get your atcoder handle ?

congratulations! :D

anyone please tell me problem c approach?

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

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.

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

//// ~~~~~~

## include <bits/stdc++.h>

using namespace std;

## define int long long

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

}

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; }

}

int32_t main() {

} ~~~~~~

can somebody tell me where i am going wrong

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?

W=min(W1, W2, W3) =>

W=min(4, 1+3, 4) = 4.

damn, thank you :)

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!

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?

Fail to debug E :(