atcoder_official's blog

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

We will hold AtCoder Beginner Contest 395.

We are looking forward to your participation!

  • Vote: I like it
  • +41
  • Vote: I do not like it

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

I am looking forward to it.

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

The E also became easier and easier.

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

hope i can become green in this

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

SpeedCoder 4 times in a row...

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

Is D meant to be solved via DSU?

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

Can anyone please help me, my code for E is ac in 69 tests cases and fails in one test case. My code

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

D and E were good problems.

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

The one who passed 2 problems in 48 seconds might use AI. How can he type so fast!???

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

Can anyone help me with D. Below is my submission https://atcoder.jp/contests/abc395/submissions/63289001

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

    You can't iterate in the whole nest list and modify the pigeon nest_id. It'll lead to TLE, you need to think about how do you manage the swapping of nests. Hashmaps will certainly help.

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

      you suggest I use 2 hashmaps? one for nest to bird mapping and one for bird to nest mapping

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

        Yes, I can post my solution, if needed. But the main idea is using 2 hashmaps. In fact I used 3 hashmaps, but probably 2 should be enough.

        I used one hashmap for mapping notional_nest_id and one for mapping real_nest_id. And the a map for mapping pigeon_id to notional_nest_id.

        And you'd have to think on where to use which. But this should give you an idea on how to move forward.

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

    You just need to maintain the physical location of the pigeon, the number corresponding to the nest at location i, and the location of the nest corresponding to the number i

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

Very good problems! They are not too hard to solve but require a little creative thinking. But I can't solve problem G at all...

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

Can anyone help me on how to solve the E.

My logic: First traverse (BFS) the reverse graph and find the cost for each node from root(1) to each node. And then traverse (BFS) the normal graph and check at every node, the current cost + cost to reach nth node in reverse graph from this node.

#include <bits/stdc++.h>

#define el cout << '\n'
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pii pair<int, int>
#define ll long long int

using namespace std;

vector<ll> level;
inline ll bfs(vector<vector<int>> &adj, int n) {
	int src = 1, trgt = n;
	queue<int> q;
	vector<bool> vis(n+1, false);
	q.push(src);
	vis[src] = true;
	level.resize(n+1, INT_MAX);
	level[src] = 0;
	while(!q.empty()) {
		int p = q.front(); q.pop();
		for(int &node: adj[p]) {
			if(vis[node]) continue;
			level[node] = level[p] + 1;
			vis[node] = true;
			q.push(node);
		}
	}
	return level[trgt];
}

int main() {
	fast_io;
	int n, m;
	ll x;
	cin >> n >> m >> x;
	vector<vector<int>> adj(n+1), adj1(n+1);
	for(int i = 0; i < m; ++i) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj1[v].push_back(u);
	}
	ll cost1 = bfs(adj1, n) + x, cost2 = INT_MAX;
	queue<int> q;
	vector<bool> vis(n+1, false);
	q.push(1);
	vector<ll> level1(n+1, INT_MAX);
	level1[1] = 0;
	while(!q.empty()) {
		int p = q.front(); q.pop();
		for(int &node: adj[p]) {
			if(vis[node]) continue;
			level1[node] = level1[p] + 1;
			if(level[n] != INT_MAX and level[node] != INT_MAX) {
				ll rev_cost_from_here = level1[node] + (level[n] - level[node]) + x;
				cost2 = min(cost2, rev_cost_from_here);
			}
			vis[node] = true;
			q.push(node);
		}
	}
	cost2 = min(cost2, level1[n]);
	cout << min(cost1, cost2); el;
    return 0;
}
→ Reply
  • »
    »
    14 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    In fact, you can flip the graph more than two times. But it seems like your program only considerd two flips. Hack : 12 13 1 2 1 12 3 2 3 1 4 4 5 5 6 6 7 7 2 3 8 8 9 9 10 10 11 11 12

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

    I hope my code can help you :)

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

finally an ABC with a good D which isn't a speedcoder problem.

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

    First time saw problem D, yeah it's kinda hard.

    But after solving it, I feel like it can qualify as speedcoder problem.

    → 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

how i do a good upsolving ? i am beginner , so i am confused

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

    Just try to a moment till you can say to yourself that yeah I give up now time to look at the editorials :)

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

I dont get it how, or why, G works.

What am I doing? I do a Floyd-Warshal on the whole graph to get the actual minimized cost of each edge. Then, on each query, I create the MST of the subgraph consting of the vertices 0..k, plus s and t.

But this does not give the right result. Can somebody explain?

Here is my notworking submission

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

    After floyd-warshal, the path with the minimum distance between 2 different pairs of vertices could include the same edge of the orignal graph.
    So, when you just add all the distances up, you may count the same edge multiple times.

    Countercase

    Expected output: 3
    Your output: 4

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

How to do F ? Can someone explain ?

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

