Lightning fast! But I think your problems are not good enough for this historic round.

Why are you guys down voting??? Are you guys trying to make the blog like this

I know dogshit about how to solve A i just implemented according to testcases

Noice Problem set. Especially C

A was easy but B's pretest 2 destroyed me! I was absolutely shocked why it didn't work.

Great set of problems ! Clear description, nice test cases, no mistake ... Kuddos to all organizers. I will enjoy taking more time to solve D and E.

I have been stuck on C, but I don't understand why my submission got WA : 302435615. Could someone give me a hint ?

Can anyone help explain how my answer is wrong, I'm just searching for highest degree node, removing it, then finding the highest degree node again: 302462038

I did terrible on this contest

On B, I took 2 subs to realize that I was checking [1,l+1] instead of [1,l].

code for problem C

https://codeforces.me/contest/2063/submission/302448973

can anyone point out why it failed on test 4?

Can someone explain why I am getting WA: on my submission 302454358 in problem C. I am doing brute force. I am first greedily picking the first vertice and then removing it after picking second vertice.

So hard:(

E much simpler than D. For real.

https://codeforces.me/contest/2063/submission/302459815

why this is wrong can someone explain ?

i have simply done the process told by the editorial and it is giving wa on 4

historical round, cool problems

Problem C can be solved using DP without any observation, but the state transition is a little bit complicated.

Seems that F2 can be solved much more easily by solving reversely (with a disjoint set union to maintain the father-son relationship)

hi everyone! i understand each one of you might've had super high expectations since this was round #1000, i get it, but it's not right to belittle or humiliate other people just because they didn't exactly meet your super high expectations, right? i believe B and C were really nice tasks! also overall the round was enjoyable, the editorial also seems very informative, kudos to the authors + testers for this round. let's not get blinded by our subjective views and insult other people (by downvoting their blogs) who tried their best :) thanks

For C I tried getting the maximum degree, adding that to the answer, removing that node and decreasing degree for each neighbour node and then getting the maximum degree again. Why does this fail, any counter case?

void solve()
{
	int n;
	cin >> n;
	vector<vector<int>> adj(n + 1);

	vi indegree(n + 1, 0);

	for (int i = 0; i < n - 1 ; i++) {
		int a, v;
		cin >> a >> v;
		adj[a].pb(v);
		adj[v].pb(a);
		indegree[a]++, indegree[v]++;
	}
	int maxm = -1;
	int maxmIndegreeNode = -1;
	for (int i = 1;  i <= n ; i++) {
		if (indegree[i] > maxm) {
			maxm = indegree[i];
			maxmIndegreeNode = i;
		}
	}
	int numberOfComponents = 0;
	numberOfComponents += maxm;
	indegree[maxmIndegreeNode] = 0;
	for (auto &x : adj[maxmIndegreeNode]) {
		indegree[x]--;
	}
	int maxm2 = -1;
	for (int i = 1 ; i <= n ; i++) {
		if (i == maxmIndegreeNode)continue;
		if (maxm2 < indegree[i]) {
			maxm2 = indegree[i];
		}
	}
	numberOfComponents += maxm2;
	numberOfComponents -= 1;
	// assert(numberOfComponents <= n - 2);
	cout << max(0ll, numberOfComponents) << nline;
}

ThankFully rating can not go below 0.....

https://codeforces.me/contest/2063/submission/302390551

Could anyone please explain why this approach is wrong? I just sorted a and printed the sum for l-r+1 elements.

Could someone give me a hint why my D solution gives WA3

There are nothing amazing question in this contest. And just for me , F1 is much more easier than E. Anyway , I'm glad to participate in this 1e3 round. May be it'll be better in 1024 round ? :)

