exhausted's blog

By exhausted, history, 2 months ago, translation, In English

author: exhausted, developer: exhausted

1946A - Median of an Array

Editorial
Solution

author: max0000561, developer: yunetive29

1946B - Maximum Sum

Editorial
Solution

author: exhausted, developer: exhausted

1946C - Tree Cutting

Editorial
Solution

author: azureglow, developer: azureglow

1946D - Birthday Gift

Editorial
Solution
Solution (74TrAkToR)

author: yunetive29, developer: yunetive29

1946E - Girl Permutation

Editorial
Solution

author: exhausted, yunetive29, developer: exhausted, yunetive29

1946F - Nobody is needed

Editorial
Solution
  • Vote: I like it
  • +147
  • Vote: I do not like it

»
2 months ago, # |
Rev. 2   Vote: I like it +143 Vote: I do not like it

For C, why is there an entire paragraph discussing why rerooting doesn't affect the answer, but no discussion on why the greedy algorithm is optimal?

BTW, I created video editorial for D: Birthday Gift.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    With fixed x you want to maximize number of edges to remove. Consider lowest subtree with >= x vertices, if we dont cut edge right up this subtree, we can move closest edge from top and answer won't get worse

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      But when you when you disconnect a subtree with its parent, how do you make sure its parent's component still has more than x vertices?

      We are trying to make as many cuts as possible only considering the current subtree, but we do nothing to ensure the parent still has x or more.

      What am I missing?

      • »
        »
        »
        »
        2 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        once there is a subtree with more than x points,you count it as a connected component and cut the connection with the subtree and it's father.

        it is shown that if the connected component which include the root maybe has x-less points.but it wasn't counted before.you just need to think it as add a edge which was cuttted before from this connected component to others.it won't affect the counting number.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
          Rev. 2   Vote: I like it +1 Vote: I do not like it

          so essentially, for a fixed x, and number of cuts k, you want k + 1 components whose size >= x. If you have 3 components, what's left of the chopped up parent can just be added to the components we just made

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

        same doubt and also should we not have to check for k+1 connected components? as if we remove k edges , no. of connected components will be k+1 if i'm not wrong...

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          Yeah, but I think the idea is that when you're running the algorithm, you're not guaranteeing that the connected component containing the root node has size of at least x. So, if you remove k edges, you get k+1 connected components, but for one of them you can just connect it back to the component with the root node, giving you k connected components. That way it's unnecessary to check whether the component with the root node has size at least x.

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

        we will remove the subtree sizes which we have cut already so that way will not count the removed subtree and after that we just check wether the component of which has root have the size greater that >= x its okay otherwise we have to make 1 less cut.

        you can check this,

        code for reference
        • »
          »
          »
          »
          »
          2 months ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          Why is there a need to decrease cnt if the root node has a size less than m? cnt is incremented only if we have gotten a size greater than m. So we never had an extra number in cnt. I do not understand the need to decrease it

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

            Consider this case.
            n = 7, k = 3
            1 2
            2 3
            1 4
            4 5
            1 6
            6 7

            To my understanding, the algorithm will cut edges (1, 2), (1, 4) and (1, 6). The cnt guarantees [0, cnt-1] cuts are possible, not exactly cnt cuts because it depends on the last group (root group) we made if its size >= particular x we are checking.
            You can try adding extra edge like (1, 8) and see what happens.

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
            Rev. 3   Vote: I like it 0 Vote: I do not like it

            root_comp_size < m

            all other comp size >= m

            so to make the root_comp also have size >= m , we can merge any adjacent other component to do that we need to remove 1 cut, which is what we did

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

        I am just proving that it's optimal, like if we consider best way to choose edges, we can move edge lower, while subtree size is >= x. About algorithm of checking, of course we root a tree, then do this greedy, and we just need to check in the end that root component size is >= x, if not, then we can remove only 1 edge, cause all other comps are of size >= x

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

        Just noting down my understanding if anyone is still confused about this:

        There are really only two cases to think about

        • If the root component has at least x vertices

        • If the root component has less than x vertices

        In the first case, it is straight forward. We simply have to check if we have at least k + 1 components, since making k cuts would lead to k + 1 components.

        In the second case, it is a bit of a think. As per most implementations, if we have less than x vertices, we have not added this component to our count of components yet. So we must increment this count by 1.

        But since we have less than x vertices, we also want to re-unite this component with another (that already has at least x vertices, which is why it had gotten disconnected in the first place). So we must also decrement the component count by 1.

        So ultimately, our component count remains the same, and we simply want to check if we have at least k + 1 components, for the same reason that making k cuts would lead to k + 1 components.

        Ref [C++ clean]: https://mirror.codeforces.com/contest/1946/submission/252842752

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

    During up-solving I found BFS thoughts more intuitive, if you consider from last level (leaf nodes) and then go upwards. I realised that the only way to break subtree optimally was the one that is mentioned in editorial. Though I couldn't implement BFS solution

  • »
    »
    2 months ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

    C editorial is fucking trash

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    problem C mega sexy... during contest it just gave my skills a serious reality check

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice editorial . Really liked Problem C and D .

