atcoder_official's blog

AtCoder Beginner Contest 414 Announcement
By atcoder_official, history, 14 months ago, In English

We will hold Mirrativ Programming Contest 2025 (AtCoder Beginner Contest 414).

We are looking forward to your participation!

  • Vote: I like it
  • -6
  • Vote: I do not like it

Comments Comments (75)
| Write comment?
»
14 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I hope this contest to be much better than last one :)

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

how to do C and D ??

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

    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

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

      We get n-1 adjacent distances , if we remove larger m-1 distances and add up the rest do we get the answer ?

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

        Yep, the biggest m — 1 distances tho

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

          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.

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

    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.

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

      Still quite couldn't get the approach for D. Can you elaborate more..

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

        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

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

          "
okay, the approach this not complicated, I'll show you an example



take this as the input
  7 2
  5 10 15 20 8 14 15

so n = 7 and m = 2

now lets sort the array into 
  5 8 10 14 15 15 20

first try to use one station to cover every house, then the station is best to be placed at 12.5 so to minimize strength, which is 7.5

now the sum of strengths is simply 7.5, lets call it S(1)

but we have two stations to plant, It means that I can split the array into two parts, and let each part be powered by a station.


 
in that case we can split the houses in these 5 ways

  5      10 14 15 15 20 -> sum of strengths (5-5)/2 + (20-10)/2
  5 10      14 15 15 20 -> sum of strengths (10-5)/2 + (20-14)/2
  5 10 14      15 15 20 -> sum of strengths (14-5)/2 + (20-15)/2
  5 10 14 15      15 20 -> sum of strengths (15-5)/2 + (20-15)/2
  5 10 14 15 15      20 -> sum of strengths (15-5)/2 + (20-20)/2

now, it is important to see, that in the first way, the total strength equals to S(1) - Gap, where Gap is the distance of the two houses where the split happen. 

e.g. in first way, the sum of strengths is (5-5)/2 + (20-10)/2 = 5, which is exactly S(1) - (10-5)/2 = 7.5 - 2.5 = 5

same goes for all of them

so, the first and last way of split will give the minimum sum of strength, because they have the maximum distance between the two houses where the split happen



so now the question translates to: 
  you have m-1 operations to split the houses, and each time you split, the sum of strengths reduce by the distance of the two houses where the split happen. How to find the minimum sum of strength?



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

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

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

    C is just bruteforce

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

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

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

    Yup got AC with this approach

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

      U using C++? I'm using Python, maybe that's why

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

      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

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

        share your code please

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

          bool isPal(ll k, ll a) {
	char buf[64] = {0};
	to_chars(buf, buf+64, k, a);
	int len = strlen(buf);
	for (int i = 0; i < len/2; i++) {
		if (buf[i] != buf[len-1-i])
			return false;
	}
	return true;
}

void runTest()
{
	ll a,n;
	cin >> a >> n;
	ll res = 0;
	ll maxL = to_string(n).size();
	for (int i = 1; i < 10; i++) {
		if (isPal(i, a) && i <= n)
			res+=i;
	}
	for (ll val = 1; val < pow(10, maxL/2); val++) {
		string s = to_string(val);
		string t{s.rbegin(), s.rend()};
		ll k = stol(s+t);
		if (k <= n && isPal(k, a))
			res += k;
		for (char c = '0'; c <= '9'; c++) {
			ll k = stol(s+c+t);
			if (k <= n && isPal(k, a))
				res += k;
		}
	}
	cout << res << endl;
		

}
          → Reply
  • »
    »
    14 months ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    You can write a next palindrome function. Total number of palindromes <=10^12 is of a countable order. https://oeis.org/A070199

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

Why is the sample of problem F SO WEAK??????

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

Problem G is easy to think but difficult to write. :thinking:

It is different from other ABC.

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

https://atcoder.jp/contests/abc414/submissions/67547421 i am getting run time error in B on 2 test cases can someone tll thr error

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

for E, I arrived at this equation. How to compute this?

