AtCoder Beginner Contest 210 Announcement

Блог пользователя chokudai

Автор chokudai, история, 3 года назад, По-английски

We will hold AtCoder Beginner Contest 210.

Contest URL: https://atcoder.jp/contests/abc210
Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20210717T2100&p1=248
Duration: 100 minutes
Number of Tasks: 6
Writer: leaf1415
Tester: Nyaan
Rated range: ~ 1999

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

chokudai
3 года назад
31

Комментарии (23)

Показать архивные | Написать комментарий?

DontLookBack

3 года назад, # |

Thanks for the wonderful contest! I spent a lot of time on D. Wish I was faster with implementation skills got it in like last 2 minutes phew!

D-idea

Code

//Think simple yet elegant.
//Keep your brain open.
#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll  long long
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define pi pair<int,int>
#define pii pair<int,pi>
#define REP(i,n) for(int i=0;i<n;i++)

#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)

#define time__(d) \
    for ( \
        auto blockTime = make_pair(chrono::high_resolution_clock::now(), true); \
        blockTime.second; \
        debug("%s: %lld ms\n", d, chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - blockTime.first).count()), blockTime.second = false \
    )
struct dat{
	ll cost,x,y;
};
void run_case(){
	ll h,w,x,c;
	ll i,j;
	cin >> h >> w >> c;
	ll g[h][w];
	for(i=0;i<h;i++){
		for(j=0;j<w;++j){
			cin >> g[i][j];
		}
	}	
	ll ans = 1e18,fans=1e18;
	ll dp1[h][w],dp2[h][w];
	for(i=0;i<h;++i){
		for(j=w-1;j>=0;--j){
			if(i>0 && j<w-1){
				dp1[i][j]=min({dp1[i-1][j+1],dp1[i][j+1],dp1[i-1][j]});
				ans=min(ans,dp1[i][j]+g[i][j]+c*(i+1-j-1));
				dp1[i][j]=min(dp1[i][j],g[i][j]-c*(i+1-j-1));
			}
			if(i==0 && j<w-1){
			
				dp1[i][j]=dp1[i][j+1];
				ans=min(ans,dp1[i][j]+g[i][j]+c*(i+1-j-1));
				dp1[i][j]=min(dp1[i][j],g[i][j]-c*(i+1-j-1));
			

			}
			if(i>0 && j==w-1){
				dp1[i][j]=dp1[i-1][j];
				ans=min(ans,dp1[i][j]+g[i][j]+c*(i+1-j-1));
				dp1[i][j]=min(dp1[i][j],g[i][j]-c*(i+1-j-1));
			}
			if(i==0 && j==w-1)
				dp1[i][j]=g[i][j]-c*(i+1-j-1);
		
		}
	}

	for(i=h-1;i>=0;--i){
		for(j=w-1;j>=0;--j){
			if(i<h-1 && j<w-1){
				dp2[i][j]=min({dp2[i+1][j+1],dp2[i+1][j],dp2[i][j+1]});
				ans=min(ans,dp2[i][j]+g[i][j]-c*(i+1+j+1));
				dp2[i][j]=min(dp2[i][j],g[i][j]+c*(i+1+j+1));
			}
			if(i<h-1 && j==w-1){
				dp2[i][j]=dp2[i+1][j];
				ans=min(ans,dp2[i][j]+g[i][j]-c*(i+1+j+1));
				dp2[i][j]=min(dp2[i][j],g[i][j]+c*(i+1+j+1));
			}
			if(i==h-1 && j<w-1){
				dp2[i][j]=dp2[i][j+1];
				ans=min(ans,dp2[i][j]+g[i][j]-c*(i+1+j+1));
				dp2[i][j]=min(dp2[i][j],g[i][j]+c*(i+1+j+1));
			}
			if(i==h-1 && j==w-1)
				dp2[i][j]=g[i][j]+c*(i+1+j+1);
		}
	}
	
	cout<<ans<<"\n";
}
 
int main(){
	fast;
	int t=1;
	while(t--){
		//cout<<"Case #"<<cn<<": ";
		run_case();
		//++cn;
	}
}

→ Ответить

hbarp

3 года назад, # ^ |

Instead of making 4 cases, just make 2 cases. Lets just fix the point for which 'row' value would be bigger. The code gets a lot more simple with that.

Code

void testCase() {
    int n, m, k; cin >> n >> m >> k;
    vector<int> pmi(m + 1, inf), smi(m + 2, inf);
    int a[n + 1][m + 1];
    int ans = inf;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            pmi[j] = min(pmi[j], pmi[j - 1]);
            int c1 = a[i][j] + k * (i + j) + pmi[j];
            int c2 = a[i][j] + k * (i - j) + smi[j];
            ans = min({ans, c1, c2});
            pmi[j] = min({pmi[j], a[i][j] - k * (i + j)});
        }

        for (int j = m; j > 0; j--)
            smi[j] = min({smi[j], smi[j + 1], a[i][j] + k * (j - i)});
    }

    cout << ans;
}