»
2 months ago, # |
  Vote: I like it -6 Vote: I do not like it

I see at least two things gone horribly wrong for this round:

A: Okay, this should probably seem like a nitpick for non-problemsetters, but you should have let $$$\mathcal{O}(n^2)$$$ pass for the position. Why exactly? Because this is a damn rule. Didn't KAN remind you?

the rule in question

F: Who even decided $$$\mathcal{O}(n \log^2 n)$$$ intended with $$$n=10^6$$$ was a good idea? Why? What led you to think so?

  • »
    »
    2 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    I don't see why my code is wrong for https://mirror.codeforces.com/contest/1946/submission/252819046 but keep getting "wrong answer on pretest 2 expected 12 but got 19 in 3096th number or so". Can you check my python submission in my history? It seems (exactly same idea) similar to a solution I found which was accepted.

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

    $$$\mathcal{O}(n \log^2 n)$$$ isn't that bad for $$$n = 10^6$$$ especially when you aren't doing heavy stuff with sets or segment trees, and the TL is 6 seconds. Personally, my solution passed pretty close to time limit though, but as I said in a previous comment, they probably wanted to cut $$$n \log^3 n$$$ solution.

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

      But $$$n=2 \times 10^5$$$ is more than enough to cut most $$$\mathcal{O}(n\log^3 n)$$$ solutions of any constant? I mean the single $$$\log n$$$ is already dozen times the difference, I can't see why would they fail to block a slower solution with $$$n=2 \times 10^5$$$. Unless they wanted to block an $$$\mathcal{O}(n\sqrt n)$$$ solution, which doesn't look like a very good decision after all if that solution doesn't make the task much easier to solve.

      • »
        »
        »
        »
        2 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        I see your point. They could have reduced both the limits and TL in order to make $$$n \log^2 n$$$ pass comfortably enough.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Oh, also another thing. I think the tight TL makes Python / Java solutions almost impossible to pass (evidenced by the fact that there are no AC Python or Java solutions yet, even in practice mode).

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

        Two of the logarithms are from fenwick and harmonic series, so they are smaller than usual log

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
          Rev. 2   Vote: I like it +3 Vote: I do not like it

          Why would that make a difference? The difference between $$$\log_2 x$$$ and $$$\ln x$$$ is constant, i.e. $$$1/\ln(2) \approx 1.44$$$ times, which suggests that it shouldn't be that much smaller than the usual log. Also, what makes you think Fenwick must have a smaller constant? Though it is hard to admit it, many sources suggest that the Fenwick tree's speed is on par with a well-written bottom-up segment tree. If their intention is to let Fenwick tree pass and block segment trees, wouldn't that be one of the most stupid decisions ever?

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it +5 Vote: I do not like it

            I wrote the same solution with a bottom up segment tree (253203142) and with a fenwick tree (253207869).

            The solution with the fenwick tree got AC in ~5000 ms while the one with the segment tree got TLE 12.

            In my opinion it's better to let $$$O(n\log^3n)$$$ solutions pass rather than cutting off some $$$O(n\log^2n)$$$ solutions because of the constant factor.

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

    Thanks to this, I uphacked all solutions with Arrays.sort((primitive type)[]) without randomization I found written in Java 8, not sure Java 21 can be hacked too

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

    How is problem A $$$\mathcal{O}(n \log^2 n)$$$? It's clearly $$$\mathcal{O}(n \log n)$$$ per test case. 252755171

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

    Where are these rules mentioned? Like the one you've mentioned in the spoiler.

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

      There is a document titled "Polygon advices", which starts with a huge text stating "IF YOU ARE TO PREPARE A ROUND ON CODEFORCES, THESE ARE RULES. FOLLOW THEM AS CLOSE AS YOU CAN". I do not know if I am allowed to disclose further; ask KAN for details.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://mirror.codeforces.com/contest/1946/submission/252802394

