How would you prove it? Please provide a proof.

Are branded t-shirts different from the Kotlin Heroes ones?

You don't know shit about CF then. D2C is D1A, so it's always made for D1 after B.

CancerForces

Dumb problemsetters, they never learn...

Yeah, I see.

How the hell is problem C solved more than B? WTF?

Yeah, Educational rounds are supposed to be easier, for some reason I always do much worse in them...

A wise man once said — "Why no testers?", and he got downvoted. The result: this round

0-based indexing

Both are possible, it was slightly easier this time, but it seems like it's been like that for the last 10 rounds or so, so it could be a bit of both.

For D you realize that you can group graph vertices into components based on their entity/number assigned to them. You can then number each group and join only one element of each group with each element of the group that comes after. This way all the elements of next group are reachable one from another.

Say you have groups 1, 2 and 3. You join first element of 1 with all elements of 2 and join first element of 2 with all elements of 3. Finally join all the elements besides the first one in the first group with first one of the second group. Why? So that each vertix of first group is reachable from any other.

The only base case is when there is one color, then there exists no answer.

I used to be really bad for the first 2 months, today I solved 5 problems so don't give up and keep practicing. Unless you're doing problems below your current level, there is no wrong way of practicing.

Am I the only one to fail D2 on test 22? BTW, could anyone explain how my code could fail (on a smaller testcase)?

Actually, it used one of the standard ideas (counting number of 1s and 0s), I am still confused with so many people including myself not getting the idea...

B is just brute force and I have no idea how to solve A.

In B just take the largest value greedily to make sure the first GCD is largest and mark it as taken. Out of all the non-taken elements choose one that gives the largest GCD, but in order to not recalculate GCD every time, keep the prefix GCD in one variable and update in each iteration.

I did it using substraction rather than using the remainder, still passed with same complexity and obviously the same idea.

I didn't get your first point. CodeForces shows green and CodeChef shows green, what is wrong with that? Could you explain in a simpler way?

How do you improve your problem solving ability? The same applies for speaking. Speak in the language you are trying to learn. that's how I did it.

One of the toughest judges. Solving 200 problems there is a true achievement and gives you so much knowledge (there is no editorial, so you will have to think for long periods). Another great judge (not as tough as Timus, but with quality problems) is POJ, but it is now full of "not so great" problems, unlike 5-6 years ago. To put it into perspective, you will likely be at least purple-yellow after solving 350-400 problems from old collection. And it is not really even an approximation, to solve those problems you have to be very knowledgeable.

My man got some contribution by writing a blog and lost it all in the comments section.

Seriously though, do you guys have any tips for people like me who can solve problems on their own in the practice session but fail badly in the competition?

For example problem B and C from yesterday, I got the right idea in both of them but failed to implement them correctly under pressure (I've been stuck on B for 30 minutes because I wrote wrong variable names so decided to move to C, where I've gotten the right idea in 2nd attempt, failed two more times and after polishing two ifs got it right).

Persistence my man! Full year of persistence paid off! Congrats. :)

Could by any chance lessons be sorted in increasing order of difficulty? I am feeling like Binary Search should be covered before segment trees. Perhaps it could be easier for beginners to wrap their head around the problems that way.

Could anybody tell me what's wrong with this DP code for D? It is getting TLE on test 6. Thanks!

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

const int oo = 0x3f3f3f3f;
int t, n, ans;
char ca[200005];
int ar[200005];
int dp[2][2][2][2][200005];

int check(int a, int b) {
	return (ar[0] != a) + (ar[1] != b);
}

bool valid(int second_last, int last, int prev) {
	if (second_last && last && prev) return 0;
	if (!second_last && !last && !prev) return 0;
	return 1;
}

int solve(int second_last, int last, int ffirst, int ssecond, int pos) {
	if (dp[second_last][last][ffirst][ssecond][pos] != -1) return dp[second_last][last][ffirst][ssecond][pos];
	if (pos == n) {
		if (!valid(second_last, last, ffirst)) return oo;
		if (!valid(last, ffirst, ssecond)) return oo;
		return 0;
	}
	int ans = oo;
	if (valid(second_last, last, 0)) {
		int addi = (ar[pos] != 0);
		ans = min(ans, addi + solve(last, 0, ffirst, ssecond, pos + 1));
	}
	if (valid(second_last, last, 1)) {
		int addi = (ar[pos] != 1);
		ans = min(ans, addi + solve(last, 1, ffirst, ssecond, pos + 1));
	}
	return dp[second_last][last][ffirst][ssecond][pos] = ans;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> t;
	while (t--) {
		ans = oo;
		cin >> n;
		memset(dp, -1, sizeof dp);
		for (int i = 0; i < n; i++) {
			cin >> ca[i];
			if (ca[i] == 'R') ar[i] = 1;
			else ar[i] = 0;
		}
		ans = min(ans, check(0, 0) + solve(0, 0, 0, 0, 2));
		ans = min(ans, check(0, 1) + solve(0, 1, 0, 1, 2));
		ans = min(ans, check(1, 0) + solve(1, 0, 1, 0, 2));
		ans = min(ans, check(1, 1) + solve(1, 1, 1, 1, 2));
		cout << ans << endl;
	}
}

DISCLAIMER: This reply is intended for the newcomers and not the trolls.