[user:chromate00][user:MikeMirzayanov] I have submitted A in the contest. It is showing submitted in the official standings, however it is not showing submitted in the unofficial standings. Kindly rectify the situation. Submission- [submission:https://codeforces.me/contest/2063/submission/302363475]

Editorial seems quite overkill for many of the problems, like binary search for D, and forest of splay trees for F. That being said I also solved F with link-cut tree lmao, though I'm not sure why the editorial doesn't mention that the forest of splay trees kinda just is a link-cut tree?

Anyway, very happy to AK and get rank 27 on such a special round. Screencast here for those who are interested.

can anyone tell me whats wrong with mine approach

https://codeforces.me/contest/2063/submission/302431234

i am finding the vertex with highest indegree and then recalculating indegrees and then taking and removing the highest again. i am taking the case of line graphs separately

Edit : found the mistake

1 2 1 3 1 4 2 5 2 6 3 7 3 8

Why this is incorrect pretest 4

// this is code
void STROY(){
    int n;
    cin >> n;
    vvll adj(n + 1);

    vll degree(n+1, 0) ;

    fr(i, 0, n - 1)
    {
        int u, v;
        cin >> u >> v;
        degree[u]++;
        degree[v]++;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vp temp;
    int com = 1;
    
    for (int i = 1; i <= n; i++)
    {
        temp.push_back({degree[i], i});
    }

    SORT(temp);
    int node = temp.back().second;
    com += temp.back().first - 1;

    for (auto it : adj[node])
    {
        if (adj[it].size())
        {
            degree[it]-- ;
            adj[it].pop_back();
        }
    }
    degree[node] = 0 ;

    vp tempp;
    for (int i = 1; i <= n; i++)
    {
        tempp.push_back({degree[i], i});
    }
    
    SORT(tempp);

    com += tempp.back().first - 1;

    cout << max(0, min(n-2, com)) ;
}

I don't get why my following logic failed in problem C,

My approach:

Initially ans = 1, and store the number of edges in an array sz.

First, find the vertex with most edges, let's say vertex u with sz[u] edges, then answer increase by sz[u]-1, then decrease sz[x] by 1 for all vertext adjacent to u. Also set sz[u]=0

Then repeat the process to get second vertex v. Then ans again increase by sz[v]-1

Submission:

https://codeforces.me/contest/2063/submission/302433943

despite doing horribly i think the problems are slightly better than your avg div 2 , and more balanced , not the quality i expected for the 1000th , still nice tho

edit : i havnt seen problem F , maybe it'll change my view of the contest

again messed up B and solved C before B. Also why downvotes, why do you think the problems aren't "awesome" ?

F1 was predicted to be easier than D ?! :(

can anyone help me this in problem B for the test case

6 3 6
10 40 30 50 80 5

according to the solution given in tutorial the answer is coming out to be 45 but like in range 3 to 6 even if we try reverse any subsequence of the array the interval sum is not coming out to be 45 but it is accepting the solution I do not know how that sorting logic is working here I got this thing like why we are trying for 1 to r or l to n so can anyone please explain this

also any advice for how should i maintain my rating range i am getting a lot of -ve delta nowadays though i am solving 1200, 1300,1400

302471253 why does this not work for C?

I don't know that experts can set most of the questions in a Div2 round before :|

The above is just my opinion, because after a while, I will become an expert :(

guys, did nobody solve C using dp/ dfs ?

Channel Name : Computer Knowledge Link : Link

This guy is repeatedly posting solution to questions for the Last several Rounds. Not Only codeforces, but also to contests on Leetcode, CodeChef (He is currently solving a Live Contest from Codechef).

Kindly, Look into the matter. @chromate00

In the second question (Subsequence Update), can we just sort the given array and give output the sum of the first (r — l + 1) elements as we can swap any elements with any other element ? I followed this logic it passed the test case 1 but failed in test case 2 , Help ?

Failed to solve problem C, Can somebody please point out my mistake

WA4 : https://codeforces.me/contest/2063/submission/302459466

Here is my 2 post contest accepted submission for C..

302473806. (using inclusion exclusion property)

302476948 (initial approach with more operations)

can anybody hack these submissions??

During contest I guessed that, checking the first 10 or 20 nodes with higher in degree will do the work.. But I did not implement & I stuck with my initial solution.. Sed,, i missed as always...

Why is this Showing TLE on the first pretest on problem C, what's wrong , can anyone help me out[submission:302460657],

I thought the problems were great, also I appreciate that F was doable even for div 2 participants. I found CDE all very interesting problems, but that's probably because they're at my level.

Great problemset.

In C you can simply output $$$d_{max} * 2 - 1$$$ when there are three or more nodes with the same maximal degree without simulation and otherwise just simulate picking two best nodes greedily.

In D, when computing the $$$k$$$-th answer, you can just check if the number of point pairs (segments) picked from one of the two lines exceeds the possible maximum which is $$$n - k$$$ and $$$m - k$$$ for the first and second line, respectively. If it does, knock the last segment length from the answer and add two lengths from another line. If it doesn't, just add the length from that line that allows it (i.e. from which the number of already picked segments is strictly less than the possible maximum) and yields maximal of two results (if both are allowed). The only thing you need for prepocessing is to sort segment lengths in decreasing order like shown and proven in the editorial.

Could anyone explain the 2 pointers approach in problem D please?

I had the same direction as editorial for C but couldn't figure it out completely and then had to go back to DP because DP made sense to me quickly but the editorial approach needs some casework to be done.

302483202

Will please someone help me analyse where this code is going wrong on testcase4?

I take the vertex with highest vertex and add deg-1 and decrement degrees for all connected nodes then again take the highest deg and add to ans.

Clean solution for problem C : 

302487313

Thank you chromate00 for the round, I had a fun time!

It seems that problems F1 and F2 are very similar to problem E of the recent 997 round.

good Round

Problem C : extreme brute force solution (302504107)

In the editorial of D, shouldn't it be concave instead of convex? Prefix sum of a decreasing sequence should be concave right?

I actually used DP on trees and i don't know why but my solution is failing on Test case 2 C ripped my whole contest. missed D by 5 minutes.

here is my submission if someone would like to help 302414968

P.S.-I personally liked the contest problems