Can anyone help find the test case for which my code is wrong? Also whats wrong in the approach

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Greedily creating segments, left to right, in such a fashion might be wrong.

    It would fail for the following test case

    Spoiler
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem E is just liitle modification of past problem. Not new.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody please explain why the solution of the problem F works in $$$O(N\log^2(N))$$$?

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

    There are $$$O(N\log^2(N))$$$ pairs of $$$(a,b,c)$$$ such that $$$a | b$$$ and $$$b |c$$$ and $$$ a < b < c $$$.

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

      Can you please provide a proof for this statement?

      • »
        »
        »
        »
        2 months ago, # ^ |
        Rev. 2   Vote: I like it +30 Vote: I do not like it

        What we need is $$$\sum \sum N/i/j$$$ for $$$1 \le i \le N$$$, $$$1 \le j \le N$$$

        $$$\sum 1/i$$$ is $$$\log N$$$ for $$$1 \le i \le N$$$
        $$$\sum 1/j$$$ is $$$\log N$$$ for $$$1 \le j \le N$$$

        $$$\sum \sum N/i/j$$$ can be written as $$$N (\sum 1/i) * (\sum 1/j)$$$ for $$$1 \le i \le N$$$, $$$1 \le j \le N$$$

        This leads to $$$O(N*log^2N)$$$ upper bound on no of such pairs.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +17 Vote: I do not like it

        Fix $$$a$$$. Now the number of pairs of $$$(b,c)$$$ that satisfy $$$a<b<c$$$ and $$$a|b$$$ and $$$b|c$$$ is bounded by

        $$$ \frac{N}{a}\sum_{i=1}^{\frac{N}{a}} \frac{1}{i} \approx \frac{N}{a} \ln \left(\frac{N}{a}\right)$$$

        Now, the total number of $$$(a,b,c)$$$ pairs are around

        $$$\sum_{a=1}^N \frac{N}{a}\ln\left(\frac{N}{a}\right) \lt \ln N \sum_{a=1}^N \frac{N}{a} \approx N \ln ^2 N$$$
        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Hi, could you explain more about the sum (1 / i) part? Is that the part of counting Cs when fixing a and b?

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Why haven't you provided your code along with the editorial ? If I am not able to implement any solution provided above, should I go through all the submissions of users and try to find out which user has solved the problem according to approach described in the editorial ?

»
2 months ago, # |
  Vote: I like it +7 Vote: I do not like it

