chromate00's blog

Codeforces Round 1000 (Div. 2) — Editorial
By chromate00, 2 days ago, In English
Rating Predictions

The editorial for each task is written by me, chromate00. I tried to explain each task with as much detail I could fit in. Brace yourselves, it is going to be LONG. Please don't try to open all spoilers at once, it lagged my browser. Also, I apologize for not telling you strongly enough to read every problem, almost every tester thought F1 is easy if you read it well...

Also, our fellow wuhudsm told me there will be another community contest in the Gym soon, details will be posted on https://codeforces.me/blog/entry/138706 shortly :catThink:

2063A - Minimal Coprime

Author: chromate00

Hint
Editorial

2063B - Subsequence Update

Author: Yugandhar_Master

Hint
Editorial

2063C - Remove Exactly Two

Author: chromate00

Hint
Big Hint
Editorial

2063D - Game With Triangles

Author: wuhudsm (Original Idea) & chromate00 (Modified Idea)

Hint
Big Hint
Editorial

2063E - Triangle Tree

Author: Yugandhar_Master

Hint
Editorial

2063F1 - Counting Is Not Fun (Easy Version)

Author: chromate00

Hint
Editorial

2063F2 - Counting Is Not Fun (Hard Version)

Author: chromate00

Hint
Editorial
  • Vote: I like it
  • +52
  • Vote: I do not like it

»
3 hours ago, # |
  Vote: I like it +124 Vote: I do not like it

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

→ Reply
  • »
    »
    3 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why do you believe this?

    → Reply
    • »
      »
      »
      2 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I explained my reasons in the comments above: everyone has high expectations for this game, But I think although there were no serious issues in this contest, the problem setter did not do anything very well. So lots of people (including me) doesn't like it.

      → Reply
  • »
    »
    88 minutes ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Maybe 1024th round is more historic for a programmer.

    → Reply
    • »
      »
      »
      85 minutes ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      You are right, but this is historic too! (Wish CodeForces can hold a better contest in the 1024th round!)

      → Reply
»
3 hours ago, # |
← Rev. 2   Vote: I like it -20 Vote: I do not like it

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

→ Reply
  • »
    »
    3 hours ago, # ^ |
    ← Rev. 2   Vote: I like it +17 Vote: I do not like it

    Because many people think Round $$$10^3$$$ should be made of awesome problems as an historic round. Clearly the problems aren't good enough.

    → Reply
    • »
      »
      »
      3 hours ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Deeply sorry if you thought the tasks weren't awesome, I think we have different thoughts. I think most tasks were great.

      → Reply
      • »
        »
        »
        »
        2 hours ago, # ^ |
          Vote: I like it +85 Vote: I do not like it

        → Reply
      • »
        »
        »
        »
        2 hours ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        Well, you promised something epic, that might not be in a "normal div2 round".

        No hate, but imho normal div2 rounds usually have more interesting problems on positions A-D.

        Problem E's intended solution is really nice, but why did noone spot that it can be killed with normal small-to-large? To me E was also "read and immediately know how to solve"

        You managed to make interesting problem F, but intended solution using splay trees is also not in the list of epic things to me :/

        → Reply
        • »
          »
          »
          »
          »
          2 hours ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I did notice that E can be killed with small-to-large. I thought that the problem still is worth it, but it wasn't a surprise that it is "killed". I was thinking that depth-wise small to large is not a common topic for Div. 2.

          F has A LOT of solutions. Please don't be discouraged, any solution that works is a great solution for it.

          → Reply
          • »
            »
            »
            »
            »
            »
            2 hours ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I think my E just used common small to large which i implemented in at least 5 other cf problems back from the times when I was div2, though it's not the point

            Yeah, problem is still worth it, I'd be very happy to see such in div2 2 years ago when I was CM (as it was my fav trick then), but I'm speaking from a div1 perspective (perhaps, even if we're not rated auditory, we're still looking forward to 1000th round)

            For problem F you're right, just was discouraged after looking for a nice way to find the "outter" bracket pair for the last 20 minutes of the contest, and then seeing that in editorial...

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              87 minutes ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              There are much cleaner ideas for F2.

              My solution was to maintain a segtree initially of all 0, then each time a bracket pair is added, you update each value in the interval by 1.

              Then, the left bound of the interval you are contained in is simply the first element to the left of your position that has a smaller value.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                4 minutes ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Yep, that's exactly what i thought of in the contest! Just didn't manage to finish it, as i had roughly 2 minutes left when i was done with that segment tree xD

                Thanks for explaining!

                → Reply
      • »
        »
        »
        »
        71 minute(s) ago, # ^ |
        ← Rev. 2   Vote: I like it -9 Vote: I do not like it

        Yeah I wonder why they don't like speed forces for abc and bullshit geometry and greedy+ bullshit implementation for d, and an E which is just standard problem where u added also bullshit geometry to make it Cool but all u did was make a standard problem worse

        Even for a normal div2, this would've been a shitty contest, let alone round 1000

        → Reply
        • »
          »
          »
          »
          »
          51 minute(s) ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          cope

          → Reply
        • »
          »
          »
          »
          »
          8 minutes ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          the inclusion of "triangle" doesn't make a problem geometry. D and E has absolutely nothing to do with geometry unless you have not encountered the triangle inequality or area of a triangle formula, which you hopefully would've learned in middle school.

          → Reply
      • »
        »
        »
        »
        65 minutes ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        Personally I thought the problems were all great, didn't get all of them but the main idea for CDE required some clever insights and were interesting to me. I also like that F was actually doable for div 2 contestants.

        → Reply
      • »
        »
        »
        »
        63 minutes ago, # ^ |
          Vote: I like it +14 Vote: I do not like it

        I thoroughly enjoyed the problems. This might be my favorite round ever.

        → Reply
