I think they will not have time to recalculate the rating

But isn't it better to see more ad hocs, neither than more realizations and case-working etc?

Hope to see less greedy problems in the contest

Добавили в анонс.

Why?

What was the delay for?

I don't understand why do u mention it here. People anyway get to know themselves.

why

Thought it was 10 hours.

10 minutes more of being an expert :p

it happens when you are just few ratings away from expert

come on it's only ten minutes

Muahhhh, you're going down my son

...

You solved E though!

was it some sort of a pattern I was able to find some patterns but couldn't connect the dots :/

SAME BRO

How to handle the portals part ?

Was not able to think that whether we have to move from u to v or vice-versa.

Nice problem anyways.

It is always optimal to defend castle as late as possible. Do dp on what is the maximal sum of importance values if you are in castle i and have j warriors.

It is always better to defend a castle as late as possible. There will be DP[position][count of warriors]. So, while going to the next state, you assign some warriors to defend castles. Here, it's obvious that you want to defend castles with maximum importance whether you want to defend the current castle or previous castle(s) by portals.

Yes, I did it using binary search

It was

Actually, you can compute the exact formula for the number of paths on which particular x lies (it quite depends on the parity of x). Then, using this formula, you find the maximal odd x1 and the maximal even x2 for which the numbers of paths are at least k and output the maximal number among x1, x2, and 1 (because 1 is a corner case for the formula).

I had a pattern-matching closed form

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

if b == 1:
	print(a)