i can t understand the C solution , can u guys suggest me a similar classic problem? , to understand the idea ?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, for problem C I can't understand why if we have at least k+1 vertices with at least x vertices in its subtrees our condition is resolved. Can anyone explain it briefly?

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Because if we can get more than k+1 components then we would merge some components to make number of components to be exact k+1 and in doing so the size of final merged components would still remain>=x(since the size would only increase) and so the condition is still satisfied

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

      I think that the question told us that we should omit exactly k edges and after that, we should have at least x nodes in each remaining component but this solution is for situations where we want to only omit one edge and after that, we want to have at least x nodes in each remaining component. Am I right or does this solution support the first situation too?

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

        the solution tells us to omit as many edges as possible ensuring that each component has size>=x

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem C, If I do a recursive dfs, it gives TLE(Python). Can someone who solved in python tell me how to get around this? I would appreciate it a lot. Thank you

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

wish i read D first

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

High quality editorial!

»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

In problem E I think it should be nCr[(pm1)-2,p(m1-1)-1] since position of pm1 and (pm1)-1 both are fixed.

Because we have (pm1)-1 element and maximum element out of this is automatically at p(m1-1)th position.

»
2 months ago, # |
  Vote: I like it +20 Vote: I do not like it

Here is my stream discussin these problems

My contest screencast see it if you want to know what I was doing in the contest.

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

    Sir can you explain In problem D why we will count no of submasks present in an array.Basically I didn't understand the getmaxlength() function

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Initially, I misread the problem and tried to solve different version.
      We dont need getmaxlength() function. The submission 252805024 that got AC did not even have this.

      Disclaimer: This comment assumes you have watched the stream and uses some of the definitions mentined in the stream.

      The crucial idea is -
      Lets say we want to find no of maximum partitions such that on
      (pref[0]^pref[i])|(pref[i]^pref[j])|(pref[j]^pref[k])|(pref[k]^pref[n]) = M Notice that pref[0]=0, so pref[i] should be submask of M.
      Now lets look at pref[i]^pref[j], we want it to be submask of M.
      So all the bits that are 0 in M, should be 0 in pref[i]^pref[j].

      If kth bit in pref[i]^pref[j] is 0, if kth bit of both pref[i] and pref[j] are same.

      Now, because all pref[i] is submask of M, so any bit that is 0 in M will also be 0 in pref[i].
      Because for any bit that is 0 in M should be same for both pref[i] and pref[j], we have a condition that any bit that is 0 in M should also be 0 in pref[j].
      Now, this is the definition of submask. We have reached a conclusion that pref[j] should be submask of M.

      Now, we can use the same reasoning to get pref[k] should be submask of M too. So on for all pref[*] we need.

      Then the idea was we do not have to bruteforces X submasks, we can get it done using logX different submasks.

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    in problem a given solution yields output 1 for input of 2 member array (2,4). while the answer should be 2. if we use 1 operation value will be 7/2 which is ultimately 3.

    heres the editorials solution:

    void solve() { int n; std::cin >> n; std::vector a(n); for (int i = 0; i < n; i++) { std::cin >> a[i]; } std::sort(a.begin(), a.end()); int p = (n + 1) / 2 — 1; int res = std::count(a.begin() + p, a.end(), a[p]); std::cout << res << "\n"; }

    am i missing something in the logic/ question statement?

    edit--never mind read the problem wrong. used preconception of median to write the solution.

»
2 months ago, # |
  Vote: I like it +40 Vote: I do not like it

I didn't know E was a standard problem.

Solved it slightly differently. This felt a little bit more intuitive to me.

Spoiler
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    actually one of our testers wrote this solution and it can be implemented easily without any handling any corner cases click

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

      Can't open the page. Says — you are not allowed to view the requested page.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        here it is
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    So, my original solution to this problem was this. The tutorial provided a different solution, because it seemed more understandable

»
2 months ago, # |
  Vote: I like it +15 Vote: I do not like it
int y = (x^(1 << b));
for (int c = b - 1; c >= 0; c--) {
    if (((y>>c)&1) == 0) y ^= (1 << c);
}

FYI it is the same as

int y = ((x >> b) << b) - 1;
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    i would rather code the first than think about the most optimum way to code it sirs

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