»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    +++++

    → Reply
  • »
    »
    3 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Both A and B were copy from test case and it passes lol. I didn't even read the whole problem just test case should pass XD

    → Reply
    • »
      »
      »
      3 hours ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      on B selecting just the minimum $$$r-l+1$$$ and printing the sum passed sample (I apologize for that, oh well)

      → Reply
»
3 hours ago, # |
  Vote: I like it -7 Vote: I do not like it

Noice Problem set. Especially C

→ Reply
»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

My Approach for B that didn't work
→ Reply
  • »
    »
    3 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Play with the maximum values in the [L,R] with the minimum values of both the subarrays to left and to right of [L,R]

    → Reply
    • »
      »
      »
      100 minutes ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hey I didn't understand the intution behind it. Can u please explain why it works?

      → Reply
  • »
    »
    3 hours ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    The subsequence you have selected either contains $$$[1,l)$$$ or $$$(r,n]$$$, simple sorting can result in mixing together.

    → Reply
  • »
    »
    3 hours ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    obviously 1 2 2 1 is not going to work when l,r=2,3

    → Reply
  • »
    »
    2 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Suppose you have the following input

    Input

    Your approach would yield $$$1+1=2$$$, but this is not correct. You can't get to swap both $$$2$$$s with both $$$1$$$s. You wish to swap costly items in $$$a[l:r+1]$$$ with cheaper items.

    Observation
    Approach
    → Reply
  • »
    »
    102 minutes ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I give you a easier Approach Just see my solution https://codeforces.me/contest/2063/submission/302470981

    → Reply
»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

→ Reply
  • »
    »
    3 hours ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Consider this test:

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

    Your code outputs $$$4$$$, the correct answer is $$$5$$$.

    → Reply
    • »
      »
      »
      2 hours ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      My logic is correct, but my code is wrong. Because I modify the unordered_set I'm iterating on, the loop stops after the first iteration. I wasn't aware of this behavior ...

      → Reply
»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 hours ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Consider this test:

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

    Your code outputs $$$4$$$, the correct answer is $$$5$$$.

    → Reply
    • »
      »
      »
      3 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I ran it locally and got 5

      → Reply
      • »
        »
        »
        »
        2 hours ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Your code seems to go to an infinite loop in 'Custom invocation' section. o.O

        → Reply
    • »
      »
      »
      3 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I followed a similar approach but my code is a bit different, the testcase that you gave passes on my code, can you maybe provide a TC where my code is failing?

      My code

      → Reply
»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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].

My Prediction
→ Reply
»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

code for problem C

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

can anyone point out why it failed on test 4?

→ Reply
»
3 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Check this case

    → Reply
    • »
      »
      »
      3 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      mine was passing on this as well don't know why it failed

      I guess the key thing was that the node with largest indegree and decrease the indegree by 1 for each neighbour and then found largest indegree overall and we are done

      → Reply
      • »
        »
        »
        »
        2 hours ago, # ^ |
        ← Rev. 2   Vote: I like it +1 Vote: I do not like it

        Consider that if you remove a vertex $$$v$$$ with maximum degree $$$d$$$ that contains at least two childs with degree $$$d$$$, you will get rid of the possibility to split the tree to $$$2\cdot d - 1$$$.

        Because if you remove $$$v$$$, you will get $$$d$$$ components, but your maximum degree will decrease to $$$d-1$$$. If you remove one of the childs of $$$v$$$ with degree $$$d$$$, you maintain the maximum degree as $$$d$$$.

        → Reply
        • »
          »
          »
          »
          »
          2 hours ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          can you give an example ?

          → Reply
          • »
            »
            »
            »
            »
            »
            2 hours ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            example: 1-2-3-4-5 Vertex 3 cannot be erased.

            → Reply
        • »
          »
          »
          »
          »
          2 hours ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          but it would still result same no

          see what i am doing is taking maxi indegree first and then after subtraction of 1 again maxdegree 2 and subtract 1 from both of them i tried your case but it fails as well

          see this is the submission if you could provide a tc where it fails

          my submission

          → Reply