None of the problems violate the propositions of the contest. I mean, nobody is forced to tell you E is harder than F. Many times D is easier than C, this time C was as easy as A and perhaps slightly easier than B, so I don't see anything wrong with F. You are always kindly asked to read all the problems.

As for the hacking phase, it's never completely fair, this round is not specific in that regard. After all, 50 people taking hacks won't really decrease your ranking by more than 50 places, and in case you are top 300-400, chances are hacking A or B won't be enough to surpass you.

Weak pretests, many time they are rather weak, but again this is not something stated in the propositions.

Conclusion: The points made in the blog are bullshit, I guess everyone is aware of it, so no changes soon I guess.

Yeah, listen to Ari, no unnecessary tags.

Are you gonna continue doing this for each new contest?

Yay! I managed to solve only B! Maybe I should stop competing for a while.

It's not really easy to determine. In Div2 rounds there are many different categories of Div2 participants — beginners, intermediate, upper-intermediate, advanced, etc. Beginners may solve B or C, intermediate may solve D, upper-intermediate may solve E, etc. Not all Div2 participants are same. :)

Read all the statements, have fun and try to solve as much as possible! At least you'll meet some new concepts. :)

Here is my code that passes everything:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll r, g, b;
vector<ll> ar, ag, ab;
ll dp[205][205][205];

ll solve(ll i, ll j, ll k) {
	if (dp[i][j][k] >= 0) return dp[i][j][k];
	return dp[i][j][k] = max({(i >= r || j >= g) ? 0 : ar[i] * ag[j] + solve(i + 1, j + 1, k),
				  (j >= g || k >= b) ? 0 : ag[j] * ab[k] + solve(i, j + 1, k + 1),
				  (i >= r || k >= b) ? 0 : ar[i] * ab[k] + solve(i + 1, j, k + 1)});
}

int main() {
	cin >> r >> g >> b;
	memset(dp, -1, sizeof dp);
	ar.resize(r); ag.resize(g); ab.resize(b);
	for (ll i = 0; i < r; i++) cin >> ar[i];
	for (ll i = 0; i < g; i++) cin >> ag[i];
	for (ll i = 0; i < b; i++) cin >> ab[i];
	sort(ar.begin(), ar.end(), greater<ll>());
	sort(ag.begin(), ag.end(), greater<ll>());
	sort(ab.begin(), ab.end(), greater<ll>());
	cout << solve(0, 0, 0) << endl;
}

I believe your mistake is this line:

if((i>=a and j>=b) || (i>=a and k>=c) || (j>=b and k>=c)) return 0;

Instead using ternary operators, like I did solves it. Why? Here's an example. If we take this line into consideration:

arr[i]*brr[j]+func(i+1,j+1,k)

We only care if either i or j is greater than a or b in your case. This means that we should not check for (i >= a && j >= b), but for (i >= a || j >= b), since one element is already out of bounds and there is no solution but your code cares only whether both elements are out of bounds, that allows space for error.

True inspiration man! I've seen a few people with very slow progress get to the top, but never people who drop that low and rise to blue. Keeps me going, already. :)

I got problem A wrong, than was stuck on it to realise my initial idea was correct. Skipped B and went to solve C, cause I couldn't improve ranking at that point. Never solved C, I'm starting to believe I am dumb at this point...

It has been out for some time. LINK

Suppose you have got these two numbers — 2 and 7. Their binary representations are: 10 and 111. Since there are no set bits in 2 that are not set in 7 the or value is 2 | 7 = 7.

This means that if a | b = t and c | d = t, than a | b | c | d = t.

Why is this true? Because a and b have no set bits which are unset in t and same holds for c and d. In other words c1 | c2 | ... | cn = t is true when c1 | t = t, c2 | t = t, ...

Since we are looking for the lowest or value of and values of pairs from a[] and b[], we test for each value from 0 to 511 (because of the constraint 2^9 which yields 512) whether there is j for ever i, such that (a[i] & b[j]) | k == k. Here k is the number we are iterating up to 511. In pseudocode it would look like this:

for (i to 512) cnt = 0 for (j to n) for (k to m) if (a[j] & b[k] | i == i) cnt += 1 break if (cnt == n) print i break

Cnt == n simply checks whether it is true for every i, instead of using some flags.

I solved B in 5 minutes and couldn't manage to solve A at all. I solved for two cases (n & 1 and n & 1 ^ 1). For even numbers I ended up with n / 2 + 1 and for odd with n — 1. Don't know why I did it, I had the correct solution inside one statement...

I used map and multiset but don't know if that's the right way to solve (it passed all the pretests though).

EDIT: The exect idea Ok- used. I update the counts in map (strucuted as [count, set of values], while inserting or removing elements in multiset.

I read the statements to my younger cousin, he enjoyed the round! Thanks StoryForces! :D

Auto comment: topic has been updated by VeryGoodVeryGood (previous revision, new revision, compare).

Thank you so much for the explanation. The first half truly helped me understand the whole idea. Thanks again!

Thank you very much, I think I am starting to get the algo now. :) It took me a while to get the difference between TS and TPP, so just to clarify the difference between Traveling Salesman and Chinese Postman is that in the first one we need to travel all the vertices and in the second one all the edges. Right? Thanks once again.