Want to solve for ABCDE!!

Hope I can AC ABCDE. :)

Hopefully I will bring my A game today and become cyan

Hope to place in Top 500

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:)

atcoder orz

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

Participated in ABC for the first time!

GOOD LUCK!!!

Want to solve for F!!!

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

F is way too easy for 525 points.

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. :/

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.

Are centroid solutions passing in problem G?

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 :

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.

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

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.

for (int i = 0; i < m; i++) {
    long long total = a[b[i]], equal_split = total / n, remain = total % n;
    a[b[i]] = 0;
    for (int j = 0; j < n; j++) {
        a[j] += equal_split;
    }
    for (int j = (b[i] + 1) % n; remain > 0; j = (j + 1) % n) {
        a[j]++;
        remain--;
    }
}

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.

long long op(long long a, long long b) { return a + b; }

long long e() { return 0; }

class BlackBox {
  public:
    segtree<long long, op, e> *diff_array;
    BlackBox(int n) { diff_array = new segtree<long long, op, e>(n); }

    void range_inc(int l, int r, long long delta) {
        diff_array->set(l, diff_array->get(l) + delta);
        diff_array->set(r + 1, diff_array->get(r + 1) - delta);
    }

    long long point_query(int idx) {
        // Atcoder's segtree prod function has range [l, r).
        // Hence, we add + 1 to make inclusive range.
        return diff_array->prod(0, idx + 1);
    }
};

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.

BlackBox box(n + 5);
for (int i = 0; i < n; i++) {
    box.range_inc(i, i, a[i]);
}
for (int i = 0; i < m; i++) {
    long long total = box.point_query(b[i]), equal_split = total / n,
                remain = total % n;
    box.range_inc(b[i], b[i], -total);
    box.range_inc(0, n - 1, equal_split);

    int start = (b[i] + 1) % n;
    if (start + remain - 1 < n) {
        box.range_inc(start, start + remain - 1, 1);
    } else {
        box.range_inc(start, n - 1, 1);
        remain -= (n - 1 - start + 1);
        box.range_inc(0, 0 + remain - 1, 1);
    }
}

for (int i = 0; i < n; i++) {
    cout << box.point_query(i) << " ";
}
cout << endl;
}

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.

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

Two minutes more please :'(

Any Hint for $$$F$$$?

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

Anyone tried to solve F as a computational geometry problem?

How to do B? I did it for half an hour but I can't solve 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?

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/

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

• First & Second -> Cake walk
• Third -> DP.
• Fourth -> Dijkstra’s (I wasn't able to figure out during the contest)

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

A-F easy, but G too hard.

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

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

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

Deleted

Why my code for E giving TLE??

Your code here...
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
vector<ll> t,lazy,a;
vector<bool> marked;
 
void build(vector<ll> a, ll v, ll tl, ll tr) {
    if (tl == tr) {
        t[v] = a[tl];
    } else {
        ll tm = (tl + tr) / 2;
        build(a, v*2, tl, tm);
        build(a, v*2+1, tm+1, tr);
        t[v] = 0;
    }
}

void update(ll v, ll tl, ll tr, ll l, ll r, ll add) {
    if (l > r)
        return;
    if (l == tl && r == tr) {
        t[v] += add;
    } else {
        ll tm = (tl + tr) / 2;
        update(v*2, tl, tm, l, min(r, tm), add);
        update(v*2+1, tm+1, tr, max(l, tm+1), r, add);
    }
}

ll get(ll v, ll tl, ll tr, ll pos) {
    if (tl == tr)
        return t[v];
    ll tm = (tl + tr) / 2;
    if (pos <= tm)
        return t[v] + get(v*2, tl, tm, pos);
    else
        return t[v] + get(v*2+1, tm+1, tr, pos);
}
 
int main(){
    fast;
    ll t1;
    t1=1;
    while(t1--){
        ll n,m;
        cin>>n>>m;
        a.clear();
        a.resize(n+1);
        for(ll i=1;i<=n;i++) cin>>a[i];
        t.clear();
        lazy.clear();
        t.resize(4*(n+1));
        lazy.resize(4*n);
        marked.resize(4*n,false);
        build(a,1,1,n);
        while(m--){
            ll ind;
            cin>>ind;
            ind++;
            ll x=get(1,1,n,ind);
            ll y=x;
            ll diff=(n-ind);
            if(diff!=0){
                update(1,1,n,ind+1,n,1);
                y-=diff;
            }
            ll val=(y/n);
            if(val!=0){
                update(1,1,n,1,n,val);
                y-=n*val;
            }
            if(y!=0){
                update(1,1,n,1,y,1);
            }
            update(1,1,n,ind,ind,-x);
        }
        for(ll i=0;i<n;i++) cout<<get(1,1,n,i+1)<<" ";
    }
}

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

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

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

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?

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

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.