$$$ \sum_{b=2}^{n} \sum_{c=1}^{b-1} \left\lfloor \frac{n - c}{b} \right\rfloor $$$
→ Reply
  • »
    »
    14 months ago, hide # ^ |
     
    Vote: I like it -7 Vote: I do not like it

    The solution to E is n*(n-1)/2 — Sum of count of all divisors of numbers from 1 to n

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

      Great , but how

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

      Proof?

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

        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 👍

        → Reply
        • »
          »
          »
          »
          »
          14 months ago, hide # ^ |
          ← Rev. 2  
          Vote: I like it -8 Vote: I do not like it

          all divisors

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

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

      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.

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

    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

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

    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.

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

Here's my feedback :

A : ok

B : why putting long long it'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)

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

Can d Be solved using binary search on answer ? I tried but was getting wrong answer ,anybody did with bs ?

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

    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.

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

    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:

    4 2
10 20 25 35

    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:

    Small nudge
    → Reply
  • »
    »
    14 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

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

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

WTF is that PE, pure math!

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

E is a great problem.

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

    How to do ?

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

      Solve this using floor sum trick.

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

        Hey could you also help in understanding the solution for D?

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

          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 location

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

      first you have

      $$$\sum_{b=2}^n \sum_{c=1}^{b-1} \lfloor \frac{n-c}{b} \rfloor$$$

      then you expand

      $$$\sum_{b=2}^{n} (n \bmod b)*\lfloor \frac{n}{b} \rfloor + (b-1- n \bmod b) * (\lfloor \frac{n}{b} \rfloor - 1) $$$

      then you expand further

      $$$n - 1 + n * (n - 1) - (2 + n) * (n - 1) / 2 - \sum_{b=2}^{n} \lfloor \frac{n}{b} \rfloor $$$

      then someone already provided the link (how to count n/b) https://codeforces.me/blog/entry/118001

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

        Can you explain the expansion of summation?

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

          let

          $$$ C = n \bmod b $$$

          then

          $$$ \lfloor \frac{n}{b} \rfloor = \frac{n - C}{b} $$$

          well if you don't understand how to get rid of the first summation then think about remainder

          $$$ \sum_ {c=1}^{b-1} \lfloor \frac{n-c}{b} \rfloor = \sum_{c=1}^{C} \lfloor \frac{n}{b} \rfloor + \sum_{c=C + 1}^{b-1} (\lfloor \frac{n}{b} \rfloor - 1) $$$

          and second summation:

          we can rewrite our summation

          $$$ \sum_{b=2}^{n} C * \frac{n - C}{b} + (b - 1 - C) * (\frac{n - C}{b} - 1)$$$

          then we can expand

          $$$ \sum_{b=2}^{n} C * \frac{n - C}{b} + (n - C) - b - \frac{n - C}{b} + 1 - C * \frac{n - C}{b} + C $$$

          then we have

          $$$ \sum_{b=2}^{n} n - b + 1 - \frac{n - C}{b} $$$

          and that is

          $$$ \sum_{b=2}^{n} n - b + 1 - \lfloor \frac{n}{b} \rfloor $$$

          and finally

          $$$ n - 1 + n * (n - 1) - (2 + n) * (n - 1) / 2 - \sum_{b=2}^{n} \lfloor \frac{n}{b} \rfloor $$$
          → Reply
»
14 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

How to do G? It kept TLE on 37 and other 3 testcases.

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

Trash contest.

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

Could anyone tell me why i got 3 TLEs in G? (https://atcoder.jp/contests/abc414/submissions/67547581) I'm crazy about it.

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

    If there are negative edges, you’ll probably get TLE in those 3 cases.

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

      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

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

      thx, i'm an idiot

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

      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

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

        In short you have to use four segment trees rather than two, for:

        • boarding an eastbound train
        • getting off an eastbound train,
        • boarding a westbound train,
        • getting off a westbound train.

        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:

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

english editorial please!

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

The E problem is so nice that i only found out pretty easy after contest:(

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

Why is it downvoted ?

Thank you for editorial :) .

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

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?

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

Reply to my previous comment about E link

I used Deepseek to understand and I'm writing it here so

  1. I can understand it more deeply

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

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

.

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

I spent a lot of time on G,but spfa was hacked :(

https://atcoder.jp/contests/abc414/submissions/67562418

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

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

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

Can anyone give me the solution for G?

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

Why does this Blog get downvoted so much? Personally, I think Atcoder provides quality problems. In addition, the staffs are really friendly too.

→ Reply