We will hold Mirrativ Programming Contest 2025 (AtCoder Beginner Contest 414).
- Contest URL: https://atcoder.jp/contests/abc414
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20250712T2100&p1=248
- Duration: 100 minutes
- Writer: sheyasutaka, toam, sounansya
- Tester: Nyaan, kyopro_friends
- Rated range: ~ 1999
- The point values: 100-200-350-400-475-525-625
We are looking forward to your participation!
I hope this contest to be much better than last one :)
Upd: bad :(
The problems are challenging, I like F and G. But C is disgusting.
how to do C and D ??
For C u can just brute force all decimal palindromes, for D u can observe that whenever u place a base station for a group of houses, its always optimal to place it in between so the strength for that station should be the distance between the farthest houses in the group, so u can just sort the distances between adjacent houses and remove the m — 1 biggest distances
We get n-1 adjacent distances , if we remove larger m-1 distances and add up the rest do we get the answer ?
Yep, the biggest m — 1 distances tho
Yeah I got it now.
Its like keeping m-1 stations at m-1 different positions where there are houses, effectively having strength zero ( Greedy).We are having one station to cover all other houses.
for problem D, in short, u need to view the question from a different angle. first sort the location of the houses, then you can think the problem like this: initially u have one station that cover from the first house to the last house, so power strength is (last-first)/2, then depends on the number of station you left to plant, u pick an index and divide the houses from that index, and make left side houses powered by a station while the right side powered by another station. you can do this division operation m-1 times, so be greedy as to where you divide.
Still quite couldn't get the approach for D. Can you elaborate more..
same couldn't get the solution . did you find a better solution? I was trying bs on answer i am not getting why it is not working
Sort the houses and then think about it then the problem becomes, "There are n elements in an sorted array and we have to from k sub arrays such that the sum of (max-min) of each sub array is minimized."
C is just bruteforce
For C, I tried to first generate all the base 10 palindrome in around O(sqrt(n)) time , i.e. for input n = 987654321, I enumerate from 1 to 98765 (the first half of n). then, I check if these number are also palindrome in base-A, but I keep getting TLE, and can't figure out a way to more efficiently generate palindromes
Yup got AC with this approach
U using C++? I'm using Python, maybe that's why
Yeah cpp
Ha no not exactly you can just iterate until 9999 then try if the number appended to its mirror works and this plus any digit in the middle
share your code please
You can write a next palindrome function. Total number of palindromes <=10^12 is of a countable order. https://oeis.org/A070199
Why is the sample of problem F SO WEAK??????
hey try this problem very hard give your thoughts https://codeforces.me/blog/entry/144656 very nice problem of trees
Problem G is easy to think but difficult to write. :thinking:
It is different from other ABC.
https://atcoder.jp/contests/abc414/submissions/67547421 i am getting run time error in B on 2 test cases can someone tll thr error
long long overflow
You need to move the
sum > 100check inside the for loop, becauselong longis not enough for 100 * 1e18for E, I arrived at this equation. How to compute this?
The solution to E is n*(n-1)/2 — Sum of count of all divisors of numbers from 1 to n
Great , but how
Proof?
a mod b = c means a = b * floor(a/b) + c
b > a imply a = c so it lead to contradiction
b < a is must and c < a is must
b must not divide a because it will make a mod b = 0 and c = 0 is wrong so it can't
then b < a and b not divide a must both hold
for a and b < a c will be uniquely determine
then we derive a way to count like above comment 👍
all divisorsThis part is wrong. You can't include the divisor 1 as a>1. Otherwise, this is a correct approach.
Edit: You can't include the number as a divisor as a and b needs to be distinct. I got it wrong. a>1 is already satisfied if we calculate it in this way.
I got that but couldnt really figure out how to compute it optimally since n is till 1e12?
So I submitted a brute force solution to check if it was correct and around 20 cases were passed and rest got TLE so yeah its correct.
floor sum like there are at most 2*sqrt(n) floor sum you can find it using two pointer like approach I learn it from this one https://codeforces.me/blog/entry/118001
You can try fixing $$$b$$$. Then the sum goes from $$$c = 1$$$ to $$$b-1$$$. In this particular floor sum for a fixed $$$b$$$, there can be at most $$$2$$$ distinct floor values, something like $$$p, p, p, ... , p-1, p-1, p-1$$$.
Now write this sum in expanded form and you will have to use floor sum trick.
where to learn floor sum trick from?
Here maybe. But you can also ask GPT for this as it a well-known thing.
great help. Nice
Here's my feedback :
A : ok
B : why putting
long longit's useless , but whatever it's just easy.C : why it's harder than D ?? , also why you put tight limit , additional $$$\log$$$ factor is enough to TLE (and I'm surely not the only one who got this).
D : ok , but should have been swapped with C.
E : uh , ok but as soon as I read it , I knew it's floor sum trick with $$$+$$$ PIE.
(hire me for testing if you don't have good one ;) , will be great if I got paid lol)
Can d Be solved using binary search on answer ? I tried but was getting wrong answer ,anybody did with bs ?
I tried to binary search on the answer, but than realize that it is not asking for the maximum strength among all stations planted, but instead the minimum sum of all stations strength. So, even though binary search will work in the first scenario it will not work as expected in the second.
Minimize biggest range $$$\ne$$$ minimize total sum of ranges. It's possible that there exists a solution that has a bigger range but an overall smaller total. For example:
In the example, its obviously possible to get a solution with $$$\text{max_sz} \le 10$$$ (cover first two with one, cover last two with another). But that's actually wrong! Notice that if the first station covers the first three houses and the last one covers the last house solo, that only incurs $$$15 + 1 = 16$$$ penalty instead of our $$$10 + 10 = 20$$$ penalty!
Now, binary search can work, but it uses more complex ideas that you don't really need until you hit like, 2400 CF rating. This problem is actually way easier if you remove the binary search idea and instead ask this:
How do you solve $$$k=1$$$? Then, is there a way to take this solution and use it to solve $$$k=2$$$?
You might be relating it with Angry Cows problem from USACO but I couldnt figure out a binary search solution for this since the power of each station is different, instead I came up with another very simple solution, sort the houses and then think about it then the problem becomes, "There are n elements in an sorted array and we have to from k sub arrays such that the sum of (max-min) of each sub array is minimized."
WTF is that PE, pure math!
E is a great problem.
How to do ?
Solve this using floor sum trick.
Hey could you also help in understanding the solution for D?
You take the smallest n-m gaps.
Try to proof this first:
Total signal strength + Sum of gaps between signals = Last house location - First house locationfirst you have
then you expand
then you expand further
then someone already provided the link (how to count n/b) https://codeforces.me/blog/entry/118001
Can you explain the expansion of summation?
let
then
well if you don't understand how to get rid of the first summation then think about remainder
and second summation:
we can rewrite our summation
then we can expand
then we have
and that is
and finally
How to do G? It kept TLE on 37 and other 3 testcases.
Trash contest.
Could anyone tell me why i got 3 TLEs in G? (https://atcoder.jp/contests/abc414/submissions/67547581) I'm crazy about it.
If there are negative edges, you’ll probably get TLE in those 3 cases.
Could the complexity be worse than $$$O(E\log V)$$$ when containing negative edges? For $$$r \lt L$$$, I build the edge with cost $$$-x_u$$$ connect from $$$u$$$ to the node in segment tree, and edge with cost $$$x_v$$$ connect from node in segment tree to $$$v$$$, and It pass in 1500ms.
My Submission
thx, i'm an idiot
Could you please tell me how to solve G. I saw editorial and solved the one in editorial (This Problem](https://codeforces.me/contest/786/problem/B)). In this problem, we use 2 segment trees.
But, Here how to do it when we have to use |xᵢ — xⱼ|.
Please help me @Inw143 and @toam
In short you have to use four segment trees rather than two, for:
Example for "boarding an eastbound train":
Example for "getting off an eastbound train":
Once you have the segment trees in place you can use extra nodes for each train, so that you add $$$O(\log N)$$$ edges each train, something like this:
english editorial please!
Yes
The E problem is so nice that i only found out pretty easy after contest:(
Why is it downvoted ?
Thank you for editorial :) .
Can anyone give me the solution for F.
What i tried was find dis from root to every index using bfs then if dis%k == 0 then print dis/k or else -1. What am i missing here, why my solution won't work?
You can go up for $$$x$$$ step then go down to other subtree by $$$k - x$$$ step.
I also use this solution, but keep getting WA at test 01_test_00 and 03_test_00. Do you have any ideas or hints about this? Thank you very much
Thanks got the problem in my solution.
Reply to my previous comment about E link
I used Deepseek to understand and I'm writing it here so
I can understand it more deeply
others get helped
so we had $$$ \sum_{b=2}^{n} \sum_{c=1}^{b-1} \left\lfloor \frac{n - c}{b} \right\rfloor. $$$
Lets ignore the outer summation and focus on the one inside. Also let $$$ r = n\mod b $$$ so we get $$$ n = q.b + r $$$ where $$$ q = \left\lfloor\frac{n}{b}\right\rfloor $$$
so the inner equation becomes
$$$ \left\lfloor\frac{n - c}{b}\right\rfloor = \left\lfloor\frac{q.b + r - c}{b}\right\rfloor $$$
This can be rewritten as
$$$ \left\lfloor q + \frac{r - c}{b}\right\rfloor = q + \left\lfloor\frac{r - c}{b}\right\rfloor $$$
Notice that we have $$$ 0 \lt = r \lt b $$$ and $$$ 1 \lt = c \lt b $$$ so the $$$ r - c \subseteq [b - 2, 1 - b] $$$
Now the term $$$ r - c $$$ can be split into 2 cases, when $$$ r \gt = c $$$ and when $$$ r \lt c $$$. When $$$ r \gt = c $$$ we get $$$ 0 \lt = r - c \lt = b - 2 $$$ which when put into the floor always comes out to be 0.
When $$$ c \gt r $$$ we get $$$ r - c = -(c - r) $$$. You may notice that $$$ 0 \lt c - r \lt = b - 1$$$
$$$ 0 \lt \frac{c - r}{b} \lt = \frac{b - 1}{b} $$$
$$$0 \gt \frac{-(c - r)}{b} \gt = \frac{-(b - 1)}{b} $$$
This values is always of the form $$$ -1 \lt d \lt 0 $$$ whose floor always comes out to be -1. (Recall that floor is the largest integer <= x)
so now the inner summation breaks into the following
$$$ \sum_{c=1}^{b-1} \left\lfloor\frac{n - c}{b}\right\rfloor = \sum_{i=1}^{r} q + \sum_{i=r+1}^{b-1} (q - 1) $$$
which becomes $$$ rq + (b - 1 - r)(q - 1) $$$
Now we have to simplify this which follows:
$$$ rq + bq - b - q + 1 - rq + r $$$
$$$ bq - b - q + 1 + r $$$
Substituting $$$ r = n - bq $$$ as $$$ n = bq + r $$$
$$$ bq - b - q + 1 + n - bq $$$
$$$ n - b + 1 - q $$$
$$$ n - b + 1 - \left\lfloor\frac{n}{b}\right\rfloor $$$
so the final expression becomes
$$$ \sum_{b = 2}^{n} n - b + 1 - \left\lfloor\frac{n}{b}\right\rfloor $$$
which is equivalent to
$$$ \frac{n(n - 1)}{2} - \sum_{b=2}^{n}\left\lfloor\frac{n}{b}\right\rfloor $$$
.
I spent a lot of time on G,but spfa was hacked :(
https://atcoder.jp/contests/abc414/submissions/67562418
How can I contact the atcoder admins?
The questions didn't come up for me until 10 minutes after I started (I have to use a vpn)
I'm 100% sure I registered as a ranked player but nothing is added to me!
This is the first time I've managed to solve 5 questions in a contest and if I don't get ranked I'll definitely kill myself
Can anyone give me the solution for G?
Why does this Blog get downvoted so much? Personally, I think Atcoder provides quality problems. In addition, the staffs are really friendly too.