atcoder_official's blog

By atcoder_official, history, 11 days ago, In English

We will hold KAJIMA CORPORATION CONTEST 2024(AtCoder Beginner Contest 340).

We are looking forward to your participation!

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Want to solve for ABCDE!!

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope I can AC ABCDE. :)

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hopefully I will bring my A game today and become cyan

»
11 days ago, # |
  Vote: I like it -6 Vote: I do not like it

Hope to place in Top 500

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hopefully that I can solve all the problems like last time:)

ps:last time I participate in ABC I become 1600+ which is 2 Kyu:)

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

atcoder orz

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I want my name to change color from brown to green.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Participated in ABC for the first time!

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

GOOD LUCK!!!

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Want to solve for F!!!

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello everyone! Did everyone AC the first two problems? Go!

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

F is way too easy for 525 points.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    did you know about linear diophantine equations before the contest or you understood it during the contest ?

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It's a pretty basic concept.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the C problem based on? How to solve it? Does it involve some observation? Can't use DP because of the constraint on n but I couldn't solve it at all throughout the contest. :/

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I solved using dp. Use map for memoisation

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Print out the first 20-ish answers, you will spot the pattern

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Use DFS on states that a number meet until get to 1. Don't forget to save a state so you don't meet it again.

  • »
    »
    10 days ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

  • »
    »
    10 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    Spoiler
    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I get WA,what`wrong with it?

      Spoiler
      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        log2(n) is creating problem as the constraints are upto 1e17.

        log(pow(2,56)-1) = 56 but actually it should be 55.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    First, find out the leftmost set bit of n, i.e., basically log2(n). Let's say it is x, so we add x times n to our ans and then calculaterem, i.e., n-(1<<x), and then addrem*2 to our ans.

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I tried this as well but it didn't pass for the 1e17 case. It passed for tbe rest so I was convinced that this is it but was very surprised at the end. I didn't use built-in C++ log function either. Can you share implementation if you did that?

      • »
        »
        »
        »
        10 days ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it
        int main(){
            in_trice
        
        ll n;
        cin>>n;
        ll ans=0;
        
        int x=0;
        
        ll tmp=n;
        
        while(tmp>1){
            tmp/=2;
            x++;
        }
        // cout<<x<<endl;
        // cout<<x<<endl;
        ans+=(x)*1LL*n;
        
        ll rem=n-(1LL<<x);
        // cout<<rem<<endl;
        ans+=rem*1LL*2;
        
        cout<<ans<<endl;
        return 0;
        }
        
»
10 days ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve F?

I know that the third point of the triangle should be on a line parallel with (0, 0), (X, Y) line. and we can find the line format(ax+b) but I don't know how to find an integer point on this line.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +11 Vote: I do not like it
    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can we use this prewritten code during the contest ?

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Yes

      • »
        »
        »
        »
        10 days ago, # ^ |
        Rev. 2   Vote: I like it +1 Vote: I do not like it

        You don't need the whole code. It's just a single run of extended Euclid's algorithm.

        def extended_gcd(a, b):
        	if b==0: return a, 1, 0
        	g, x1, y1 = extended_gcd(b, a%b)
        	return g, y1, x1-(a//b)*y1
        

        After that you need to deal with a few cases (positive/negative numbers + value of gcd). Took me quite a while to figure out how to cover it. An example of a task that is a good intuition builder for extended_gcd.

»
10 days ago, # |
  Vote: I like it +13 Vote: I do not like it

Are centroid solutions passing in problem G?

  • »
    »
    10 days ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    What is the idea for the centroid solution? Is there a reason the centroid solution should not pass?

    My centroid solution doesn't even pass the samples.

»
10 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

My thought process for E: Mancala 2.

Usually in these type of problems, people struggle with off-by-one errors. A clever way to avoid these bugs is to rely on Euclid's Divison Lemma. It says that ANY number can be written as :

$$$ num = div *q + rem $$$

where $$$div$$$ is read as Divisor and $$$0 \leq rem < div$$$. But that's not all, you can quickly find out $$$q$$$ and $$$rem$$$ via these equations.

$$$ \begin{align} q &= num / div \\ rem &= num \% div \end{align} $$$

Suppose we are performing the operations for the the box with $$$num$$$ balls. Then,

$$$ \begin{align} num &= n*q + rem \\ q &= num / n \\ rem &= num \% n \end{align} $$$

Now, it's easy to see that EVERY box will receive $$$q$$$ balls in Phase 1. And in phase 2, a total of $$$rem$$$ boxes would receive one ball each.

Code

Submission

Now, how do we optimize this. Notice that Phase 1 is simply adding an increment $$$q$$$ to all elements of a subarray. While phase 2 is adding $$$1$$$ to possibly 2 subarrays (a prefix and a suffix). Hence, we need a data structure that can support range increment and point query.

Atcoder's library provides a data structure that can support range sum and point update queries. Now, how do we use it for this scenario? We can do so by simulating difference array. Some people like to maintain the difference array in the segment tree on the fly, however, I personally write a wrapper around it to make the code more readable. A sample implementation can look like.

Code

Finally, we can use our custom data structure to perform range updates. The only challenge is to handle the updates via $$$rem$$$. But notice that it will always be a suffix and prefix update. Hence, you can first update the suffix, and if there are still some balls remaining, you can do a prefix update.

Code

Submission

I am not sure if segment tree was an overkill for this problem. If it was, I'd love to know your alternate solutions.

»
10 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For problem C, AC × 10, WA × 1.. What's wrong with this?

#include <iostream>
#include <cmath>

using namespace std;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    long long n; cin >> n;
    long long on = n;

    long long e = 1; long long add = 3;
    long long sum = 0;
    while (n > 2) {
        sum += add * powl(2, e);
        ++add; ++e;
        n -= powl(2, e);
    }
    sum += (((long long)log2(on))+2) * ((on) - ((long long)powl(2, e)));
    cout << sum+2;
}
»
10 days ago, # |
Rev. 2   Vote: I like it +17 Vote: I do not like it

Two minutes more please :'(

Screen-Shot-2024-02-10-at-17-43-18

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Any Hint for $$$F$$$?

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    $$$S = \dfrac{|AY-BX|}{2}$$$
    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I know till that , tell me more

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        And that's all??

        Cant you solve $$$ax+by = \gcd(a,b)$$$??

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Area = |x1(y2 — y3) + x2(y3 — y1) + x3(y1 — y2)| / 2

        now putting Area=1 and (x1,y1)=0,(x2,y2)=(X,Y) and let (x3,y3)=(x,y)=(A,B)

        then 2=|Xy-xY|.

        so possible answer is Xy-xY=2 or Xy-xY=-2. you have given X and Y and find (x,y) which satisfied any of above 2 equation which is standered problem

        • »
          »
          »
          »
          »
          10 days ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          yeah I went that far but just couldn't solve the standard prbl, thanks for help

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Any ideas about D? I solved it using dfs but get TLE :(

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Dijkstra

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Oh, that's really easy after you mentioned it... Why didn't I think about that before...

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        This is my first time doing CP. When doing LeetCode problems, I always use SPFA, so I used SPFA again, but TLE'ed :( I fixed it to use Dijkstra, but ran out of time...

        • »
          »
          »
          »
          »
          10 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          In China there's a saying, "About SPFA: it died." That means SPFA is going to be hacked by some evil problemsetters.

»
10 days ago, # |
  Vote: I like it -8 Vote: I do not like it

Anyone tried to solve F as a computational geometry problem?

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do B? I did it for half an hour but I can't solve it.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In the editorial of Question C There is this one-line return m[N] = f(N / 2) + f((N + 1) / 2) + N; I had written the same program as the editorial but with the above line changed to

Your code here...
long long a = floor(n * 1.0 / 2), b = ceil(n * 1.0 / 2);
return dp[n] = n + dfs(a) + dfs(b);

But I got WA on submission. Can you tell me why my method was incorrect?

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think the reason is the precision error in floor or ceil function because of double type.

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks. I searched online and all the answer that I came across was related to that only.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

For D: Super Takahashi Bros, if you were not able to intuitively figure out why Dijkstra would work for the problem, I've written a tutorial on how to think of Dijkstra problems via BFS (which is usually easier to reason about).

https://cfstep.com/training/tutorials/graphs/dijkstra-is-bfs-in-disguise/

»
10 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone please help me figure out why my $$$O(n \log^2 n)$$$ small-to-large merging TLEs only on star graphs?

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    move(vs.begin(), vs.end(), back_inserter(lhs->raw[k]));

    You should use small to large here too.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it
  • First & Second -> Cake walk
  • Third -> DP.
  • Fourth -> Dijkstra’s (I wasn't able to figure out during the contest)
  • »
    »
    10 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Fifth -> Segment tree :)

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Third is not dp

        	long mul = 1, ans = 0
        	while(mul * 2 <= n){
        		mul *= 2;
        		ans += n;
        	} 
        	out.println(ans+(n-mul)*2);
    
    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The most straightforward solution is still DP-ish

      ll a(ll n) {
          if (memo.count(n)) return memo[n];
          if (n == 1)
              return 0;
          else
              return memo[n] = n + a(hfloor(n)) + a(hceil(n));
      }
      

      You need to implement floor and ceil yourself though. Using floating point arithmetics will fail.

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I also did dp

      • »
        »
        »
        »
        10 days ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        Why are u using floor and ceil? Simply u can do n/2 and (n+1)/2

        • »
          »
          »
          »
          »
          10 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I did implement them as such -- after finding out that floor and ceil breaks due to precision errors

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Here is the DP Solution.

      ll solve(ll n, unordered_map<ll, ll>&dp){
          if(n == 1) return 0;
          if(dp[n] > 0) return dp[n];
          return dp[n] = n + solve(n/2, dp) + solve((n+1)/2, dp);
      }
      
»
10 days ago, # |
  Vote: I like it -8 Vote: I do not like it

I think intended solution of $$$F$$$ mayn't be linear diophantine otherwise why would they say that the area has to be 1 not any other integer

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The official editorial does look like a exgcd though. That $$$1$$$ is used to add to the complexity I believe, so you can't just use the results from exgcd.

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      But why it does not use a uncertain number like $$$S$$$ which is inputed?

      • »
        »
        »
        »
        10 days ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        maybe to confuse the participants to look for observations rather than googling standard solution

        other possibility is they rushed problem setting that's why avoided extra input constraint

»
10 days ago, # |
  Vote: I like it +2 Vote: I do not like it

A-F easy, but G too hard.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me how can I see the test cases of some problem at atcoder?

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please help me understand why my code is giving RE for just 1 test case of Problem D. All other test cases are AC.

#include <bits/stdc++.h>
using namespace std;

#define int long long

int32_t main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	int n;
	cin >> n;

	vector<vector<pair<int, int>>> v(n);

	for (int i = 0; i < n; i++)
	{
		int a, b, x;
		cin >> a >> b >> x;
		x--;
		v[i].push_back({a, i + 1});
		v[i].push_back({b, x});
	}

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	vector<int> dist(n, LONG_MAX);
	vector<bool> visited(n, false);

	pq.push({0, 0});
	dist[0] = 0;
	while (!pq.empty())
	{
		pair<int, int> p = pq.top();
		pq.pop();

		int x = p.second;

		if (visited[x])
		{
			continue;
		}
		// cout << "reached\n";
		visited[x] = true;

		// for (auto r : v[x])
		// {
		// 	cout << r.first << " " << r.second << '\n';
		// }

		for (int i = 0; i < v[x].size(); i++)
		{
			int to = v[x][i].second;
			int weight = v[x][i].first;
			if (dist[x] + weight < dist[to])
			{
				dist[to] = dist[x] + weight;
				pq.push({dist[to], to});
			}
		}
	}

	cout << dist[n - 1];
}

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem G can be solved using small to large merging. My submission

»
10 days ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Deleted

»
10 days ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Why my code for E giving TLE??

code
»
10 days ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

Yay, I first time solved problem G by myself without using hints (after contest though). This time it is quite simple. Usually it requires some strange not widely known theorems, but this one didn't required anything except dfs and simple combinatorics.

My solution.

Solve for each color independently. Solve first this simple task: there are vertices of only one color. We need to calculate number of subgraphs-trees (How to call subgraph, which is a tree, actually?). Let $$$dp[v]$$$ is the number of subgraph-trees, which are in subtree of $$$v$$$ and have $$$v$$$ in them. Then $$$dp[v] = (dp[c_1] + 1) \cdot (dp[c_2] + 1) \cdot \dots $$$, where $$$c_i$$$ are children of $$$v$$$. And the answer is $$$res = dp[1] + dp[2] + \dots$$$.

Now back to full problem. Can we for every color just create a graph with edges $$$u-v$$$ if $$$u$$$ is lowest ansestor of $$$v$$$ with the same color and then run the same algorithm? Well, not really. There can be a situation, when two vertices of some tree have $$$lca$$$ of some othere color. Then path between them will not be calculated. How to fix it? Let's just add all those $$$lca$$$ to the tree and do the same. There are not many $$$lca$$$ and to get them all, we can build an euler tour on vertices of this color and add $$$lca$$$ for every two adjacent vertices.

How the $$$dp$$$ changes? Now we have some additional fictitious vertices $$$v$$$, which have other color. For them we simply do two things. First, $$$dp[v] -= 1$$$, because there is no subgraph-tree with only this vertice. There are also no subgraph-trees, for which $$$v$$$ is the root, but we can use them in upper subtrees, so we need to pass them up. So, second, for such $$$v$$$ do $$$res -= dp[c_1] + dp[c_2] + \dots$$$, where $$$c_i$$$ are children of $$$v$$$.

»
10 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For G we don't need stack to find the parents, if we sort the array of vertices again based on pre-dfs order (after adding LCAs) then for each $$$0 < i$$$ we have $$$LCA(x_{i-1}, x_i) = p[x_i]$$$ where $$$p[x]$$$ is parent of vertex $$$x$$$.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I can't find the testcases for ABC340 on dropbox, there's only upto ABC335. Do anyone know how to find?

»
9 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

One Python Problem for the task D

I tried to construct the graph structure with dictionary but failed in 7 cases. But if I changed to the list without any other changes in the algorithm, i got AC.

Here are my codes different from 'list' version:

graph = {i: {} for i in range(1, n+1)}

for i in range(n-1):

    a, b, x = map(int, input().split())

    graph[i+1][i+2] = a  

    graph[i+1][x] = b

and the code using in Dijkstra algorithm:

for next, weight in graph[cur].items():

Can someone teach me why I should use list instead of dictionary?

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you tell me why I am getting WA in this E solution? https://atcoder.jp/contests/abc340/submissions/50242534

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There's some bug in your segment tree template. AC submission after making the limits less restrictive (which somehow shadows the bug(?)).

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

For G: Leaf Color: I created a practice contest and blog discussing the $$$O(n)$$$ Tree DP idea for a fixed color. The editorial mentions that this is a good exercise for blue coders, so I encourage you to submit to the practice contest.