Please update the editorial, I want to see how to solve G :)

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

    I'll explain my solution to the problem. The idea is to generalize the solution to the original problem of finding the Minimum Steiner Tree.

    Minimum Steiner Tree

    Beforehand we compute the shortest path between every pair of nodes using Floyd-Warhsall, so we have access to the shortest path between every pair of nodes in $$$O(1)$$$.

    Then we can solve this using dynamic programming, representing each state as follows:

    $$$dp[mask][u]$$$ represents the minimum cost of a subtree that spans all nodes in $$$mask$$$ and includes $$$u$$$ as an arbitrary additional node.

    Each mask represents a subset of the special nodes we want to have in the final tree, and $$$u$$$ is any node in the graph (possibly in $$$mask$$$). The solution to the problem is the minimum over all nodes $$$u$$$ of $$$dp[FULL][u]$$$ where $$$FULL$$$ is the mask representing the set with all special nodes in it.

    We can compute each state in order of $$$mask$$$ (i.e when we are solving a particular mask, we should have solved all previous masks before). When computing the problem for a fixed mask: - if the mask is empty the cost is 0, since the tree consist of only one node ($$$u$$$) - if the mask has one element the cost is $$$dist(s, u)$$$, where $$$s$$$ is the node in the mask, and $$$u$$$ the other node (possibly the same). In this case the tree is just the shortest path connecting both nodes. - The case with at least two elements is the more interesting one.

    If the mask has at least two elements, then in any optimal tree to this subproblem, exists a node $$$v$$$ such that removing the edges incident to $$$v$$$ will split the tree into multiple components where no component has all special nodes.

    The intuition behind this argument is that, either $$$u$$$ itself is on the optimal tree, which means it is in the path between two special nodes, or is a leaf in the tree, and by moving in the direction of any special node we will find the node $$$v$$$ with the desired properties.

    Given that we know this node $$$v$$$ exists, we try each node in the graph as if it were the node $$$v$$$, and then try every proper non empty $$$submask$$$, ending at $$$v$$$

    $$$dp[mask][u] = min_{submask ⊂ mask} dp[submask][u] + dp[mask \ submask][u]$$$

    This way we find the minimum cost tree with with nodes in $mask$ and a node $$$u$$$ in the path between two special nodes. Now we need to compute the case where the node $$$u$$$ is a leaf outside of the path. We can compute it using a variation of shortest path, using multiple sources and multiple destinations. It is equivalent to compute dijkstra in a graph with a virtual node that can reach any node $$$u$$$ with cost $$$dp[mask][u]$$$ and then can move using the regular edges of the graph.

    The overall cost of computing the first part is $$$O(3^k * n)$$$ and the cost for the second part is $$$O(2^k \cdot n^2)$$$.

    Minimum Steiner Tree 2

    We now extend these ideas to solve the given problem. The previous dynamic programming is already quite rich, it returns the minimum tree with all special nodes plus an extra arbitrary node. Now we are interested in the case of having two extra arbitrary nodes, which indicates we want to compute the following dynamic programming:

    $$$dp[mask][u][v]$$$ represents the minimum cost of a subtree that spans all nodes in $$$mask$$$ and include $$$u$$$ and $$$v$$$ as arbitraries additional nodes.

    Where $$$u$$$ and $$$v$$$ could be the same and could be in $$$mask$$$. Again we fill the dynamic programming in a similar way. - If the mask is empty then the minimum cost is the cost of the shortest path between $$$u$$$ and $$$v$$$. - If the mask has one node $$$s$$$, then we should find the Steiner node, this is a node that minimizes the sum of the distances to $$$u$$$, $$$v$$$ and $$$s$$$. This can be done in $$$O(n^3 \cdot k)$$$ by trying all candidates. - Otherwise we are again in the interesting case.

    Now we need a similar observation than the one we need before. We will initially compute correctly $$$dp[mask][u][v]$$$ for pair of nodes $$$u$$$ and $$$v$$$ such that they are part of an optimal tree, and then we can extend that later to every pair of nodes by moving through edges using dijkstra with the virtual node as we did before.

    By removing incident edges to the nodes $$$u$$$ and $$$v$$$ we divide the tree in components, such that some components are a subtree of node $$$u$$$ , some are a subtree of node $$$v$$$ and potentially one of them is in the path between $$$u$$$ and $$$v$$$. More importantly there should be at least one special node in the subtree of $$$u$$$ and at least another special node in the subtree of $$$v$$$. Only in this case $$$u$$$ and $$$v$$$ are part of the optimal tree for the given $$$mask$$$. Given this observation we can iterate through all disjoint submask A, B, C, such that A and C are the special nodes in the subtrees of $$$u$$$ and $$$v$$$ respectively, and $$$B$$$ are the special nodes in the path between $$$u$$$ and $$$v$$$. Notice A, B, C should be a partition of $$$mask$$$, and $$$A$$$ and $$$C$$$ shouldn't be the whole mask. We can iterate through all these masks in $$$O(4^k)$$$, for an overall complexity of $$$O(4^k \cdot n^2)$$$

    Using dijkstra to extend the found values to every possible pair has cost $$$O(2^k \cdot n^3 \cdot \log n)$$$

    → Reply