yet another youtuber whose streams i like :D

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

hoping to become pupil :)

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 :(

Yeah I too was surprised to see your performance. (been following you for some time :))

I think C>E1,E2>D, C take me a lot of time, while D is my first submission

make a 3x3 matrix of the activities with the most friends, and do recursion to find the optimal 3 days, sum of whose is our answer.
Code: 238064464

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

You can greedily try to to match for each vertex vertices only from different subtrees and then you are left with maximum 1 subtree with unmatched vertices where you can recurse.

EDIT:

238056332

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 ?

For C My approach was to take all the elements of A first Then greedily start removing elements of A from last and filling the remaining with the maximum available elements of B we have, while doing this keep taking max of all

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 > i$$$

i just think which marble each player will select

if A's turn A just pick what max(A get + B lose)

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 I can give a more clearly stated explanation to the solution discussed here.

Consider current score as S.

Now, think of two index i and j, where values in a and b are still > 0.

Let these two index be such that Alice takes one, and Bob takes the other.

Final effect on Score after the 2 moves:

Case1 (Alice takes ith, Bob takes jth marble) : S1 = S + (a[i]-1) — (b[j]-1)

Case2 (Alice takes jth, Bob takes ith marble) : S2 = S + (a[j]-1) — (b[i]-1)

If S1 > S2:

S + (a[i]-1) — (b[j]-1) > S + (a[j]-1) — (b[i]-1)

(a[i]-1) + (b[i]-1) > (a[j]-1) + b[j]-1)

(a[i] + b[i]) > (a[j] > b[j])

Therefore, if both players move optimally,

They take the marble from the index which has the largest sum, a[k] + b[k]

Hence, the approach:

Sort and construct the score based on (a[k] + b[k]) is a correct approach.

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

Nope, Please I got that

Nice solution.. didnt thought of this did with dp ^-^

Really cool implementation for d.

I got the logic during the contest. But started implementing without any plan. Ended up with a big messy code which I could only complete after the contest. Got AC anyway.

same

lmfao accurate

mine

keep update max(b)

constuct prefix of a

answer = max( (k-i-1)*max_b + prefix[i])

(k-i-1) is remaining of k after do ith quest

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.

Try merging the total amount Alice and Bob have and choosing the optimal values greedily from the sorted merged set of values.

see this guy's solution: https://leetcode.com/problems/stone-game-vi/solutions/969817/strategy-proof/

only difference between the leetcode problem and E2 is that in E2 you subtract n % 2 from the answer.

Basically after each move each player in profit of a[i]+b[i]-1 coin if he choose ith index so make a set of pair and insert a[i]+b[i] in set with its index.(only if a[i]>0 & b[i]>0) and in each move pop greater sum index and do operation according to player while set is not empty.238003308

look from the perspective of alice & try to make score of alice as much as possible.

Now lets consider two elements a = [x1, x2] & b = [y1, y2] then in this case in which case alice will win

say alice first selects y1 to remove from b then score will be (x1-1 — y2 -1) because then bob will only left with x2 to remove

similarly if alice remove y2 first then score will be (x2-1 — y1-1)

now see in both the cases which is giving higher score simply sort the index with value x1 as first for alice and then alternately removed one by one because we have sort it such that it'll give maximum score to alice on its turn bob will try to remove the next maximum possible to minimize the score.

Check solution here : https://codeforces.me/contest/1914/submission/238051187

You have to send it in both problems in order to get points.

dude D is very easy just brute over the top 3 on each group and check if there is different date since we are sure we will find a combination for such conditions

yeah solved using heap

I have tried this approach by storing sorted elements in a stack and popping if they belonged either to the same index or the same kind of event. This approach however does not work because it means that you will always choose the highest popularity on the first pick. Lets say u had 99 and 95 in A and 98 and 1 in B assume any value for C. If you choose 99 in A which will be on top of the heap you will fail to choose 98 for B which happened on the same day. 95+98>99+1. Here heap approach fails and you will have to compare the highest 3 to get answer.

If you play as Alice and take i on some move, you earn a[i] — 1 because Bob can't decrease this number after your move (-1 because you decrease your number by 1), and you earn b[i] because Bob loses b[i] marbles. And now you play as Bob and take j on some move, you earn b[j] — 1 because Alice can't decrease this number after your move and you earn a[j] because Alice loses a[j] marbles. So you need to maximize the same thing (a[i] + b[i] — 1) for both Alice and Bob on every move.

in each step you try increase yours score and decrease opponent score as much as possible so A[i] + B[i] its just how much you can get if u pick i-th element, increase for A[i] and descrease for B[i] (and opposite for bob)

No. After hacking phase ratings will be updated.