else:
	chopped_even = bin(b+1)[3:]
	len_even = len(chopped_even)
	best_even = ((a-int(chopped_even, 2))//(2**len_even))*2

	chopped_odd = bin(b)[2:]
	len_odd = len(chopped_odd)
	best_odd = ((a - b) // (2**len_odd))*2 + 1

	print(best_even if best_even > best_odd else best_odd)

I came up with a DP approach to problem E but I missed submitting it by a few seconds :( I wanted to become cyan but I guess, next time :"-( I am so sad rn

Anyways, did anybody else come up with a DP solution to E? I used sort of "improved" memoization. The code became kinda long though.

Suppose we have function — f(x) that gives number of paths with x inside. I just checked some values if f(n, x) >= k. What values? I dk why it works it but seems that enough to check x + dif, x — dif, where dif >= 0 and dif <= 3, and x — is prefix of binary representation of n. Submission for details

Check it out here https://codeforces.com/blog/entry/72164?#comment-564659

1-the answer exists if all elements are equal to "B" or "W" 2-(For every element equal B) start from the first index of the array and if the current element is w make it b and change the adjacent element too.If it's w don't touch it make i++.make the process until to the end of the string.At the end check whether all elements are equal to B or not. 3-do the same thing for W

Notice that the parity of the number of $$$W$$$'s and $$$B$$$'s doesn't change with each operation. Hence, if there are an odd number of $$$W$$$'s and $$$B$$$'s, it's impossible.

Now, w.l.o.g, let's assume that the number of $$$W$$$'s are even. We shall try to remove all the $$$W$$$'s. Switching $$$WB$$$ makes it $$$BW$$$. This 'shifts' $$$W$$$ to the right. Let $$$w_i$$$ be the index of the $$$i^{th}\ \ W$$$ in the string. For each odd $$$i$$$ perform operations $$$w_i\dots w_{i+1}-1$$$.Doing so 'shifts' the odd $$$W$$$'s to the even ones and removes them both.

E: path(x) contains y IFF in binary form either y or y ^ 1 is the prefix of x.

My (unimplemented) idea:

Let's count the max number of soldiers we can leave at each castle. The values will always increase. (Can be done in linear time) Suppose we have 0, 1, 1, 3, 5, 5.

From the sequence we can see that we can - leave 2 people in any of 5th or 6th castle - leave 2 people in any of 4th-6th castle - leave 1 person in any of 1th-6th castle

Then let's have a priority queue pq with the importances of the castles. - Add to pq the importances of the 5th and 6th castles + all the castles accessible from these two via portals. Take 2 best from the queue - Add the 4th castle (+ accessible from it via portals), take 2 best from the queue - add the 2nd and the 3rd (+ accessible from those), take 1 best

Return the sum of all the taken importances.

It's DP. dp[index][numWarriors] = optimum value when you are starting from index = index with numWarriors.

Check solution to E here https://codeforces.com/blog/entry/72164?#comment-564659

when the schools place is (x,y) the place for the tent must be (x+1,y) or (x,y-1) or (x-1,y) or (x,y+1)

It is always better to defend a castle as late as possible. There will be DP[position][count of warriors]. So, while going to the next state, you assign some warriors to defend castles. Here, it's obvious that you want to defend castles with maximum importance whether you want to defend the current castle or previous castle(s) by portals.

You could use inbuilt lower_bound and upper_bound functions in C++

Turned out in C I had the quadrants wrong. Not wrong implemented, but the wrong idea about how they are constructed.

In E it is no endless loop, my implementation is simply that slow :/

And i missed the case to check both colors in B.

Rip rating, I am doing something wrong.

Why are you signed in as another user?

I thought k == n is in the sample itself!

Nice solution, i thought it firstly too(before i decided that it needs dp). However i missed the fact that only furthest portal is matter. Thank you for your detailed comment.

Even I solved it using greedy method. Time complexity O(nlogn).

#include
using namespace std;
#define ll long long
#define ld long double
#define endl "\n"
#define dbg(x) cout << #x << " = " << (x) << endl;
const ll MOD = 1000000007;
const ll INF = 0x7fffffffffffffff;

void input() {
	#ifndef ONLINE_JUDGE
	freopen("F:\\Scripts\\input","r",stdin);
	freopen("F:\\Scripts\\output","w",stdout);
	#endif
}

template 
void print(T v, int l = 0, int r = 5){
	for(int i = l;i < r;i++) cout << v[i] << " ";
	cout << endl;
}

const int M = 5005;
int n, m, k;
int a[M];
int b[M];
int c[M];
int road[M];

int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); 
	input();
    
	cin >> n >> m >> k;
	for(int i = 0; i < n; ++i) 
		cin >> a[i] >> b[i] >> c[i];
	vector> g(M);
	int v[M] = {0};
	for(int i = 0; i < m; ++i) {
		int u, v;
		cin >> u >> v; u--; v--;
		road[v] = max(road[v], u);
	}


	for(int i = 0; i < n; ++i)
		if (road[i]) 
			g[road[i]].push_back(i);

	for(int i = 0; i < n; ++i) {
		sort(g[i].begin(), g[i].end(), [&](int a, int b) {
			return c[a] > c[b];
		});
	}

	priority_queue>, greater>> pq;
	int ans = 0;
	for(int i = 0; i < n; ++i) {
		while (k < a[i] and !pq.empty()) {
			k += 1;
			auto x = pq.top();
			ans -= x.first;
			v[x.second] = 0;
			pq.pop();
		}
		if (k < a[i]) return cout << -1 << endl, 0;
		k += b[i];
		if (!road[i]) {
			k -= 1;
			v[i] = 1;
			ans += c[i];
			pq.push({c[i], i});
		}
		for(auto j: g[i]) {
			if (v[j]) continue;
			if (k) {
				v[j] = 1;
				ans += c[j];
				pq.push({c[j], j});
				k -= 1;
			}
		}
	}
	cout << ans << endl;
}

I thought about that for a while at the end of the contest, but I don't know how to send flow through the students which attend three or two classes, I solved it using simplex method but didn't have enough time for implemented it in the contest

could've waited for 10 more submissions to get 66966996 :)

Thank you for the solution though

It is almost the same as model solution, so it is allowed to pass (model solution is $$$O(M^3)$$$ with very low constant, that's why the TL is so high).

In fact, I didn't know how to solve this problem faster before I saw some submissions with quadratic complexity.

Yes. Please

I think it is similar to 1251E2 - Voting (Hard Version).

Link is here

Actually, the most similar thing between these two problems is "I can't achieve it during the round".

Do it the greedy way.

Formally

while (have black blocks) {
  ix = first black block;
  block[ix] = white;
  block[ix + 1] = !block[ix + 1];
}

Check if the solution exists and try this for both black and white.

That problem has 2 points: - figure out that the binary search will work - get the idea that you should check only even numbers and max even answer + 1

As for the first, there are some problems which are solved by binary search, but once you know it the problem is no more challenging.

The second part is unique, just a question of practice and attention to details.

About improving yourself — first of all, what exactly is bad during the contest? Once you know the exact problem, you can start working on it.

Change your each "else if" to "if", a point can fit 1 or 2 "if" branch.

The dp state is how many castles we passed and how many warriors remained, $$$dp[5000][5000]$$$, where $$$dp[i][j]$$$ is the maximum sum of importance values of castles that we are already defending.

Interestingly enough, we do not need all those portals in the input. For a castle $$$v$$$, we need only the rightmost portal (since postponing the defense definitely won't cause us any harm). So, we are left with $$$5000$$$ portals, and no two of them lead to the same castle. BTW, it is convenient to interpret leaving a warrior in the current castle as a portal from $$$v$$$ to itself.

Transitioning between states is not really difficult. First, we copy all values from $$$dp[i - 1][]$$$ to $$$dp[i][]$$$ with an offset $$$+b_i$$$ — that is how many warriors we gain when capturing castle $$$i$$$. Note that we should omit copying some states $$$dp[i - 1][j]$$$, where $$$j < a_i$$$, since by definition we can't continue with such an army.

Then, $$$dp[i][j] = max(dp[i][j + k] +$$$ sum of $$$k$$$ portals w/ largest importance at castle $$$i$$$ over all possible $$$k$$$, $$$dp[i][j])$$$. Note that you should go bottom-up in respect to $$$j$$$ in order to avoid errors.

Asymptotic complexity is $$$O(n \cdot m)$$$, where $$$m$$$ is $$$5000$$$ — the maximum possible number of warriors in our army: $$$n \cdot m + (m \cdot p_1 + m \cdot p_2 + ... + m \cdot p_n) = n \cdot m + m \cdot (p_1 + p_2 + ... + p_n) = n \cdot m + m \cdot n = O(n \cdot m)$$$, where $$$p_i$$$ denotes the number of portals in the $$$i$$$-th castle.

BledDest

Are the editorials still being prepared? It has been more than 2 days since the contest!