252835387 Can someone please tell the test case where my code is failing. Thanks

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the editorial of D? What does this mean "After this, if there is a 1 in x in this bit, update the answer and return the array to its original state."?

And is there any other approach to this problem?

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

    According to me what they are trying to say is that if we have even 1 at ith POS and x ith bit is also 1 then we do not need to partition it further.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For F:

I wrote a $$$\mathcal O(\sum cnt^2_{divisors})$$$ and thought it was brute force but it passed. It can be really short and fast if implemented well.

Why it's the intended solution? $$$n=10^6$$$ usually leads to a $$$\mathcal O(n\log n)$$$ solution.

Anyway, a typical 74 math problem.

»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it

In problem F I think it should be t1 >= L instead of <=.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    thanks! fixed it

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I am wondering what is the limit of F's answer. Can someone prove that F's answer is in range of int or long long?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone have D's solution using DSU?

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

    C u mean?

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      No. D has a tag of DSU. edit: In the morning it was showing tag of DSU but it's now removed. Why such?

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

        I had such solution, you may check my submission

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

          It's hard to grasp the underlying logic behind your DSU solution merely by looking at the code. Can you please elaborate your idea behind the solution?

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

            When we go bit by bit, we might need to unite segments in one component, so I used dsu to store the number of components. I also used set to effectively unite neighbouring numbers and rollbacks, since I needed to roll after attempting each bit

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hey, can you explain your solution. Thanks

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

        can you just read tutorial?

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it +16 Vote: I do not like it

          правильно, туда его, пусть идет решение читает

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

          I was talking about the above code you mentioned in the comment. I did not see it was not yours

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Reading proof for C was a nice journey

»
2 months ago, # |
  Vote: I like it -8 Vote: I do not like it

why everybody used lambda function in c instead of normal function?? (especially candidate master and above)?

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

    With normal functions, you must make all variables and stuff global, so you must clear them after every test case, and this is so boring and waste of time.

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

      and one more thing that we don't have pass many of the data that we pass in function

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Please somebody explain first part of solution C, how we can get the same solution for x — 1, if we have it for x?

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

    Suppose you want to know that is it possible to cut the tree using k edges in such a way that every component has at least x nodes. now suppose that the answer is affirmative,i.e., every component has at least x nodes. now if you rephrase the problem after replacing x with x-1, you see that if we cut the tree in the same way as we did to find the answer to whether is it possible to cut the tree so that every component has greater than or equal to x nodes, you find that every component has greater than x-1 nodes(as every component has >=x nodes).

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

      I understand, that is, we need x — 1 vertices, but we already have x. I thought that we need exactly x — 1 :) As a result, we have answers [1, 1, 1, ..., 1, 0, 0 ...0] and we can use binary search to find the maximum possible x. Now it remains to write the checking function. Thanks, it's clear now!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://mirror.codeforces.com/contest/1946/submission/252897123 Can anyone help find the test case for which my code is wrong?

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem B :Can somebody explained me why i am getting overflow issue:https://mirror.codeforces.com/contest/1946/submission/252902592

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

is there a way to use dsu in problem c? like if we remove all of the edges first and then start combining components?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Solution to problem C using Tree trimming submission

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

B is really just kadane

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

