Actually, maximum independent set is pretty hard problem to solve and can be done in $$$O(n^3)$$$ using Kuhn's algorithm on bipartite graphs. The graph you build isn't even bipartite (you can easily obtain odd length cycle with segments $$$[1; 5]$$$, $$$[4; 8]$$$ and $$$[3; 6]$$$, they all have pairwise intersections). I don't know a good solution for this problem for non-bipartite graphs, just some randomized approaches which don't work well.

Video Editorial of Problem D: Binary String to Subsequences

I had the same approach. At least i'm glad to know that i wasn't the only one. Thanks vovuh for the explanation :)

I tried the same and then I learned that finding maximum independent set is not as easy as I thought

Maybe because it doesn't have transivity.For example,Segment A=[2,3],B=[3,4],C=[4,5], A-B ans B-C are invalid,but A-C is valid.So you can't map in this way.

Video explanations to everything else. (And also A-C lol)

In the first for loop you are doing sum[a[i]+a[j]]++ which is wrong because lets say there are 3 people with weights {1,3,3} In the first iteration , you are using the zeroeth person thrice (when (i,j) is (0,0) (0,1) (0,2)). In the first iteration itself sum[4] will be 2 which is not possible since if the zeroeth person made a team with the first person for sum=4, he cannot make another team with the second person. As a person cannot be in 2 teams, this approach fails.

I also did like this only. The only mistake I spotted in your code is that in your priority queue, you're arranging the edges by (weight * nx) [nx = no of leaves for this edge contributes to the sum].
Instead, it should be the reduction we can get if we make our operation in it, i.e. (weight * nx — (weight / 2) * nx).
Example to prove the contradiction, let's say weight1 = 7 and nx1 = 3, and weight2 = 3 and nx2 = 7. If we do the operation on 1st one, 7*3 = 21 will reduce to 3*3 = 9, hence the deduction is 12. On the other hand if we do on 2nd one, 3*7 = 21 will reduce to 1*7 = 7, hence the deduction is 14.
But in your code, 1st one will be operated. Hope you understood.
My submission — 89053607

Tried implementing a similar idea to achieve $$$O(N)$$$ memory complexity but my solution is TLEing at the last test case.

Here's the idea: Sort according to the end points of the segments and let $$$dp[i]$$$ = the maximum number of segments you can pick considering only the first $$$i$$$ (in the sorted list).

The transition involves trying to pick the $$$i^{th}$$$ segment, which requires running exactly the same dp on all subsets of the $$$i^{th}$$$ segment. Then compare this to not picking the $$$i^{th}$$$ segment, which corresponds to just considering the first $$$i-1$$$ segments.

I'm not sure of the time complexity, but I believe it should be $$$O(N^2)$$$. Would appreciate if somebody double checks this/gives ideas for optimization.

Here's the submission: 89072684

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(n);i++)
#define repl(i,a,b) for(int i=(a);i<(b);i++)

struct range {
	int l, r, ind;
};

int rangedp[3005];
vector<range> subs[3005];

int solve(vector<range> lr, int ix=3001) {
	if(lr.size()<=1) return lr.size();
	if(rangedp[ix]!=-1) return rangedp[ix];
	int n = lr.size();
	int dp[n+1];
	dp[0]=0;
	repl(i, 1, n+1) {
		dp[i]=1; // picked this one
		// solve for elements inside current segment
		dp[i]+=solve(subs[lr[i-1].ind], lr[i-1].ind);
		// binary search last index that doesn't
		// intersect with current segment
		int l=0, r=i-1, j=i-1;
		while(l<=r) {
			int mid=(l+r)>>1;
			if(lr[mid].r>=lr[i-1].l) {
				j=mid;
				r=mid-1;
			} else l=mid+1;
		}
		// add the number of segments you can get
		// by including the j segments that don't
		// intersect with the current one
		dp[i]+=dp[j];
		// is it optimal to include current segment
		// or should we skip it?
		dp[i]=max(dp[i-1], dp[i]);
	}
	return rangedp[ix]=dp[n];
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t;
	cin >> t;
	while(t--) {
		int n;
		cin >> n;
		vector<range> lr;
		rep(i, n) {
			range val;
			cin >> val.l >> val.r;
			val.ind=i;
			lr.push_back(val);
		}
		// sort according to end point, break tie so that
		// larger segments appear later
		sort(all(lr), [](range a, range b) {
			if(a.r!=b.r) return a.r < b.r;
			else return b.l < a.l;
		});
		// precompute subsets of each segment
		rep(i, n) subs[i].clear();
		repl(i, 1, n) {
			int j=i-1;
			while(j>=0 && lr[j].r>=lr[i].l) {
				if(lr[j].l>=lr[i].l) subs[lr[i].ind].push_back(lr[j]);
				j--;
			}
			reverse(all(subs[lr[i].ind]));
		}
		memset(rangedp, -1, sizeof(rangedp));
		cout << solve(lr) << endl;
	}
	return 0;
}