»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

So hard:(

→ Reply
»
3 hours ago, # |
  Vote: I like it +10 Vote: I do not like it

E much simpler than D. For real.

→ Reply
»
2 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    2 hours ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    you choose the first vertex incorrectly. you take the vertex with the highest degree, but maybe if there are several such vertices, you take a non-optimal vertex.

    → Reply
»
2 hours ago, # |
  Vote: I like it -7 Vote: I do not like it

historical round, cool problems

→ Reply
»
2 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 hours ago, # |
  Vote: I like it +7 Vote: I do not like it

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

→ Reply
  • »
    »
    2 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    oh well, it was initially forcing online, and the coordinator thought offline is not too much easier. If offline makes it cleaner for you, you can solve it offline.

    → Reply
»
2 hours ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
2 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

Code
→ Reply
  • »
    »
    2 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Also great round!!

    → Reply
  • »
    »
    2 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same here.

    → Reply
  • »
    »
    2 hours ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    there's a slight issue with this. let M be the maximum degree of a vertex present in the tree, and V be the set of all vertices with such degree M. there can be a case where you can remove a vertex from this set and still have another vertex of degree M present, which is the optimal way. however, in your case you aren't considering this and would remove a vertex which would affect the degrees of all remaining vertices in V, and hence, give a sub-optimal answer.

    for example: for a tree of 8 nodes with these edges: -

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

    here you'd end up removing (1, 2) or (1, 3) which would give 4 components, but ideally you should remove (3, 2) and have 5 components.

    hope that helps

    → Reply
»
2 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    2 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i was not able to think this so i just used two pointer.

    → Reply
  • »
    »
    115 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    oh god i was so dumb i was onto this problem for an entire hour no!!!!

    → Reply
  • »
    »
    68 minutes ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    This would fail. Consider the test case

    3 6 6 4 3 2 l = 3, r = 5

    Here, by your logic, the answer should be 8, but clearly notice that the answer for this test case is 9.

    → Reply
»
2 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ? :)

→ Reply
»
2 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

[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]

→ Reply
  • »
    »
    2 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    chromate00 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-
    302363475

    → Reply
»
2 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
2 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    118 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why this is incorrect 

    // 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)) ;
}
    → Reply
»
119 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

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)) ;
}
→ Reply
»
117 minutes ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    102 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Consider this situation: the tree has five nodes —— 1-2-3-4-5

    Vertex 3 is one of the vertices with most edges, so possibly you tried to remove vertex 3. But the only optimal method is to remove vertex 2 and 4.

    → Reply
»
117 minutes ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
116 minutes ago, # |
  Vote: I like it +7 Vote: I do not like it

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

→ Reply
»
103 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    100 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes, we gave less scores on it and it turns out that people don't read :(((((((((((

    → Reply
»
102 minutes ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
97 minutes ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

302471253 why does this not work for C?

→ Reply
»
92 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
81 minute(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

guys, did nobody solve C using dp/ dfs ?

→ Reply
»
78 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
75 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

→ Reply
  • »
    »
    66 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This would fail. Consider the test case

    3 6 6 4 3 2 l = 3, r = 5

    Here, by your logic, the answer should be 8, but clearly notice that the answer for this test case is 9.

    → Reply
»
72 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

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

My approach

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

→ Reply
  • »
    »
    67 minutes ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    consider graph like 1-2-5-3-4 In this if you remove 5 first then answer will be 2 but if u remove 2 or 3 first then answer will be 3 .

    → Reply
  • »
    »
    55 minutes ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    It works until you don't have a graph which has three nodes with a maximal degree which form a tree subgraph. Then, if you pick the "root" of this tree as the first node (which can happen as you don't check which of the nodes having equal degrees to pick), its removal will decrease the degrees of both other nodes of that degree, so no nodes to pick at second step will have that maximum degree. And if you pick a "leaf" of this tree as the first node to remove, the second leaf will still have the maximum degree after removal as it wasn't adjacent to the first node, so you can pick the second leaf as the second node.

    → Reply
    • »
      »
      »
      36 minutes ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you, I never saw it that way, need to work on trying more testcases.

      → Reply
»
71 minute(s) ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    37 minutes ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    Actually, I think it's correct. We can see that the wrong solution fails when there are $$$3$$$ connected vertices with the same largest degree, and we can't pick the middle one as the first to remove. However, when there are $$$4$$$(or more) such vertices, we can pick the first one arbitrarily because it won't affect answer anymore. Therefore, checking 10 nodes(in fact, 3) should be enough.

    → Reply
»
68 minutes ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
66 minutes ago, # |
  Vote: I like it +4 Vote: I do not like it

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.

→ Reply
»
60 minutes ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
40 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
39 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    25 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
28 minutes ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
18 minutes ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it 
Clean solution for problem C :

302487313

→ Reply
»
2 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply