Блог пользователя exhausted

Автор exhausted, история, 8 месяцев назад, По-русски

автор: exhausted, разработчик: exhausted

1946A - Медиана массива

Разбор
Решение

автор: max0000561, разработчик: yunetive29

1946B - Максимальная сумма

Разбор
Решение

автор: exhausted, разработчик: exhausted

1946C - Разрезание дерева

Разбор
Решение

автор: azureglow, разработчик: azureglow

1946D - Подарок на день рождения

Разбор
Решение
Решение (74TrAkToR)

автор: yunetive29, разработчик: yunetive29

1946E - Девочка-перестановочка

Разбор
Решение

автор: exhausted, yunetive29, разработчик: exhausted, yunetive29

1946F - Никто не нужен

Разбор
Решение
Разбор задач Codeforces Round 936 (Div. 2)
  • Проголосовать: нравится
  • +147
  • Проголосовать: не нравится

»
8 месяцев назад, # |
Rev. 2   Проголосовать: нравится +143 Проголосовать: не нравится

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.

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    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

    • »
      »
      »
      8 месяцев назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      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?

      • »
        »
        »
        »
        8 месяцев назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          8 месяцев назад, # ^ |
          Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

          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

      • »
        »
        »
        »
        8 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          7 месяцев назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          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.

      • »
        »
        »
        »
        8 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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
        • »
          »
          »
          »
          »
          8 месяцев назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          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

          • »
            »
            »
            »
            »
            »
            8 месяцев назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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.

          • »
            »
            »
            »
            »
            »
            8 месяцев назад, # ^ |
            Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

            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

      • »
        »
        »
        »
        8 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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

      • »
        »
        »
        »
        8 месяцев назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        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://codeforces.me/contest/1946/submission/252842752

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится -12 Проголосовать: не нравится

    C editorial is fucking trash

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    because he is exhausted ..... LMAO

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Nice editorial . Really liked Problem C and D .

»
8 месяцев назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

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?

  • »
    »
    8 месяцев назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    I don't see why my code is wrong for https://codeforces.me/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.

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      8 месяцев назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        8 месяцев назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          8 месяцев назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

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

      • »
        »
        »
        »
        8 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          8 месяцев назад, # ^ |
          Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

          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?

          • »
            »
            »
            »
            »
            »
            8 месяцев назад, # ^ |
              Проголосовать: нравится +5 Проголосовать: не нравится

            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.

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      8 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

https://codeforces.me/contest/1946/submission/252802394

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

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

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

    It would fail for the following test case

    Spoiler
»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      8 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can you please provide a proof for this statement?

      • »
        »
        »
        »
        8 месяцев назад, # ^ |
        Rev. 2   Проголосовать: нравится +30 Проголосовать: не нравится

        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.

      • »
        »
        »
        »
        8 месяцев назад, # ^ |
          Проголосовать: нравится +17 Проголосовать: не нравится

        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$$$
        • »
          »
          »
          »
          »
          8 месяцев назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Автокомментарий: текст был обновлен пользователем azureglow (предыдущая версия, новая версия, сравнить).

»
8 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 ?

»
8 месяцев назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    8 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      8 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

      • »
        »
        »
        »
        8 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

wish i read D first

»
8 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

High quality editorial!

»
8 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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.

»
8 месяцев назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

Here is my stream discussin these problems

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

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      8 месяцев назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

  • »
    »
    8 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
8 месяцев назад, # |
  Проголосовать: нравится +40 Проголосовать: не нравится

I didn't know E was a standard problem.

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

Spoiler
  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      8 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        8 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        here it is
  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 месяцев назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится
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;
»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone tell me why the greedy solution works , means the proof , I tried solving it in contest but wasn't able to prove that greedy can work?

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
8 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    thanks! fixed it

    • »
      »
      »
      7 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Does anyone have D's solution using DSU?

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    C u mean?

    • »
      »
      »
      8 месяцев назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        8 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I had such solution, you may check my submission

        • »
          »
          »
          »
          »
          8 месяцев назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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?

          • »
            »
            »
            »
            »
            »
            8 месяцев назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Reading proof for C was a nice journey

»
8 месяцев назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      8 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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!

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can somebody help me why this is failing at 3rd test case? Overflow issue not able to figure out why it is happending? https://codeforces.me/contest/1946/submission/252902592

»
8 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Solution to problem C using Tree trimming submission

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

B is really just kadane

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

252783316 why is this code wrong,i just found max sum subarray indices and thgen added it 2 power k times and finally added all the rest ekements of original array

»
8 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

[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

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

This is my solution to problem C, the idea is same yet I'm getting TLE. Can anyone help? https://codeforces.me/contest/1946/submission/252888566

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    8 месяцев назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
         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?

    • »
      »
      »
      8 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        8 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I am just noticing the problem D is not having binary search tag, I though 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.

»
8 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 ?

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    Thanks!

    • »
      »
      »
      8 месяцев назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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.

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Any similar problem is there like E but easier?

Thanks in advance.

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 месяцев назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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.

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How is the formula for A derived?

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

very good competition.I like it!!!

»
8 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Does anyone have C solution using DSU?

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Hello, i just wanted to ask about this solution. Isn't (sum % P + P ) % P = (sum % P ); So why write that extra +P?

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How can we solve D using binary search? Can anyone share their soln or explain?

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

really liked problem F, thanks for the contest!

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

in problem B,i didn't understand the idea of modulo..can ypu explain it

»
8 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Hey, did you end up figuring it out. I was just doing this problem for practice and it seems I have the right algorithm but I don't get the modulo stuff either

»
7 месяцев назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone explain what is wrong here https://codeforces.me/contest/1946/submission/254039662

»
7 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 месяцев назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

Обратите внимание. В разборе задачи D под фразой "вернуть массив в исходное состояние" подразумевается вернуть массив в его предыдущее состояние, а не в самое изначальное, которое дано в тесте. Я сначала не так это понял и долго не мог разобраться, почему у меня ловит WA2 -_-

  • »
    »
    7 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    если бы ты не просто списывал с разбора, а вник бы в задачу и хоть немного подумал для чего эти откаты массива, ты бы все понял. если хочешь просто сдать задачу не думая — скопируй авторский код и не жалуйся на разбор, который даже не можешь нормально прочитать и осознать

    • »
      »
      »
      7 месяцев назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Я как раз вник в задачу и поэтому смог её залить и понять, что там предыдущее состояние. Меня просто смутило, что в разборе по-другому написано.

      Я вообще сначала хотел в предыдущее состояние откатывать, но потом прочитал разбор, где было написано исходное состояние и подумал, что это у меня что-то не так и решил возвращать массив в самое изначальное состояние.

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why does this code TLE for F?

https://codeforces.me/contest/1946/submission/254907291

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