Can you explain how to find this

finding the largest set of intervals such that no two overlap

Haha I actually made the exact same mistake (then they came out with the clarification and I felt like such a fool... not the first time I've misread a problem). Didn't make much progress on that though.

You don't handle n=1 correctly and read outside of array bounds leading to strange values of s1 and s2. Because the array and vector have different sizes on the stack the memory read by a[1] and a[n-2] is different between your solutions so you end up with different behaviour.

your ans is not correct

Before all, we calculate the number of leaves in every subtree using DFS. The contribute of the lowest edge between the subtree's root and the root is the number of leaves in the subtree multiplied by the edge's weight. Recall the contribute of one move is the diff of its edge's contribute after move. For example, for an edge of weight 5 whose subtree has 3 leaves, its contribute is $$$5*3=15$$$, and the contribute of its first move is $$$5/2*3-5*3=-4$$$.

We use a multi-set/priority_queue or other data-structure containing all available moves sorted by its contribute in non-decreasing order. When we do a move, we push the next move in data-structure (weight divided by 2). If two moves' contribute equal, which first? We first take the one of which next move has lower contribute. If the next move equal, we check the next of next, and so on. But this take too long time($$$\log W$$$), we have better method. If two moves' contribute equal, either their's weight - weight/2 equal and the leaves number of their's edge equal or any one's weight-weight/2 equals the other's leaves number. First case, one has large weight will always win. Second case, one has little weight will always win. You can prove it easily.

There're exactly 2 cases of the answer, odd or even. If the answer is even, we can think two one-cost-move as one two-cost-move, and do this process greedily. If the answer is odd, we can take a one-cost-move that has lowest contribute. This is my submission: 89086737.

I'm not sure whether it correct, although it get Accept before system test.

Iam sorry if someone felt offended by my comment. But I didn't have such intentions. I don't get why people down vote others comments. I am not spreading rumours or criticizing someone or putting something which hurts someone. I am really trying my best to grow and help others to grow along with me. Do you all know how ugly it would be if anyone including my recruiters who open my profile and see a negative contribution. Guys we are members of the same community please try to help others not critisize them. If anyone felt offended by this message iam sorry again.

Can you please share your approach for E1

thank you so much

hacking doesn't effect rating in div 3. so people can learn to hack here.

Where do you want help here, it's completely incorrect.

You are probably using this code on some online compiler, copying the output from there and then pasting it as manual input. But online compilers doesn't really give you complete output for such big codes, they probably stop at around 500th test case among your 1000 cases (you can check that by writing cout<<i<<" "<<50<<endl;).

So instead, compile it on your pc (eg: codeblocks) and then use files, get output onto a file, submit that file.

Also notice that the code you want to hack which gave TLE on some online compiler(due to incorrect input), may not really give TLE.

Try compiling with the flags -g -D_GLIBCXX_DEBUG. It will catch most common errors in STL containers and provide some helpful information about them.

In this case, you are trying to dereference an iterator after you just erased its contents from a set. The error produced by the debugger is "Error: attempt to dereference a singular iterator.".

Well, I haven't read the editorial yet, because I got an AC during the contest itself, but here is how I approached the problem.

So, we got a string of 1s and 0s and the length is n. The task is to make partitions, i.e. divide it into subsequences which are either of the form 10101.. or 01010...

So let me assign group 1 to my first character. And simultaneously, I'll try to decide what is the next character my group 1 needs.

Now here comes the second element. I just need to check, whether it'll fulfill the hunger of group 1 (that is it gives the required element), or whether it'll just make another group 2 of it's own and wait for a suitable match. This is the way, we need to do for all the rest of the positions.

Now to solve it effectively, I just need to maintain the group numbers for those waiting for 0s and 1s, and so I'll need a map and I'll make a map of sets, because of it's O(n) time insert and delete (I'll need these operations, because the groups will keep swapping there needs between 0s and 1s).