[submission:252783316]why is this code wrong,i just found indices of subarray with max sum and added it 2 power k times and finally added rest members of array other than those indices(indices of max sum subarray) to final sum

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't understand a single thing about C editorial. Can somebody explain the greedy algorithm with actual proof?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This is my solution to problem C, the idea is same as the editorial still I'm getting TLE. Can anyone explain? https://mirror.codeforces.com/contest/1946/submission/252888566

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can't understand the proof of problem C. whats the first case and the second case? and whats the first variant? whats the first time? Do "case", "variant" and "time" mean the same thing?

  • »
    »
    2 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it
         1
       /  \
      2    3
     / \   / \
    4   5  6  7
    

    For such a binary tree and x=3. If I start the dfs on node 1. I think the algorithm would remove the edge 1-2. But if I start from node 2 and traverse node 1 at last. The algorithm would not remove the edge 1-2. although the answer is still correct the set of removal edges is not coincide. Could anyone please tell me where I might have misunderstood?

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

      no, edge 1-2 will not be deleted, because you can renumerate node 2 and 3, in this case dfs remove only edge 1-3

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

        Emm... Sorry im still confused. So u mean when dfs starts from node 1 and visits node 3 first, it would only remove edge 1-3? But the subtree of node 2 also meets the requirement(components > 3). why dfs do not cut the edge 1-2 since it would visit node 2 anyway.

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

          because you return 1 edge if size of node 1 component is less than x

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I am just noticing the problem D is not having binary search tag, I thought Binary search is the most intuitive solution for D as I solved using binary search during contest. And also the editorial logic is not matching with the intuition i had ?

I did binary search on answer, like for k pairs what is the minimum number I can create satisfying <= x which was the difficult part.

Don't know I did binary search on C also, may be my thought process got biased ?

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

    Hey there, i checked your solution, but could not understand the logic behind it. Can you please elaborate your solution?

    Thanks!

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Sure, so if you are asking how I approach the solution then its like I see that we have to calculate the maximum pairs k , so may be we can binary search on the answer k.

      so to model the problem as binary search, I did like "lets say we have to take at least K pairs, in that case what is the minimum number we can make".
      If you see the modeling of problem also bit non-trivial, I am saying we have take at least K pairs (this 'atleast' is most important for writing the checker function correctly)

      so in the checker function what I am doing is trying to make the smallest number possible where I need to at least K pairs.

      Now if you want to know how exactly I have written the code, my code is clean you can check should be self-explanatory if you are good with bitmasking and OR minization techniques (which I am not so good at from time to time).

      I can tell you the concept, I am going from MSB to LSB, and checking if the current bit I can make it 0 or not. If we can make it 0, we will update our answer for that particular bit as 0, otherwise as 1.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi! I have a question about problem B:

5 1
4 -2 8 -12 9

For the above test case, if I select [-12] as the subarray and insert its sum (-12) in the array, the sum of the array will be 4-2+8-12+9-12 = -5. And -5 modulo (10^9 + 7) is 1000000002. Why is this not the optimum answer?

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

    your motive is to calculate the maximum answer without modulo. we are ask to perform % (1e9 + 7) as answers can be pretty large and can't be represented in 64bit integer.

    you are not supposed to take the value which is giving you the maximum after modulo.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C was very nice, it's very similar to this one (except for the binary search part):https://mirror.codeforces.com/contest/1833/problem/G

»
2 months ago, # |
  Vote: I like it +11 Vote: I do not like it

I think some problem setters really don't care about quality of Div2.B problems anymore. This Div2.B feels like filler problem, just invented at last moment or something. It's just kadane algorithm. Nothing more, nothing less.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How is the formula for A derived?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

very good competition.I like it!!!

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Felt problem C is not obvious -- just implemented and got AC but re-rooting argument in editorial is quite nice

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a question, the x in question B I think is constantly changing, the answer at k = m should depend on the x of the question at k = m — 1, but then the x should have changed when transferring shouldn't it, or am I thinking too much about it :(

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In E, as written in editorial :- p1 should be 1 for some valid permutation to exist. 1. Is it because, it's the first element and it will be maximum in it's segment because there's no element before it. 2. If the above reasoning is true, then shouldn't s1 also be equal to 1, since aN is the last element.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think I've been missing something, this code gives wrong result for test case 6 1000, 6x -1000000000:

#define ll long long
const ll P = 1e9+7;

