We will hold Daiwa Securities Co. Ltd. Programming Contest 2024（AtCoder Beginner Contest 383）.
- Contest URL: https://atcoder.jp/contests/abc383
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20241207T2100&p1=248
- Duration: 100 minutes
- Writer: MtSaka, nok0, evima
- Tester: physics0523, kyopro_friends
- Rated range: ~ 1999
- The point values: 150-250-350-400-500-525-625
We are looking forward to your participation!
Hope the problem G is easier than last two ABC.
There aren't any rated participant passed G.
Is Daiwa Securities Co. Ltd. hiring via this contest for any role?
Hope all the coders can get a high perf. GL && HF!
I wish every could have a fantastic experience at this anticipating contest!
I AC D !!!!!!!!!!!!!
what even D?
Basic number theory problem
D is easy if you know the divisor formula.
what is that? can you given a high level editorial?
The number of divisor of any positive integer n is (p1+1) * (p2+1) *(pk+1). where pi is one of the distinct prime factor of n. since 9 can only be written as a product of 3 * 3. and 3 * 1. The number of prime factors of such an integer who has 9 divisors and either 2 or 1. get all the primes until 10^7 and brute force it.
E harder than F
u did f?
yes
can you explain your approach
Sort on the basis of colour and then apply dp
dp
first,sort the elements with c
$$$dp_{i,j,0/1}$$$ being: seeing to the i-th element,having used j money, 0 for no elements of this color have been choosed,1 otherwise
(sorry for my bad english)
+1
How G? I had some ideas using aliens trick, but I was still no where close to solution.
Can anyone explain E?
So, you set this kind of D, what are you gonna do for ABC next time?
huh??????????????????????????????????????????????????????
Why r u mad though?
it's just that if these kinds of problems are permitted then they can shit out a task every 30 seconds and one problemset every 10 minutes, and still argue "it makes a problemset anyways" instead of actually considering if it can determine rating properly
ABC is meant to be educational.
For D, my solution WA*29. For Sample2
4000000000000, my code output407097while the correct answer is407073. Why?I was doing the exact same mistake. For the case p^8, p should be prime, you are probably counting for all natural numbers p, if p^8 <= n, but it has to be done only for primes
I was also doing the same mistake. How can so many people think the same way and step into the same trap?? It's actually funny...
Lol,true
Got it, thank you very much!
You're asking why but not providing your code?
My Idea for the problem E and F:
E:- Topic — Sorting, DSU || For each node, we will maintain whether the node belongs to arr1 or arr2. We have maintained it using cnt1 and cnt2 variables in DSU. First, sort the edges in ascending order. Then connect the edge one by one and during each Union Operation, We can connect the path from arr1 to arr2 using min(cnt1[node1],cnt2[node2]) or from arr2 to arr1 using min(cnt2[node1],cnt1[node2]). The cost will be no. of operations multiplied by edge weight in current Union. https://atcoder.jp/contests/abc383/submissions/60536697
F:- Topic — Knapsack DP, Sorting || The problem is simple Knapsack, the only catch is how to maintain the number of distinct colors. Suppose the number of distinct colors is X, then we can add K(given constant) by X times. We can sort the items by the colors so that we can check if the next item is of same color or not. We can maintain binary parameter in DP to check if we are taking current color first time or not. https://atcoder.jp/contests/abc383/submissions/60546303
Great job! For E, there's a trick that can simplify your code. You can store the occurrences in one array $$$cnt$$$, add $$$A_i$$$ to it and minus $$$B_i$$$ from it. Then you can just multiply $$$cnt_u$$$ and $$$cnt_v$$$ to see if it gives the answer after the merge. Click to see more information.
Could you please explain how your code checks if a color is being used for the first time in Problem F?
parameter op=0 represents that current color is not used yet, that's why temp variable= k when op=0. Once we use current color, we pass op=1. If next color is different from current color, again pass op=0
In E, we can find lengths using dijikstra but how would we pair A,B??. One way can be sorting lengths of each pair (Ai,Bi), but that would be k^2.
You can sort edges based on the weight. As the cost is defined as max weight of the edges on the path, you can add them 1 by 1. When A and B become connected through new edge, it means $$$dist(A, B) = w_{edge}$$$.
Then it's the greedy idea: if you can pair A, B with a minimal cost of the set, you should do it. Otherwise, the cost would be worse. Consider freshly connected A, B and still not connected C, D. If you don't connect (A, B) now and consider (A, C) + (B, D) was more optimal, that you'll wait until C is connected to the (A, B) component and D is connected with (A, B) component as well. At that moment (C, D) is in the same component too (but maybe they were connected even earlier). Then the 2 holds: $$$cost(A, B) \le cost(A, C)$$$ and $$$cost(C, D) \le cost(B, D)$$$.
So, $$$cost(A, B) + cost(C, D) \le cost(A, C) + cost(B, D)$$$. And it is better to pair them greedily. Not sure this is a strict proof, but seems strict enough
oh, i was thinking f(x,y) as shortest distance btw x,y
Say |AB|=1, |BD|=2, |CD|=3
|AB| + |CD| = 1 + 3 = 4 |AC| + |BD| = 3 + 2 = 5
indeed, |AB| + |CD| <= |AC| + |BD|
But |BD| < |CD|.
So I don't think your proof is rigorous.
it's basically the variant of kruskal's algorithm
can we calculate efficiently next DP:
dp[i][j] = max{0 <= k <= j}(dp[i-1][k] + a[i][j-k])
It's some kind of convulsion but I don't understand how to calculate it.
Can someone help me with this D solutionIt fails one testcases and i am not able to debug it.
try to not use the in-built sqrt function. make your own and try again
fails again here
In the last loop, you should remove the condition (i != sq), as you are leaving out some pairs from (0 to i — 1) when (i == sq).
Thanks for your reply,i realised it rn the mistake
any idea about problem G?
Is it rated?