Really Informative. Thanks. Keep these Discussions coming...

Improve your internet connection before doing live streams and change your microphone. how someone supposed to understand whatever you are explaining in the live stream :')

As far as I'm concerned, not making any submission during contest will make the contest not count for you. But you can unregister anyway: follow this link: https://codeforces.me/contestRegistrants/1914/friends/true and click the red X

Sorry, downvoted by accident.

Have a nice day, friend.

Marinush

Lol it didn't happen this contest :D. Bricked E1 tho

After solving A, B, C, D, E1 & E2:

There is nothing we can do...

Due to some issues, it will be updated after this round.

Unrated for you.

ok then I clearly assume that I can solve A-D :)

Still rated

What's the greedy optimal solution?

I couldn't figure out greedy solution even thought I tried for so much time. Finally had to submit E1 with brute force solution

can you explain it

I couldn't even get E2 but got F :(

Try all 3*3*3=27 combinations of the largest 3 values of a,b,c

I did it by trying all permutations the order of choosing, and when its ones turn to choose they just choose the biggest one where the day isn't chosen before, and just getting the max of all permutations.

It can be done using dp with bitmasking. Here's the code: https://codeforces.me/contest/1914/submission/237970710

BFS and pair teams height wise (bottom to top) I think. If there are any remaining players (which happens when they are along a path of the tree), pair them up with players at a higher level with highest priority.

I got confused with D and not able to solve at all

Please explain ?

I don't think there was an "idea". Firstly it was clear that distinct problem solves would be a prefix. So just brute force on the prefix and for the rest of solves just take the maximum b[i] in the prefix. See, just brute force.

Greedy approach, "if I decided to stop increasing my level at level $$$i$$$, what is the maximum score I can get?" if you stop at level $$$i$$$, then your best choice is to use the remaining $$$(k - i)$$$ plays redoing the maximum $$$b_j$$$ such that $$$(1 \leq j \leq i)$$$ again and again. So the answer is this maximum value across all $$$i$$$, just keeping in mind that you can't go to level $$$i$$$ if $$$k \gt i$$$

Сейм. Я вообще сначала написал топ сорт, а потом заметил это условие.

Alice wants to save her balls and get rid of Bob's, they both equally affect the score. And the vice versa for Bob.

If Alice picks ith-marble, score increases by a[i]-1 and if Bob picks ith-marble score decreases by b[i]-1. If Alice did not pick up the ith-marble in his turn, this means that his choice of say jth marble which increased his score by a[j]-1 is more significant than the impact of Bob decreasing the score by b[i]-1 in the following turn, compared to an increase of a[i]-1 and a decrease of b[j]-1. So you need to sort the array |a[i]-1|+|b[i]-1|, which is equivalent to sorting a[i]+b[i]

Initially, both Alice and Bob got all the marbles. No matter who operates on color i, the difference between their marbles is fixed a[i]+b[i]-1, so do a[i]+b[i] Sorting, Alice greedily chooses the largest a[i], and Bob chooses the largest b[i].

I think this div 3 round's ratings update will be applied first, then the previous edu round, according to the latest announcement.

I think it is Rated. Look at that. Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

I think f[i] represents the set of all colours that occur exactly once prior to index i. It uses hashing to fit in a single integer and the xor means that after the second occurrence of each colour, it is removed from the hash. Then if there are two distinct indices i, j such that f[i] == f[j] and they are nonzero, all colours that occur between i and j only occur between i and j, and there exists another colour that "surrounds" them. Hence turning on any light bulb among this set initially could not be part of a minimal solution, because you would have to turn on one that surrounds them anyway (and that could have been used to turn that initial one on). So you can skip to the last occurrence of each f[i] when counting the number of ways.

The core idea revolves around determining the number of ways to activate bulbs in such a way that disjoint ranges are covered. The approach involves finding** sets of bulbs that, when activated, cover a specific disjoint range**.

Let's denote the number of disjoint ranges as 'k.' For each range, we aim to identify the bulbs whose activation covers the entire range. Through some careful considerations, we conclude that we need to eliminate bulbs that do not contribute to extending the current segment. This elimination process is efficiently executed using prefix hash values and storing the last pointer for each unique prefix value.

To illustrate this concept, consider the arrangement of bulbs: 1 2 2 3 1 3. The number of disjoint ranges in this case is one. Building prefix hash values results in pre[0]=1, pre[1]=1^2, pre[2]=1, pre[3]=1^3, pre[4]=3, pre[5]=0. After activating the first bulb, we jump to the bulb at index 1 + (last[1]=2).

The hashing technique employed here, as introduced by jiangly, is a so cool and unique that when understood properly can be generalized to solve a variety of other problems involving segment merging or ranges.

const int mod= 998244353;

std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());

void solve(){	
	int n;
	cin>>n;
	vector<int>col(2*n);
	for(int i=0;i<2*n; i++){
		cin>>col[i];
		col[i]--;
	}
		
	//now through random number generator
	//let's generate for each colour a unique random val
	
	vector<int>hashVal(n);
	for(int i=0; i<n; i++)hashVal[i]= rng();
	
	//now make a prefix xor array of these hashed values
	//so that we can effectively know how many 
	//ranges of 0 to 0 we have
	//number of min sets= number of ranges
	
	vector<int>prefixXor(2*n,0);
	prefixXor[0]= hashVal[col[0]];
	for(int i=1; i<2*n; i++)prefixXor[i]= prefixXor[i-1]^hashVal[col[i]];
	
	//number of zeroes = no of ranges
	int ans= count(prefixXor.begin(),prefixXor.end(),0);
	
	int ways=1;
	map<int,int>jumpTo;
	for(int i=0; i<2*n; i++){
		jumpTo[prefixXor[i]]= i;
	}
	
	for(int i=0; i<2*n;){
		//start of range-> prefixXor= hashedVal[i]
		
		if(prefixXor[i]==hashVal[col[i]]){
			//inside new range
			//jump directly all the ranges lying
			//completely inside it and not helping in
			//extending it
			
			int active=1;
			int j=i;
			while(prefixXor[j]!=0){
				j= jumpTo[prefixXor[j]];
				active++;
				if(prefixXor[j]==0)break;
				j++;
			}
			ways= (ways*active)%mod;
			i=j+1;
		}
	}
	cout<<ans<<" "<<ways<<endl;
	return;
}

read this post https://codeforces.me/blog/entry/107753

You should just take maximum of possible pairings, no matter if it's leaves or not (just make sure they are from different branches). I've got my brain melted after writing the append of results of child-dfs to current res (.0 = pairs, .1 = available people in subtree) (solution). Same thing but much simpler is in the jiangly's solution

no, if you can provide a source where similar code was already written before the contest it's not considered as cheating.

If you have proved it,can you pls provide a proof of it?

proof was my way to solution. i couldn't guess.