int main()
{
    int t;
    cin >> t;
    int kk = 0;
    while(t--)
    {
        int n, k;
        cin >> n >> k;
        vector<int> a(n);
        int sum = 0;
        for(int i = 0; i < n; i++)
        {
            cin >> a[i];

        }
        ll big = 0;
        ll subar = 0;
        for(int i = 0; i < n; i++)
        {
            sum += a[i] ;
            subar += a[i];
            subar = max(subar, 0LL);
            big = max(big, subar);
        }
        sum = (sum % P + P ) % P;
        big = big % P;

        int T = 1;
        for(int i = 0; i < k; i++)
        {
            T = T *2 % P;

        }
        int ans = (sum + big * T - big + P) % P;
        cout << ans<< endl;
    }
    return 0;
}

I can't really find the problem, I looked at the editorial code and it seems fine to me.

Also if anyone cares to elaborate, why can we use int for sum (like editorial does) can't that overflow the value, does OP knows that test cases won't to that, or is there something else that I'm missing?

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

    Oh so basically problem was that sum was int actually, I tought I already tried it as long long. Also I now see that in editorial int was defined as long long, idk why would someone do that, it's confusing to beginners but okay.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

really liked problem F, thanks for the contest!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In the editorial for C:

If after this process there are at least k connected components, then the condition is satisfied for this x , otherwise it is not.

Shouldn't it be k+1 connected components since we are removing k edges.

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anybody help me with B by providing a resource for me to understand modular arithmetic as required for such problems? For example, why must we take t = t * 2 % P; instead of simply adding first and then taking the modulo.

Thanks in advance.

»
2 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

exhausted

As per editorial of problem:D, I have one small doubt.

suppose my array is [ 2 , 1 , 2 , 2 , 1 , 2 ] and my x = 0;

[ 2 , 1 , 2 , 2 , 1 , 2 ]
  ^       ^   ^       ^
  L1      R1  L2      R2

since we want to maximize the number of segments, each segment must contain exactly 2, such numbers

Can you please explain, how to handle above case from the editorial ?

Answer is, when I take an entire array, otherwise, there is no answer.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain me solution of $$$C$$$ in simple words please , I mean why the greedy algorithm works

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In the solution of C :

if (sz >= x && f != v) {
   ++res, sz = 0;
}

There is no need of checking if it is the root node or not because even if it is, it will make sz = 0 which will be handled in the

later part

so this can also work :


if (sz >= x) { ++res, sz = 0; }
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Edit: I got it

In the editorial solution of problem E, the line res = max(res, (int)b.size()); updates res. But b.size() is non-increasing while we are moving from bit number 30 to bit number 0. If b.size() is non-increasing, why can't we simply print the first best answer of b.size() when discovered and then break out of the loop. I tried submitting it but I got WA, so I am missing something. Can anyone point out what am I missing?

Here's the submission link. The only difference between that submission and editorial's code is the break statement after res = max(res, (int)b.size())

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somneone send me a solution for problem B using dp because i do not know how to apply dp to it?

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    well what the editorial did was dp just that it has a formal name called "Kadane's Algorithm" my solution is here.

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For C, this is code that i have written:


def dfs(cur,par,x,cnt,adj,n): num = 1 for nxt in adj[cur]: if nxt == par: continue num += dfs(nxt,cur,x,cnt,adj,n) if num >= x: cnt[0] += 1 return 0 return num def check(x,adj,n,k): cnt = [0] dfs(1,-1,x,cnt,adj,n) return cnt[0] > k t = int(input()) while t > 0: t -= 1 n,k = map(int,input().split(" ")) adj = [[] for i in range(n+2)] for i in range(1,n): a,b = map(int,input().split(" ")) adj[a].append(b) adj[b].append(a) l = 1 r = n while l <= r: mid = (l+r)//2 if check(mid,adj,n,k): l = mid+1 else: r = mid-1 print(r)

i am getting runtime error on testcase 4 and i don't know why it is happening

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why does this code TLE for F?

https://mirror.codeforces.com/contest/1946/submission/254907291

I'm at 77 wrong submissions, my solution looks almost identical to the editorial.