My Submission : 89003229

set doesn't have duplicates, so you go into infinite loop.

AC on making it multiset: 89075373

In (4) is it not sufficient to check if RED2/2 >=RED1(here red1 is choosing from pq1 once) and if it is true perform operation on pq2 else on pq1 ? can you give a counter example of it?

You are erasing the first element of vector. vector.erase() has a time complexity equal to the length of the vector because when you delete the first element you have to shift the entire vector to the left one position. As you're calling erase() multiple times inside a loop, when the vector length becomes large, you get TLE. Instead of erasing the first element, you can erase the last element using pop_back() which has a constant time complexity because the order in which you insert '0' and '1' in the existing subsequences doesn't matter (as long as you're maintaining minimum number of subsequences).

.....where ai is the (index) number of (the) subsequence, the i-th character of s belongs to.

Even if it wasn't clear to you, it was kinda obvious :)

Actually here, all the characters(0 or 1) are belong to exactly one sub-sequence. So, from your point of view the result should always be 1 1 1 1... right? But no, actually here it's meant that if there are n sub-sequences, number them from 1 to n. then print which character belongs to which sub-sequence. For example: 4 0011 has 2 valid sub-sequences, let number them as 1st sub-sequence and 2nd sequence. So let first 0 is belong to 1st sub-sequence, then 2nd 0 should obviously belong to 2nd sub-sequence. Now, first 1 can either be belong to 1st sub-sequence or 2nd, and the last 1 would be in the alternate sub-sequence. So result can either be 1 2 2 1 or 1 2 1 2 or 2 1 1 2 or 2 1 2 1. I think you have got this now, right?

Your task is to choose the maximum by size (the number of segments) subset of the given set of segments such that each pair of segments in this subset either non-intersecting or one of them lies inside the other one.

what does this statement mean? so confused. ><

• 10 28
• 8 2 8
• 5 1 4
• 6 1 10
• 10 2 7
• 7 2 1
• 9 2 1
• 2 1 5
• 4 1 9
• 3 2 5
• Sorry i dont know how to end line :((

I think it will work. I am applying same thing but storing only edge with cost 1 in priority_queue and cost 2 in other priority_queue.

Yes, It worked.

Try this input:

1
12
110110001010

Correct output:

3
1 2 1 1 3 2 1 3 2 2 1 1

Your output:

4
1 2 1 1 4 1 2 3 1 1 1 1 

I'm just trying to help. pks18 and Greatest789, in such cases, where you want to find a test case, you can use stress testing with an AC solution.
Take a look at this blog

Heaps are actually faster then sets, your solution is giving TLE, as you are passing graph(vector g) by value, which increases the time complexity. Pass Graph(vector g) by reference or make it a global variable.

Heyy, you need to use a custom comparator in your priority queue so that your top element is always the one that results in max decrease in the sum.

class Compare { public: bool operator() (pair<int, int> a, pair<int, int> b) { int x = a.second/2; int y = b.second/2; return a.first * (a.second - x) < b.first * (b.second - y); } };

Here the 1st element of the pair is the no of leaves and the 2nd element is the weight.

No, I don't think so. We positively need to iterate over all possible values of sum, and for each sum, we need to find how many groups we can make. And after that, we'll find the maximum number of teams. So, the order has to be O(n^2).

If you're in Linux and you have the appropriate GCC version (>5), you can just use the flag -stdc++=17 to use c++17.

in :
1
5
00100
out :
2
1 2 1 1 2

you can see this test case says it all. 2 set was starting from 0 and your code is giving the next element as 0 also in the second subsequence.

Yes easiest when you cheat and your solution gets skipped ;)

Maybe you are not taking the difference as the factor to decide which edge should be halved first.

For n=2, it will consider both the vertices as leaves. In fact, for any tree where the root has only 1 degree will have it as a leaf. Ask yourself if that's what you really want or whether this makes a problem in your implementation (whatever you want to do with the leaves). You can start from 2 as you know that 1 is root. But yes, other than this corner case, your logic is ok.