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.net/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.net/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 > 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 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.net/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

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

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.

for E1: just use the mini max algorithm: check my submission

it means that node x is a superior of node y if node y is in node x's subtree

Count pairs $$$(u, v)$$$ where $$$LCA(u,v) \notin \{u,v\} $$$

In problem statement it's highlighted in bold: exactly two light bulbs for each color. Tbh, I didn't notice it during the round. So when we have a group of bulbs with 2 of each, we have SCC and can turn it on with just 1 switch in |group| — |sub sccs| ways. 2 of each color => xor == 0.

Suppose you pick all the quests until the index $$$i$$$ just once ($$$i$$$ must be less than or equal to $$$k$$$). You still have $$$(k - i)$$$ moves remaining, and you can only choose the quest with an index less than or equal to $$$i$$$. We will greedily choose the quest with the largest value of $$$b$$$.

ll sum = 0, ans = 0, m = 0;
for(int i = 1; i <= min(n, k); ++i)
    m = max(m, b[i]),
    sum += a[i],
    ans = max(ans, sum + (k - i) * m);

cout << ans;

I fixed some of your logic, hope it helps

238110031

btw, the 3944th case seems to be

7
1 1 1 2 3 4 

The answer is 3 but your solution says 2.

The three pairs could be (2, 6), (3, 7), (4, 5). Other combinations are possible.

carrot is good. It is always close to the real delta.

Start pairing members from deepest leaves until you reach the root

Nope, question says The second line contains "n−1 integers p2,p3,…,pn(1≤pi≤n), where pi is the index of the direct superior of the i-th employee." So, in 1 2 1; first number is direct superior of p2 => p1 is direct superior of p2 ; second number is direct superior of p3 => p2 is direct superior of p3 ; third number is direct superior of p4 => p1 is direct superior of p4 ; So, only (3,4) is valid team.

shouldn't you erase it after updating res ?

yes when will ratings update?

yes

What's going on?

ahahahah nice, I killed it in my code xDDD

in comparator when equal return false, just change >= to >
blog

yes

WOW !! You submitted the same code, changing the variable name mb to ar .. And is it a coincidence ??

Your submission: 237968347 t = int(input()) for _ in range(t): n, k = map(int, input().split()) a = list(map(int, input().split())) b = list(map(int, input().split()))

ar = [0] * n
ar[0] = b[0]
for i in range(1, n):
    ar[i] = max(ar[i - 1], b[i])

ans = 0
cnt = 0
for i in range(min(k, n)):
    cnt += a[i]
    rem = k - (i + 1)
    cur = cnt + rem * ar[i]

    ans = max(ans, cur)
print(ans)

Your friend(/co-cheater)'s submission 237961744 t = int(input())

for _ in range(t): n, k = map(int, input().split())

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

mb = [0] * n
mb[0] = b[0]
for i in range(1, n):
    mb[i] = max(mb[i - 1], b[i])

res = 0
tot = 0
for i in range(min(k, n)):
    tot += a[i]
    rem = k - (i + 1)
    cur = tot + rem * mb[i]

    res = max(res, cur)

print(res)

If you look at E1 and E2, I was not able to think of the greedy criteria of a[i] + b[i] at first so i had brute forced it for E1. I coded this up in the last 5 minutes when the solution came up to me. Idk what else i can do to justify my innocence :/

The tutorial finally comes out!

Providing a comparator that does not satisfy strict weak ordering to sort() is undefined behavior.

So getting a correct answer is one of the possibilities.