→ Ответить

rkguptagkp462

3 года назад, # ^ |

A short implementation - Submission

→ Ответить

DontLookBack

3 года назад, # ^ |

How to think of short implementations faster ?

→ Ответить

rkguptagkp462

3 года назад, # ^ |

Think of some tricks to simulate many cases with some variables which you can pass in some function on basis of which it will change. Don't know to explain it better.

→ Ответить

aryanc403

3 года назад, # |

+31

How to do F?

→ Ответить

aopo

3 года назад, # ^ |

-14

→ Ответить

bjy

3 года назад, # ^ |

← Rev. 2 →

represent inputs by their prime factors
cry... edit: editorial's out, I wasn't nearly as close as I'd guessed

→ Ответить

Felerius

3 года назад, # ^ |

+15

We can reduce the problem to one big 2-SAT instance, containing one variable per card denoting which side of it we use (plus some supplementary ones).

First, we go through every possible divisor $$$d \in [2, MAX]$$$, where $$$MAX = 2 \cdot 10^6$$$, that could divide two numbers on the front side of two cards. For every $$$d$$$, we enumerate all cards $$$C_d$$$ that contain a number divisible by $$$d$$$ on either side. We can to this in $$$\mathcal{O}(MAX \log MAX)$$$ if we save every card containing a number for every number. The total size of all $$$C_d$$$ should be roughly $$$4 \cdot 10^6$$$ if we use the $$$\sqrt[3]{n}$$$ approximation for the number of divisors of some $$$n$$$.

Now for every $$$d$$$, we check whether there exists a card containing numbers divisible by $$$d$$$ on both sides. If thats the case, we go through we all other cards in $$$C_d$$$ and force them be flipped to the side not divisible by $$$d$$$ using a clause like $$$(x \lor x)$$$ or $$$(\overline{x} \lor \overline{x})$$$ (if there is another card with both sides divisible by $$$d$$$, we can immediately output no).

If there is no card with both sides divisible by $$$d$$$, we want to allow at most one card in $$$C_d$$$ to be flipped to its divisible-by-$$$d$$$ side. For that there is a construction using about $$$3 \lvert C_d \rvert$$$ clauses and $$$\lvert C_d \rvert$$$ supplementary variables. KACTL's 2-SAT code contains an implementation for it. I've always used it without figuring out why it works, but it probably becomes obvious if you spend some time playing around with it on paper. Solving the 2-SAT instance then just requires the standard algorithm using strongly-connected components.

→ Ответить

dnshgyl21

3 года назад, # ^ |

For the last paragraph, you mentioned I used edges in a kind of prefix and suffix order a little bit similar to this Problem.

Is there any other nice trick to handle these types of implications? mine implementation was messy.

→ Ответить

madlogic

3 года назад, # |

How to solve E?

→ Ответить

bane

3 года назад, # ^ |

Make pair of $$$Ai$$$ and $$$Cost$$$. Sort on Cost in ascending order, if cost is same compare gcd($$$Ai$$$,$$$N$$$). Calculate final answer by iterating on the vector pair and adding maximum possible edges with the current cost (edges = $$$N$$$ — $$$gcd(N-Ai)$$$). Update $$$N$$$ = $$$gcd$$$ after every iteration. If we reach $$$n$$$ = 1, i.e we made N-1 edges, break.

→ Ответить

TimeTraveler

3 года назад, # |

My code for D was failing for only 3 testcases for some reason. Can someone tell what is wrong with my code? Submission Link

Code

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

const int N = 1e3+69;
int A[N][N], dp[N][N];

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int h, w, c;
    cin >> h >> w >> c;

    for(int i = 1; i <= h; i++)
    for(int j = 1; j <= w; j++)
        cin >> A[i][j];
    
    int ans = dp[1][1] = 1e18;
    
    for(int i = 2; i <= h; i++)
        dp[i][1] = c + min(dp[i - 1][1] + A[i][1] - A[i - 1][1], A[i][1] + A[i - 1][1]),
        ans = min(ans, dp[i][1]);
    for(int j = 2; j <= w; j++)
        dp[1][j] = c + min(dp[1][j - 1] + A[1][j] - A[1][j - 1], A[1][j] + A[1][j - 1]),
        ans = min(ans, dp[1][j]);

    for(int i = 2; i <= h; i++)
    for(int j = 2; j <= w; j++)
    {
        dp[i][j] = c + min(dp[i - 1][j] + A[i][j] - A[i - 1][j], A[i][j] + A[i - 1][j]);
        dp[i][j] = min(dp[i][j], c + min(dp[i][j - 1] + A[i][j] - A[i][j - 1], A[i][j] + A[i][j - 1]));
        ans = min(ans, dp[i][j]);
    }
    cout << ans;
}

