+1

hope to reach 1600+

I hope you do

me too:(

probably because of how sudden and quickly they had to create this contest

i guess they read that and did A harder than B

9:05am — 11:05 UTC (Im sleeping)

12:00pm — 2:00pm UTC (Im still sleeping)

LETS GO!!!!!

trying to use gpt for problem C isn't a good way to cross 1350

Follow TLE Eliminators level 3, spend time reading editorials (how do the makers build up to the solution ,).will help for sure.

huh?

🗿

🗿

🗿

Wow, find a player here.

yep resubmission is penalised

the older one will get "skipped" verdict.

You can find the empty cell which will destroy the least gold, then the place around the cell will be emptied and you can place TNT next to the former cell so that it won't destroy any other gold mine. It can be proven that after the first TNT is placed and the least gold is destroyed, the remaining gold can be all mined.

Apparently, 2D prefix sum. It took a good amount of time to figure that out. Lol.

Problem D.

I used the method of binary search for answers. I binary search for the number of games that players can win. During the inspection process, I came up with a greedy method. Suppose we win $$$x$$$ games. I divide the array $$$a$$$ into two parts, the first $$$x$$$ and the last $$$n - x$$$. Then I will exchange the minimum value of the first half and the maximum value of the second half (of course, some special cases need to be judged, such as the minimum value of the first half being greater than the maximum value of the second half). This greedy train of thought passed the pretest.

It's a pity that I can't explain its correctness very well.

#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 2e5 + 10;

void solve() {
	int n;
	std::cin >> n;

	std::vector<int> a(n + 1), b(n + 1);
	for (int i = 1; i <= n; i++) {
		std::cin >> a[i];
	}
	for (int i = 1; i <= n; i++) {
		std::cin >> b[i];
	}

	int lo = 0, hi = n;
	// lo = hi = 4;
	int ans = -1;
	while (lo <= hi) {
		int mid = (lo + hi) / 2;

		auto check = [&](int win) -> bool {
			// 1 ~ win // win + 1 ~ n
			// std::cerr << "check" << win << '\n';
			int minind = -1, maxind = -1;
			int minnum = 1e9, maxnum = 0;
			for (int i = 1; i <= win; i++) {
				if (a[i] < minnum) {
					minnum = a[i], minind = i;
				}
			}
			for (int i = win + 1; i <= n; i++) {
				if (a[i] > maxnum) {
					maxnum = a[i], maxind = i;
				}
			}

			bool isswap = 0;
			if (minind != -1 && maxind != -1 && a[minind] < a[maxind]) {
				isswap = 1;
				std::swap(a[minind], a[maxind]);
			}

			// std::cerr << minind << " " << maxind << '\n';

			int cnt = 0;
			int fsta = 1, fstb = 1;
			for (int i = 1; i <= n; i++) {
				if (a[fsta] > b[fstb]) {
					fsta++, cnt++;
				} else {
					fstb++;
				}
			}

			// std::cerr << cnt << " " << win << '\n';

			if (isswap) {
				std::swap(a[minind], a[maxind]);
			}

			return cnt >= win; 
 		};

		if (check(mid)) {
			// std::cerr << "ok" << mid << '\n';
			lo = mid + 1;
			ans = mid;
		} else {
			hi = mid - 1;
		}
	}
	std::cout << ans << '\n';
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int t = 1;
	std::cin >> t;
	while (t--) {
		solve();
	}

	return 0;
}

I think that was the point.

D, I thought of Binary Search on the Answer method.

But actually I don't need binary search, I can brute force all answer from 0 to N.

Hope it passes the system test.

nahh bro, A and B were quite easy if u can visualise stuff.

go on every empty cell and check what gold will be demolished if we detonated at that cell,subtract that from total gold in matrix as it will be always achievable after wards

so what I figured out was if you clear any square in the first move ... then you can always take all the remaining gold after that ( to prove this I drew a grid in my paper and then you can always expand the initial square one layer at a time in each direction )

so problem reduces to how many gold gets destroyed in first dynamite blast, and we would like to minimize this of course

so the problem is for the possible blast location in first move ( ie empty cells at center ) .. what blast square contains least amount of gold

this can be solved with prefix sum for 2d- grid like technique .. but you have to figure out rectangle affect by blasting at a particular location

Check which initial explosion will waste the least gold. After that, you can collect all the golds by choosing the empty cells optimally, so you don't need to check that.

Final answer is: total gold — least gold wasted from the first explosion among all possible first explosions.

Let's calculate the total gold of the initial matrix. The answer only depends on the first explosion we make. Let's try all the explosion we can make, and calculate the number of gold that is deleted after that explosion, let's denote it as x. Then the answer is maximum of all the total gold minus x over all explosion we made at the first move.

It was weirder that the constraint was the same.

Bhai the same thing is happening with me for the last 5-6 contest where i am unable to solve B but most of the time I can solve C in much lesser time.. Why is this happening?
Also can you tell what should I do to become specialist as soon as possible, i try to solve hard problems (1500-1600) and most of the time I am able to solve these in around an hour(unless its a dp problem), could you tell where I am going wrong?

In this problem, at worst you'll only need to explode 1 crowded cell (might have gold in it), but after that you have room to move and you'll never lose any gold.

i checked the constraints ~500 so i thought of dp and dfs (graph theory in general) maybe 2d prefix arrays

thats why i got stuck i forgot 2d prefix solution can exist

"Note that the game always lasts exactly n rounds."

same but i am still not able to figure it out, can you explain me?

I envy you

Maybe did not draw a lot of grids.

i think they only missed mentioning its infinite explosions, but explained later in the notes