→ Ответить

KartikModi

3 года назад, # ^ |

← Rev. 2 →

→ Ответить

madlogic

3 года назад, # ^ |

← Rev. 3 →

Try this case

2 2 1
13 1
1 13

The answer should be $$$4$$$. $$$(1, 2)$$$ and $$$(2, 1)$$$

I also made the same mistake, you can correct it by rotating the grid clockwise once and repeating the dp.

→ Ответить

TimeTraveler

3 года назад, # ^ |

thanks

→ Ответить

nichke

3 года назад, # ^ |

I made the same mistake 5 times :(

We are only checking for (i, j) and (i', j'), such that (i, j) is up and left when compared to (i', j'). There need to be two DP checks for both directions.

→ Ответить

monna4335

3 года назад, # |

difficulty gap between C & D is soo high!

→ Ответить

ZergTricky

3 года назад, # |

Wrote some hell on D, E was easier

→ Ответить

kristja6

3 года назад, # |

+19

A different idea to solve D: Let's solve it as a shortest paths problem. The graph will have a start vertex, which is connected to some randomly chosen tiles in the grid. The rest of the tiles is connected to the end vertex. Then search for the shortest path from start vertex to end vertex.

More concretely, from the start vertex make an edge of length $$$A_{i,j}$$$ to some pairs $$$(i, j)$$$ and from some pairs $$$(i', j')$$$ have an edge of length $$$A_{i',j'}$$$ to the end vertex. Also connect each $$$(i, j)$$$ to neighboring tiles ($$$(i + 1, j), (i - 1, j), (i, j+1), (i, j-1)$$$) with length $$$C$$$.

We set the probability of being connected to the start vertex as 0.5. The probability that the optimal pair has one vertex connected to the start and the other to the end is also 0.5. So if we repeat this whole algorithm $$$k$$$ times, the probability that we missed the optimal pair is just $$$2^{-k}$$$. Admitedly, this has a worse complexity than the solution in the editorial, $$$O(WH * log(WH) * k)$$$

→ Ответить

hardy_9795

3 года назад, # |

Can someone explain problem E solution. I am not able to understand how they are calculating the number of connected components after each operation in the editorial.

→ Ответить

SkyDreams

3 года назад, # ^ |

→ Ответить

sixth.sense1729

3 года назад, # |

← Rev. 2 →

Can anybody take a look at my code!? This is a O(H * W * log(H + W)) solution, but getting TLE on few cases. Is there a way to make it more efficient?

Here's my Code.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll mn(vector<vector<ll>> &grid, ll c) {
	int h = grid.size(), w = grid[0].size();
	set<pair<ll, pair<int, int>>> val;
	for (int i = 0; i < h; i++)
		for (int j = 0; j < w; j++)
			val.insert({grid[i][j] + c * (i + j), {i, j}});
	int i = 0;
	vector<pair<int, int>> q = {{0, 0}};

	ll mn_poss = 1e15;
	int l = h + w - 1;
	while (i < l) {
		vector<pair<int, int>> temp;
		if (q[0].first < h - 1)
			temp.push_back({q[0].first + 1, q[0].second});
		for (int j = 0; j < q.size(); j++) {
			val.erase({grid[q[j].first][q[j].second] + c * i, {q[j].first, q[j].second}});

			int m = q[j].first, n = q[j].second;
			if (n < w - 1)
				temp.push_back({m, n + 1});
		}

		while (!q.empty() && !val.empty()) {
			auto mn = q.back();
			q.pop_back();
			auto xx = *val.begin();
			int u = mn.first, v = mn.second;
			int w = xx.second.first, x = xx.second.second;
			mn_poss = min(mn_poss, grid[w][x] + grid[u][v] + c * (abs(w - u) + abs(x - v)));
		}
		q = vector<pair<int, int>>(temp.begin(), temp.end());
		i++;
	}
	return mn_poss;
}

vector<vector<ll>> trans(vector<vector<ll>> &grid) {
	int m = grid.size(), n = grid[0].size();
	vector<vector<ll>> ans(n, vector<ll>(m));
	for (int i = 0; i < m; i++)
		for (int j = 0; j < n; j++)
			ans[j][m - i - 1] = grid[i][j];
	return ans;
}

void solve() {
	int h, w;
	ll c;
	cin >> h >> w >> c;
	vector<vector<ll>> grid(h, vector<ll>(w));
	for (auto &it : grid)
		for (auto &jt : it) cin >> jt;
	ll x = mn(grid, c);
	grid = trans(grid);
	ll y = mn(grid, c);
	cout << min(x, y) << "\n";
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t = 1;
	while (t--) {
		solve();
	}
	return 0;
}

→ Ответить